海量數(shù)據(jù)處理 - 10億個(gè)數(shù)中找出最大的10000個(gè)數(shù)（top K問題）

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載

? ? ? ? 前兩天面試3面學(xué)長問我的這個(gè)問題（想說TEG的3個(gè)面試學(xué)長都是好和藹，希望能完成最后一面，各方面原因造成我無比想去鵝場的心已經(jīng)按捺不住了），這個(gè)問題還是建立最小堆比較好一些。

? ? ? ? 先拿10000個(gè)數(shù)建堆，然后一次添加剩余元素，如果大于堆頂?shù)臄?shù)（10000中最小的），將這個(gè)數(shù)替換堆頂，并調(diào)整結(jié)構(gòu)使之仍然是一個(gè)最小堆，這樣，遍歷完后，堆中的10000個(gè)數(shù)就是所需的最大的10000個(gè)。建堆時(shí)間復(fù)雜度是O（mlogm），算法的時(shí)間復(fù)雜度為O（nmlogm）（n為10億，m為10000）。

? ? ? ? 優(yōu)化的方法：可以把所有10億個(gè)數(shù)據(jù)分組存放，比如分別放在1000個(gè)文件中。這樣處理就可以分別在每個(gè)文件的10^6個(gè)數(shù)據(jù)中找出最大的10000個(gè)數(shù)，合并到一起在再找出最終的結(jié)果。

? ? ? ? 以上就是面試時(shí)簡單提到的內(nèi)容，下面整理一下這方面的問題：

top K問題

在大規(guī)模數(shù)據(jù)處理中，經(jīng)常會遇到的一類問題：在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個(gè)數(shù)，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)，這類問題通常被稱為top K問題。例如，在搜索引擎中，統(tǒng)計(jì)搜索最熱門的10個(gè)查詢詞；在歌曲庫中統(tǒng)計(jì)下載最高的前10首歌等。

? ? ? ? 針對top K類問題，通常比較好的方案是分治+Trie樹/hash+小頂堆（就是上面提到的最小堆），即先將數(shù)據(jù)集按照Hash方法分解成多個(gè)小數(shù)據(jù)集，然后使用Trie樹活著Hash統(tǒng)計(jì)每個(gè)小數(shù)據(jù)集中的query詞頻，之后用小頂堆求出每個(gè)數(shù)據(jù)集中出現(xiàn)頻率最高的前K個(gè)數(shù)，最后在所有top K中求出最終的top K。

eg：有1億個(gè)浮點(diǎn)數(shù)，如果找出期中最大的10000個(gè)？

? ? ? ??最容易想到的方法是將數(shù)據(jù)全部排序，然后在排序后的集合中進(jìn)行查找，最快的排序算法的時(shí)間復(fù)雜度一般為O（nlogn），如快速排序。但是在32位的機(jī)器上，每個(gè)float類型占4個(gè)字節(jié)，1億個(gè)浮點(diǎn)數(shù)就要占用400MB的存儲空間，對于一些可用內(nèi)存小于400M的計(jì)算機(jī)而言，很顯然是不能一次將全部數(shù)據(jù)讀入內(nèi)存進(jìn)行排序的。其實(shí)即使內(nèi)存能夠滿足要求（我機(jī)器內(nèi)存都是8GB），該方法也并不高效，因?yàn)轭}目的目的是尋找出最大的10000個(gè)數(shù)即可，而排序卻是將所有的元素都排序了，做了很多的無用功。

? ? ? ??第二種方法為局部淘汰法，該方法與排序方法類似，用一個(gè)容器保存前10000個(gè)數(shù)，然后將剩余的所有數(shù)字——與容器內(nèi)的最小數(shù)字相比，如果所有后續(xù)的元素都比容器內(nèi)的10000個(gè)數(shù)還小，那么容器內(nèi)這個(gè)10000個(gè)數(shù)就是最大10000個(gè)數(shù)。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大，則刪掉容器內(nèi)最小元素，并將該元素插入容器，最后遍歷完這1億個(gè)數(shù)，得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了。此時(shí)的時(shí)間復(fù)雜度為O（n+m^2），其中m為容器的大小，即10000。

