建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號「Kirito的技術(shù)分享」，作者kiritomoe。轉(zhuǎn)載本文請聯(lián)系Kirito的技術(shù)分享公眾號。
創(chuàng)新互聯(lián)建站2013年開創(chuàng)至今，先為江城等服務(wù)建站，江城等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為江城企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
簡單抽象一下問題，便是今天的主題：在一個(gè)百萬級無序的 long 數(shù)組中，尋找第 K 大的數(shù)。要求當(dāng)然是越快找到越好。
top K 問題
題面一描述出來，很多人都會聯(lián)想到 top K 問題，這道題無論是算法領(lǐng)域還是工程領(lǐng)域，都討論的極其廣泛，并且在實(shí)際項(xiàng)目中也很容易會遇到類似的問題，我也正好趁著這個(gè)機(jī)會總結(jié)成一篇文章。
常見的 top K 問題，及其變種：
- 有 10000000 個(gè)記錄，這些查詢串的重復(fù)度比較高，如果除去重復(fù)后，不超過 3000000 個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。請統(tǒng)計(jì)最熱門的 10 個(gè)查詢串，要求使用的內(nèi)存不能超過 1GB。
- 有 10 個(gè)文件，每個(gè)文件 1GB，每個(gè)文件的每一行存放的都是用戶的 query，每個(gè)文件的 query 都可能重復(fù)。按照 query 的頻度排序。
- 有一個(gè) 1GB 大小的文件，里面的每一行是一個(gè)詞，詞的大小不超過 16 個(gè)字節(jié)，內(nèi)存限制大小是 1MB。返回頻數(shù)最高的 100 個(gè)詞。
- 提取某日訪問網(wǎng)站次數(shù)最多的那個(gè) IP。
- 10 億個(gè)整數(shù)找出重復(fù)次數(shù)最多的 100 個(gè)整數(shù)。
- 搜索的輸入信息是一個(gè)字符串，統(tǒng)計(jì) 300 萬條輸入信息中最熱門的前 10 條，每次輸入的一個(gè)字符串為不超過 255B，內(nèi)存使用只有 1GB。
- 有 1000 萬個(gè)身份證號以及他們對應(yīng)的數(shù)據(jù)，身份證號可能重復(fù)，找出出現(xiàn)次數(shù)最多的身份證號。
傳統(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ū)別要說大也不大，但對于我們最終選擇的方案可能會有很大的區(qū)別。
我下面會介紹一些傳統(tǒng)的 top K 問題的解決思路。并且，按照我一貫的風(fēng)格，肯定會有代碼放出來，你如果是為了尋找一個(gè)”海量無序數(shù)據(jù)尋找第 K 大的數(shù)“問題的答案，相信你可以直接 copy 我的代碼。
方案一：排序法
排序法是最容易想到的思路，復(fù)雜度為 O(nlogn) 。能夠想到的各類排序算法呼之欲出，快速排序、歸并排序、插入排序、猴子排序...etc
但是工程領(lǐng)域選擇方案，往往不能僅僅使用算法復(fù)雜度來評估：
- 每個(gè)排序方案數(shù)據(jù)的交換量
- 額外空間的申請量
- 平均復(fù)雜度
- 最壞復(fù)雜度
- 不同數(shù)據(jù)量下的表現(xiàn)
那這個(gè)時(shí)候有人就要問了，我該如何選擇合適的方案呢?哎，那我又要提到那句話了，benchmark everything!雖然你肯定知道我最終沒有選擇使用排序來解決第 K 大的問題，但我還是想分享給你我的一些測試結(jié)論。
在 100w~1000w 數(shù)據(jù)量級別的無序 long 數(shù)組中，JDK 自帶的 Array.sort() 比任何一個(gè)排序方案都要快。
Array.sort 的內(nèi)部實(shí)現(xiàn)為 timsort，是一種優(yōu)化過后的歸并排序。
排序單純靠想也知道不是最優(yōu)的方案，因?yàn)槲姨岢龅膯栴}中，僅僅需要找到第 K 大的數(shù)，排序方案卻興師動眾把整個(gè)數(shù)組理順了，沒必要。
方案二：堆
針對一般的 top K 問題，一般都會默認(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
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)存，而對于海量數(shù)據(jù)而言，這顯示是一筆非常大的開銷。所以針對我比賽的場景，堆的方案可以直接 pass。
堆的解法適用于 K 較小的場景，而且非常方便維護(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 之處在于其沒有對每個(gè)子數(shù)組做切分，而是對目標(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é)
本文簡單介紹了無序數(shù)組求 Top K 問題和無序數(shù)組求第 K 大數(shù)字兩類非常相似的問題，并且提供了常見的三種解決方案。當(dāng)然，該問題也有很多變種，例如在多核機(jī)器，多主機(jī)上求解 TopK，甚至可以引入外排和 MapReduce 的思想，其實(shí)已經(jīng)是在考慮其他層面的優(yōu)化了，我在這里就不過多闡釋了。
新聞標(biāo)題：海量無序數(shù)據(jù)尋找第K大的數(shù)
當(dāng)前網(wǎng)址：http://m.5511xx.com/article/cdesoop.html
