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

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

top K 問題

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

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

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

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

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

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

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

方案一：排序法

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

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

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

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

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

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

排序單純靠想也知道不是最優(yōu)的方案，因為我提出的問題中，僅僅需要找到第 K 大的數(shù)，排序方案卻興師動眾把整個數(shù)組理順了，沒必要。

方案二：堆

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

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

小頂堆解決 Top K 問題的思路：小頂堆維護(hù)當(dāng)前掃描到的最大 K 個數(shù)，其后每一次掃描到的元素，若大于堆頂則入堆，然后刪除堆頂;依此往復(fù)，直至掃描完所有元素。Java 實現(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ù)一個 top K 的小頂堆還是維護(hù)一個 top(N - K) 的大頂堆，都需要占用 O(N/2) 的內(nèi)存，而對于海量數(shù)據(jù)而言，這顯示是一筆非常大的開銷。所以針對我比賽的場景，堆的方案可以直接 pass。

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

方案三：Quick Select

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

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

Quick Select 的 Java 實現(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 次查詢中，排序方案耗時為 6s，而 Quick Select 方案，僅需要 300ms，可以說是非常大的優(yōu)化。

總結(jié)

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