本文轉(zhuǎn)載自微信公眾號(hào)「Kirito的技術(shù)分享」，作者kiritomoe。轉(zhuǎn)載本文請(qǐng)聯(lián)系Kirito的技術(shù)分享公眾號(hào)。

簡(jiǎn)單抽象一下問題，便是今天的主題：在一個(gè)百萬級(jí)無序的 long 數(shù)組中，尋找第 K 大的數(shù)。要求當(dāng)然是越快找到越好。

top K 問題

題面一描述出來，很多人都會(huì)聯(lián)想到 top K 問題，這道題無論是算法領(lǐng)域還是工程領(lǐng)域，都討論的極其廣泛，并且在實(shí)際項(xiàng)目中也很容易會(huì)遇到類似的問題，我也正好趁著這個(gè)機(jī)會(huì)總結(jié)成一篇文章。

常見的 top K 問題，及其變種：

1. 有 10000000 個(gè)記錄，這些查詢串的重復(fù)度比較高，如果除去重復(fù)后，不超過 3000000 個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。請(qǐng)統(tǒng)計(jì)最熱門的 10 個(gè)查詢串，要求使用的內(nèi)存不能超過 1GB。
2. 有 10 個(gè)文件，每個(gè)文件 1GB，每個(gè)文件的每一行存放的都是用戶的 query，每個(gè)文件的 query 都可能重復(fù)。按照 query 的頻度排序。
3. 有一個(gè) 1GB 大小的文件，里面的每一行是一個(gè)詞，詞的大小不超過 16 個(gè)字節(jié)，內(nèi)存限制大小是 1MB。返回頻數(shù)最高的 100 個(gè)詞。
4. 提取某日訪問網(wǎng)站次數(shù)最多的那個(gè) IP。
5. 10 億個(gè)整數(shù)找出重復(fù)次數(shù)最多的 100 個(gè)整數(shù)。
6. 搜索的輸入信息是一個(gè)字符串，統(tǒng)計(jì) 300 萬條輸入信息中最熱門的前 10 條，每次輸入的一個(gè)字符串為不超過 255B，內(nèi)存使用只有 1GB。
7. 有 1000 萬個(gè)身份證號(hào)以及他們對(duì)應(yīng)的數(shù)據(jù)，身份證號(hào)可能重復(fù)，找出出現(xiàn)次數(shù)最多的身份證號(hào)。

傳統(tǒng) top K 問題的描述：

在海量數(shù)據(jù)中找出最大的前 K 個(gè)數(shù)

注意我這次提出的問題和傳統(tǒng) top K 有一點(diǎn)區(qū)別，傳統(tǒng)的 top K 問題要求的一般是”前 K 大的數(shù)“，而我現(xiàn)在遇到的是”第 K 大的數(shù)“。區(qū)別要說大也不大，但對(duì)于我們最終選擇的方案可能會(huì)有很大的區(qū)別。

我下面會(huì)介紹一些傳統(tǒng)的 top K 問題的解決思路。并且，按照我一貫的風(fēng)格，肯定會(huì)有代碼放出來，你如果是為了尋找一個(gè)”海量無序數(shù)據(jù)尋找第 K 大的數(shù)“問題的答案，相信你可以直接 copy 我的代碼。

方案一：排序法

排序法是最容易想到的思路，復(fù)雜度為 O(nlogn) 。能夠想到的各類排序算法呼之欲出，快速排序、歸并排序、插入排序、猴子排序...etc

但是工程領(lǐng)域選擇方案，往往不能僅僅使用算法復(fù)雜度來評(píng)估：

• 每個(gè)排序方案數(shù)據(jù)的交換量
• 額外空間的申請(qǐng)量
• 平均復(fù)雜度
• 最壞復(fù)雜度
• 不同數(shù)據(jù)量下的表現(xiàn)

那這個(gè)時(shí)候有人就要問了，我該如何選擇合適的方案呢?哎，那我又要提到那句話了，benchmark everything!雖然你肯定知道我最終沒有選擇使用排序來解決第 K 大的問題，但我還是想分享給你我的一些測(cè)試結(jié)論。

在 100w~1000w 數(shù)據(jù)量級(jí)別的無序 long 數(shù)組中，JDK 自帶的 Array.sort() 比任何一個(gè)排序方案都要快。

Array.sort 的內(nèi)部實(shí)現(xiàn)為 timsort，是一種優(yōu)化過后的歸并排序。

排序單純靠想也知道不是最優(yōu)的方案，因?yàn)槲姨岢龅膯栴}中，僅僅需要找到第 K 大的數(shù)，排序方案卻興師動(dòng)眾把整個(gè)數(shù)組理順了，沒必要。

方案二：堆