? ? ? ??第三種方法是分治法，將1億個(gè)數(shù)據(jù)分成100份，每份100萬個(gè)數(shù)據(jù)，找到每份數(shù)據(jù)中最大的10000個(gè)，最后在剩下的100*10000個(gè)數(shù)據(jù)里面找出最大的10000個(gè)。如果100萬數(shù)據(jù)選擇足夠理想，那么可以過濾掉1億數(shù)據(jù)里面99%的數(shù)據(jù)。100萬個(gè)數(shù)據(jù)里面查找最大的10000個(gè)數(shù)據(jù)的方法如下：用快速排序的方法，將數(shù)據(jù)分為2堆，如果大的那堆個(gè)數(shù)N大于10000個(gè)，繼續(xù)對大堆快速排序一次分成2堆，如果大的那堆個(gè)數(shù)N大于10000個(gè)，繼續(xù)對大堆快速排序一次分成2堆，如果大堆個(gè)數(shù)N小于10000個(gè)，就在小的那堆里面快速排序一次，找第10000-n大的數(shù)字；遞歸以上過程，就可以找到第1w大的數(shù)。參考上面的找出第1w大數(shù)字，就可以類似的方法找到前10000大數(shù)字了。此種方法需要每次的內(nèi)存空間為10^6*4=4MB，一共需要101次這樣的比較。

? ? ? ??第四種方法是Hash法。如果這1億個(gè)書里面有很多重復(fù)的數(shù)，先通過Hash法，把這1億個(gè)數(shù)字去重復(fù)，這樣如果重復(fù)率很高的話，會減少很大的內(nèi)存用量，從而縮小運(yùn)算空間，然后通過分治法或最小堆法查找最大的10000個(gè)數(shù)。

? ? ? ? 第五種方法采用最小堆。首先讀入前10000個(gè)數(shù)來創(chuàng)建大小為10000的最小堆，建堆的時(shí)間復(fù)雜度為O（mlogm）（m為數(shù)組的大小即為10000），然后遍歷后續(xù)的數(shù)字，并于堆頂（最小）數(shù)字進(jìn)行比較。如果比最小的數(shù)小，則繼續(xù)讀取后續(xù)數(shù)字；如果比堆頂數(shù)字大，則替換堆頂元素并重新調(diào)整堆為最小堆。整個(gè)過程直至1億個(gè)數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有10000個(gè)數(shù)字。該算法的時(shí)間復(fù)雜度為O（nmlogm），空間復(fù)雜度是10000（常數(shù)）。

實(shí)際運(yùn)行：

? ? ? ? 實(shí)際上，最優(yōu)的解決方案應(yīng)該是最符合實(shí)際設(shè)計(jì)需求的方案，在時(shí)間應(yīng)用中，可能有足夠大的內(nèi)存，那么直接將數(shù)據(jù)扔到內(nèi)存中一次性處理即可，也可能機(jī)器有多個(gè)核，這樣可以采用多線程處理整個(gè)數(shù)據(jù)集。

? ? ? ?下面針對不容的應(yīng)用場景，分析了適合相應(yīng)應(yīng)用場景的解決方案。

（1）單機(jī)+單核+足夠大內(nèi)存

? ? ? ? 如果需要查找10億個(gè)查詢次（每個(gè)占8B）中出現(xiàn)頻率最高的10個(gè)，考慮到每個(gè)查詢詞占8B，則10億個(gè)查詢次所需的內(nèi)存大約是10^9 * 8B=8GB內(nèi)存。如果有這么大內(nèi)存，直接在內(nèi)存中對查詢次進(jìn)行排序，順序遍歷找出10個(gè)出現(xiàn)頻率最大的即可。這種方法簡單快速，使用。然后，也可以先用HashMap求出每個(gè)詞出現(xiàn)的頻率，然后求出頻率最大的10個(gè)詞。

（2）單機(jī)+多核+足夠大內(nèi)存

? ? ? ? 這時(shí)可以直接在內(nèi)存總使用Hash方法將數(shù)據(jù)劃分成n個(gè)partition，每個(gè)partition交給一個(gè)線程處理，線程的處理邏輯同（1）類似，最后一個(gè)線程將結(jié)果歸并。

? ? ? ? 該方法存在一個(gè)瓶頸會明顯影響效率，即數(shù)據(jù)傾斜。每個(gè)線程的處理速度可能不同，快的線程需要等待慢的線程，最終的處理速度取決于慢的線程。而針對此問題，解決的方法是，將數(shù)據(jù)劃分成c×n個(gè)partition（c>1），每個(gè)線程處理完當(dāng)前partition后主動取下一個(gè)partition繼續(xù)處理，知道所有數(shù)據(jù)處理完畢，最后由一個(gè)線程進(jìn)行歸并。

（3）單機(jī)+單核+受限內(nèi)存

