數據分析面試題:如何從10億查詢詞找出出現頻率最高的10個?

1． 問題描述

在大規模數據處理中，常遇到的一類問題是，在海量數據中找出出現頻率最高的前K個數，或者從海量數據中找出最大的前K個數，這類問題通常稱為“top K”問題，如：在搜索引擎中，統計搜索最熱門的10個查詢詞；在歌曲庫中統計下載率最高的前10首歌等等。

2． 當前解決方案

針對top k類問題，通常比較好的方案是【分治+trie樹/hash+小頂堆】，即先將數據集按照hash方法分解成多個小數據集，然后使用trie樹或者hash統計每個小數據集中的query詞頻，之后用小頂堆求出每個數據集中出頻率最高的前K個數，最后在所有top K中求出最終的top K。

實際上，最優的解決方案應該是最符合實際設計需求的方案，在實際應用中，可能有足夠大的內存，那么直接將數據扔到內存中一次性處理即可，也可能機器有多個核，這樣可以采用多線程處理整個數據集。

本文針對不同的應用場景，介紹了適合相應應用場景的解決方案。

3． 解決方案

3.1 單機+單核+足夠大內存

設每個查詢詞平均占8Byte，則10億個查詢詞所需的內存大約是10^9*8=8G內存。如果你有這么大的內存，直接在內存中對查詢詞進行排序，順序遍歷找出10個出現頻率最大的10個即可。這種方法簡單快速，更加實用。當然，也可以先用HashMap求出每個詞出現的頻率，然后求出出現頻率最大的10個詞。

3.2 單機+多核+足夠大內存

這時可以直接在內存中實用hash方法將數據劃分成n個partition，每個partition交給一個線程處理，線程的處理邏輯是同3.1節類似，最后一個線程將結果歸并。

該方法存在一個瓶頸會明顯影響效率，即數據傾斜，每個線程的處理速度可能不同，快的線程需要等待慢的線程，最終的處理速度取決于慢的線程。解決方法是，將數據劃分成c*n個partition（c>1），每個線程處理完當前partition后主動取下一個partition繼續處理，直到所有數據處理完畢，最后由一個線程進行歸并。

3.3 單機+單核+受限內存

這種情況下，需要將原數據文件切割成一個一個小文件，如，采用hash(x)%M，將原文件中的數據切割成M小文件，如果小文件仍大于內存大小，繼續采用hash的方法對數據文件進行切割，直到每個小文件小于內存大小，這樣，每個文件可放到內存中處理。采用3.1節的方法依次處理每個小文件。

3.4 多機+受限內存

這種情況下，為了合理利用多臺機器的資源，可將數據分發到多臺機器上，每臺機器采用3.3節中的策略解決本地的數據?？刹捎胔ash+socket方法進行數據分發。

從實際應用的角度考慮，3.1~3.4節的方案并不可行，因為在大規模數據處理環境下，作業效率并不是首要考慮的問題，算法的擴展性和容錯性才是首要考慮的。算法應該具有良好的擴展性，以便數據量進一步加大（隨著業務的發展，數據量加大是必然的）時，在不修改算法框架的前提下，可達到近似的線性比；算法應該具有容錯性，即當前某個文件處理失敗后，能自動將其交給另外一個線程繼續處理，而不是從頭開始處理。

Top k問題很適合采用MapReduce框架解決，用戶只需編寫一個map函數和兩個reduce 函數，然后提交到Hadoop（采用mapchain和reducechain）上即可解決該問題。對于map函數，采用hash算法，將hash值相同的數據交給同一個reduce task；對于第一個reduce函數，采用HashMap統計出每個詞出現的頻率，對于第二個reduce 函數，統計所有reduce task輸出數據中的top k即可。

4． 總結

Top K問題是一個非常常見的問題，公司一般不會自己寫個程序進行計算，而是提交到自己核心的數據處理平臺上計算，該平臺的計算效率可能不如直接寫程序高，但它具有良好的擴展性和容錯性，而這才是企業最看重的。