針對(duì)一般的 top K 問題，一般都會(huì)默認(rèn) K 很小，所以一般的 top K 問題，可以選擇使用堆來解決。

堆有個(gè)重要的性質(zhì)：每個(gè)結(jié)點(diǎn)的值均不大于其左右孩子結(jié)點(diǎn)的值，則堆頂元素即為整個(gè)堆的最小值。JDK 中 PriorityQueue 實(shí)現(xiàn)了堆這個(gè)數(shù)據(jù)結(jié)構(gòu)堆，通過指定 comparator 字段來表示小頂堆或大頂堆，默認(rèn)為自然序(natural ordering)。

小頂堆解決 Top K 問題的思路：小頂堆維護(hù)當(dāng)前掃描到的最大 K 個(gè)數(shù)，其后每一次掃描到的元素，若大于堆頂則入堆，然后刪除堆頂;依此往復(fù)，直至掃描完所有元素。Java 實(shí)現(xiàn)第 K 大整數(shù)代碼如下：

public int findKthLargest(int[] nums, int k) { 
  PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); 
  for (int num : nums) { 
    if (minQueue.size() < k || num > minQueue.peek()) 
      minQueue.offer(num); 
    if (minQueue.size() > k) 
      minQueue.poll(); 
  } 
  return minQueue.peek(); 
} 

回到我遇到的問題，求第 K 大的數(shù)，這里沒有說明 K 的范圍，那么最壞情況下，K == N/2，無論維護(hù)一個(gè) top K 的小頂堆還是維護(hù)一個(gè) top(N - K) 的大頂堆，都需要占用 O(N/2) 的內(nèi)存，而對(duì)于海量數(shù)據(jù)而言，這顯示是一筆非常大的開銷。所以針對(duì)我比賽的場(chǎng)景，堆的方案可以直接 pass。

堆的解法適用于 K 較小的場(chǎng)景，而且非常方便維護(hù)前 K 個(gè)數(shù)。

方案三：Quick Select

Quick Select 你可能沒聽過，但快速排序(Quick Sort)你肯定有所耳聞，其實(shí)他們兩個(gè)算法的作者都是 Hoare，并且思想也非常接近：選取一個(gè)基準(zhǔn)元素 pivot，將數(shù)組切分(partition)為兩個(gè)子數(shù)組，比 pivot 大的扔左子數(shù)組，比 pivot 小的扔右子數(shù)組，然后遞推地切分子數(shù)組。Quick Select 不同于 Quick Sort 之處在于其沒有對(duì)每個(gè)子數(shù)組做切分，而是對(duì)目標(biāo)子數(shù)組做切分。其次，Quick Select 與Quick Sort 一樣，是一個(gè)不穩(wěn)定的算法;pivot 選取直接影響了算法的好壞，最壞情況下的時(shí)間復(fù)雜度達(dá)到了 O(n2)。

在大學(xué)參加 ACM 時(shí)，我便第一次接觸了該算法，記得那時(shí)數(shù)據(jù)量正好卡的 Quick Sort 無法通過，Quick Select 可以通過。

Quick Select 的 Java 實(shí)現(xiàn)如下：

public static long quickSelect(long[] nums, int start, int end, int k) { 
        if (start == end) { 
            return nums[start]; 
        } 
        int left = start; 
        int right = end; 
        long pivot = nums[(start + end) / 2]; 
        while (left <= right) { 
            while (left <= right && nums[left] > pivot) { 
                left++; 
            } 
            while (left <= right && nums[right] < pivot) { 
                right--; 
            } 
            if (left <= right) { 
                long temp = nums[left]; 
                nums[left] = nums[right]; 
                nums[right] = temp; 
                left++; 
                right--; 
            } 
        } 
        if (start + k - 1 <= right) { 
            return quickSelect(nums, start, right, k); 
        } 
        if (start + k - 1 >= left) { 
            return quickSelect(nums, left, end, k - (left - start)); 
        } 
        return nums[right + 1]; 

最終，我選擇使用了方案三：Quick Select 作為我求解第 K 大數(shù)的方案，也是 benchmark 下來最快的方案。在 10 次查詢中，排序方案耗時(shí)為 6s，而 Quick Select 方案，僅需要 300ms，可以說是非常大的優(yōu)化。

總結(jié)

本文簡(jiǎn)單介紹了無序數(shù)組求 Top K 問題和無序數(shù)組求第 K 大數(shù)字兩類非常相似的問題，并且提供了常見的三種解決方案。當(dāng)然，該問題也有很多變種，例如在多核機(jī)器，多主機(jī)上求解 TopK，甚至可以引入外排和 MapReduce 的思想，其實(shí)已經(jīng)是在考慮其他層面的優(yōu)化了，我在這里就不過多闡釋了。