? ? ? ? 這種情況下，需要將原數(shù)據(jù)文件切割成一個(gè)一個(gè)小文件，如次啊用hash(x)%M，將原文件中的數(shù)據(jù)切割成M小文件，如果小文件仍大于內(nèi)存大小，繼續(xù)采用Hash的方法對數(shù)據(jù)文件進(jìn)行分割，知道每個(gè)小文件小于內(nèi)存大小，這樣每個(gè)文件可放到內(nèi)存中處理。采用（1）的方法依次處理每個(gè)小文件。

（4）多機(jī)+受限內(nèi)存

? ? ? ? 這種情況，為了合理利用多臺機(jī)器的資源，可將數(shù)據(jù)分發(fā)到多臺機(jī)器上，每臺機(jī)器采用（3）中的策略解決本地的數(shù)據(jù)。可采用hash+socket方法進(jìn)行數(shù)據(jù)分發(fā)。

? ? ? ? 從實(shí)際應(yīng)用的角度考慮，（1）（2）（3）（4）方案并不可行，因?yàn)樵诖笠?guī)模數(shù)據(jù)處理環(huán)境下，作業(yè)效率并不是首要考慮的問題，算法的擴(kuò)展性和容錯(cuò)性才是首要考慮的。算法應(yīng)該具有良好的擴(kuò)展性，以便數(shù)據(jù)量進(jìn)一步加大（隨著業(yè)務(wù)的發(fā)展，數(shù)據(jù)量加大是必然的）時(shí)，在不修改算法框架的前提下，可達(dá)到近似的線性比；算法應(yīng)該具有容錯(cuò)性，即當(dāng)前某個(gè)文件處理失敗后，能自動將其交給另外一個(gè)線程繼續(xù)處理，而不是從頭開始處理。

? ? ? ? top K問題很適合采用MapReduce框架解決，用戶只需編寫一個(gè)Map函數(shù)和兩個(gè)Reduce 函數(shù)，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解決該問題。具體而言，就是首先根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(MD5)后的值按照范圍劃分到不同的機(jī)器上，最好可以讓數(shù)據(jù)劃分后一次讀入內(nèi)存，這樣不同的機(jī)器負(fù)責(zé)處理不同的數(shù)值范圍，實(shí)際上就是Map。得到結(jié)果后，各個(gè)機(jī)器只需拿出各自出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，然后匯總，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，這實(shí)際上就是Reduce過程。對于Map函數(shù)，采用Hash算法，將Hash值相同的數(shù)據(jù)交給同一個(gè)Reduce task；對于第一個(gè)Reduce函數(shù)，采用HashMap統(tǒng)計(jì)出每個(gè)詞出現(xiàn)的頻率，對于第二個(gè)Reduce 函數(shù)，統(tǒng)計(jì)所有Reduce task，輸出數(shù)據(jù)中的top K即可。

? ? ? ? 直接將數(shù)據(jù)均分到不同的機(jī)器上進(jìn)行處理是無法得到正確的結(jié)果的。因?yàn)橐粋€(gè)數(shù)據(jù)可能被均分到不同的機(jī)器上，而另一個(gè)則可能完全聚集到一個(gè)機(jī)器上，同時(shí)還可能存在具有相同數(shù)目的數(shù)據(jù)。

以下是一些經(jīng)常被提及的該類問題。

（1）有10000000個(gè)記錄，這些查詢串的重復(fù)度比較高，如果除去重復(fù)后，不超過3000000個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。請統(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è)身份證號以及他們對應(yīng)的數(shù)據(jù)，身份證號可能重復(fù)，找出出現(xiàn)次數(shù)最多的身份證號。

重復(fù)問題

? ? ? ? 在海量數(shù)據(jù)中查找出重復(fù)出現(xiàn)的元素或者去除重復(fù)出現(xiàn)的元素也是常考的問題。針對此類問題，一般可以通過位圖法實(shí)現(xiàn)。例如，已知某個(gè)文件內(nèi)包含一些電話號碼，每個(gè)號碼為8位數(shù)字，統(tǒng)計(jì)不同號碼的個(gè)數(shù)。

? ? ? ? 本題最好的解決方法是通過使用位圖法來實(shí)現(xiàn)。8位整數(shù)可以表示的最大十進(jìn)制數(shù)值為99999999。如果每個(gè)數(shù)字對應(yīng)于位圖中一個(gè)bit位，那么存儲8位整數(shù)大約需要99MB。因?yàn)?B=8bit，所以99Mbit折合成內(nèi)存為99/8=12.375MB的內(nèi)存，即可以只用12.375MB的內(nèi)存表示所有的8位數(shù)電話號碼的內(nèi)容。

總結(jié)

以上是生活随笔為你收集整理的海量数据处理 - 10亿个数中找出最大的10000个数（top K）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。