建站
咨詢
售后
建站咨詢
新聞中心
本文轉載自微信公眾號「Kirito的技術分享」，作者kiritomoe。轉載本文請聯(lián)系Kirito的技術分享公眾號。
創(chuàng)新互聯(lián)建站2013年開創(chuàng)至今，先為江城等服務建站，江城等地企業(yè)，進行企業(yè)商務咨詢服務。為江城企業(yè)網站制作PC+手機+微官網三網同步一站式服務解決您的所有建站問題。
簡單抽象一下問題，便是今天的主題：在一個百萬級無序的 long 數組中，尋找第 K 大的數。要求當然是越快找到越好。
top K 問題
題面一描述出來，很多人都會聯(lián)想到 top K 問題，這道題無論是算法領域還是工程領域，都討論的極其廣泛，并且在實際項目中也很容易會遇到類似的問題，我也正好趁著這個機會總結成一篇文章。
常見的 top K 問題，及其變種：
- 有 10000000 個記錄，這些查詢串的重復度比較高，如果除去重復后，不超過 3000000 個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。請統(tǒng)計最熱門的 10 個查詢串，要求使用的內存不能超過 1GB。
- 有 10 個文件，每個文件 1GB，每個文件的每一行存放的都是用戶的 query，每個文件的 query 都可能重復。按照 query 的頻度排序。
- 有一個 1GB 大小的文件，里面的每一行是一個詞，詞的大小不超過 16 個字節(jié)，內存限制大小是 1MB。返回頻數最高的 100 個詞。
- 提取某日訪問網站次數最多的那個 IP。
- 10 億個整數找出重復次數最多的 100 個整數。
- 搜索的輸入信息是一個字符串，統(tǒng)計 300 萬條輸入信息中最熱門的前 10 條，每次輸入的一個字符串為不超過 255B，內存使用只有 1GB。
- 有 1000 萬個身份證號以及他們對應的數據，身份證號可能重復，找出出現(xiàn)次數最多的身份證號。
傳統(tǒng) top K 問題的描述：
在海量數據中找出最大的前 K 個數
注意我這次提出的問題和傳統(tǒng) top K 有一點區(qū)別，傳統(tǒng)的 top K 問題要求的一般是”前 K 大的數“，而我現(xiàn)在遇到的是”第 K 大的數“。區(qū)別要說大也不大，但對于我們最終選擇的方案可能會有很大的區(qū)別。
我下面會介紹一些傳統(tǒng)的 top K 問題的解決思路。并且，按照我一貫的風格，肯定會有代碼放出來，你如果是為了尋找一個”海量無序數據尋找第 K 大的數“問題的答案，相信你可以直接 copy 我的代碼。
方案一：排序法
排序法是最容易想到的思路，復雜度為 O(nlogn) 。能夠想到的各類排序算法呼之欲出，快速排序、歸并排序、插入排序、猴子排序...etc
但是工程領域選擇方案，往往不能僅僅使用算法復雜度來評估：
- 每個排序方案數據的交換量
- 額外空間的申請量
- 平均復雜度
- 最壞復雜度
- 不同數據量下的表現(xiàn)
那這個時候有人就要問了，我該如何選擇合適的方案呢?哎，那我又要提到那句話了，benchmark everything!雖然你肯定知道我最終沒有選擇使用排序來解決第 K 大的問題，但我還是想分享給你我的一些測試結論。
在 100w~1000w 數據量級別的無序 long 數組中，JDK 自帶的 Array.sort() 比任何一個排序方案都要快。
Array.sort 的內部實現(xiàn)為 timsort，是一種優(yōu)化過后的歸并排序。
排序單純靠想也知道不是最優(yōu)的方案，因為我提出的問題中，僅僅需要找到第 K 大的數，排序方案卻興師動眾把整個數組理順了，沒必要。
方案二：堆
針對一般的 top K 問題，一般都會默認 K 很小，所以一般的 top K 問題，可以選擇使用堆來解決。
堆有個重要的性質：每個結點的值均不大于其左右孩子結點的值，則堆頂元素即為整個堆的最小值。JDK 中 PriorityQueue 實現(xiàn)了堆這個數據結構堆，通過指定 comparator 字段來表示小頂堆或大頂堆，默認為自然序(natural ordering)。
小頂堆解決 Top K 問題的思路：小頂堆維護當前掃描到的最大 K 個數，其后每一次掃描到的元素，若大于堆頂則入堆，然后刪除堆頂;依此往復，直至掃描完所有元素。Java 實現(xiàn)第 K 大整數代碼如下：
- public int findKthLargest(int[] nums, int k) {
- PriorityQueue
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 大的數，這里沒有說明 K 的范圍，那么最壞情況下，K == N/2，無論維護一個 top K 的小頂堆還是維護一個 top(N - K) 的大頂堆，都需要占用 O(N/2) 的內存，而對于海量數據而言，這顯示是一筆非常大的開銷。所以針對我比賽的場景，堆的方案可以直接 pass。
堆的解法適用于 K 較小的場景，而且非常方便維護前 K 個數。
方案三：Quick Select
Quick Select 你可能沒聽過，但快速排序(Quick Sort)你肯定有所耳聞，其實他們兩個算法的作者都是 Hoare，并且思想也非常接近：選取一個基準元素 pivot，將數組切分(partition)為兩個子數組，比 pivot 大的扔左子數組，比 pivot 小的扔右子數組，然后遞推地切分子數組。Quick Select 不同于 Quick Sort 之處在于其沒有對每個子數組做切分，而是對目標子數組做切分。其次，Quick Select 與Quick Sort 一樣，是一個不穩(wěn)定的算法;pivot 選取直接影響了算法的好壞，最壞情況下的時間復雜度達到了 O(n2)。
在大學參加 ACM 時，我便第一次接觸了該算法，記得那時數據量正好卡的 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 大數的方案，也是 benchmark 下來最快的方案。在 10 次查詢中，排序方案耗時為 6s，而 Quick Select 方案，僅需要 300ms，可以說是非常大的優(yōu)化。
總結
本文簡單介紹了無序數組求 Top K 問題和無序數組求第 K 大數字兩類非常相似的問題，并且提供了常見的三種解決方案。當然，該問題也有很多變種，例如在多核機器，多主機上求解 TopK，甚至可以引入外排和 MapReduce 的思想，其實已經是在考慮其他層面的優(yōu)化了，我在這里就不過多闡釋了。
本文題目：海量無序數據尋找第K大的數
本文URL：http://m.5511xx.com/article/cdesoop.html
