海量資料處理算法舉例

1、 海量日志資料，提取出某日通路百度次數最多的那個IP。

首先是這一天，并且是通路百度的日志中的IP取出來，逐個寫入到一個大檔案中。注意到IP是32位的，最多有個2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大檔案映射為1000個小檔案，再找出每個小文中出現頻率最大的IP（可以采用hash_map進行頻率統計，然後再找出頻率最大的幾個）及相應的頻率。然後再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。

算法思想：分而治之+Hash

1.1

2.可以考慮采用“分而治之”的思想，按照IP位址的Hash(IP)%1024值，把海量IP日志分别存儲到1024個小檔案中。這樣，每個小檔案最多包含4MB個IP位址； 

3.對于每一個小檔案，可以建構一個IP為key，出現次數為value的Hash map，同時記錄目前出現次數最多的那個IP位址；

4.可以得到1024個小檔案中的出現次數最多的IP，再依據正常的排序算法得到總體上出現次數最多的IP；

2、搜尋引擎會通過日志檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255位元組。

第一步、先對這批海量資料預處理，在O（N）的時間内用Hash表完成統計（之前寫成了排序，特此訂正。July、2011.04.27）；

  第二步、借助堆這個資料結構，找出Top K，時間複雜度為N‘logK。即，借助堆結構，我們可以在log量級的時間内查找和調整/移動。是以，維護一個K(該題目中是10)大小的小根堆，然後周遊300萬的Query，分别和根元素進行對比是以，我們最終的時間複雜度是：O（N） + N'*O（logK），（N為1000萬，N’為300萬）。ok，更多，詳情，請參考原文。

    或者：采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最後用10個元素的最小推來對出現頻率進行排序。

3、有一個1G大小的一個檔案，裡面每一行是一個詞，詞的大小不超過16位元組，記憶體限制大小是1M。傳回頻數最高的100個詞。

方案：順序讀檔案中，對于每個詞x，取hash(x)%5000，然後按照該值存到5000個小檔案（記為x0,x1,...x4999）中。這樣每個檔案大概是200k左右。

 如果其中的有的檔案超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小檔案的大小都不超過1M。

對每個小檔案，統計每個檔案中出現的詞以及相應的頻率（可以采用trie樹/hash_map等），并取出出現頻率最大的100個詞（可以用含100個結點的最小堆），并把100個詞及相應的頻率存入檔案，這樣又得到了5000個檔案。下一步就是把這5000個檔案進行歸并（類似與歸并排序）的過程了。

4、有10個檔案，每個檔案1G，每個檔案的每一行存放的都是使用者的query，每個檔案的query都可能重複。要求你按照query的頻度排序。

 還是典型的TOP K算法，解決方案如下：

    方案1：

    順序讀取10個檔案，按照hash(query)%10的結果将query寫入到另外10個檔案（記為）中。這樣新生成的檔案每個的大小大約也1G（假設hash函數是随機的）。

    找一台記憶體在2G左右的機器，依次對用hash_map(query, query_count)來統計每個query出現的次數。利用快速/堆/歸并排序按照出現次數進行排序。将排序好的query和對應的 query_cout輸出到檔案中。這樣得到了10個排好序的檔案（記為）。

對這10個檔案進行歸并排序（内排序與外排序相結合）。

    方案2：

     一般query的總量是有限的，隻是重複的次數比較多而已，可能對于所有的query，一次性就可以加入到記憶體了。這樣，我們就可以采用trie樹/hash_map等直接來統計每個query出現的次數，然後按出現次數做快速/堆/歸并排序就可以了。

方案3：

    與方案1類似，但在做完hash，分成多個檔案後，可以交給多個檔案來處理，采用分布式的架構來處理（比如MapReduce），最後再進行合并。

5、 給定a、b兩個檔案，各存放50億個url，每個url各占64位元組，記憶體限制是4G，讓你找出a、b檔案共同的url？

    方案1：可以估計每個檔案安的大小為5G×64=320G，遠遠大于記憶體限制的4G。是以不可能将其完全加載到記憶體中處理。考慮采取分而治之的方法。

    周遊檔案a，對每個url求取hash(url)%1000，然後根據所取得的值将url分别存儲到1000個小檔案（記為a0,a1,...,a999）中。這樣每個小檔案的大約為300M。

    周遊檔案b，采取和a相同的方式将url分别存儲到1000小檔案（記為b0,b1,...,b999）。這樣處理後，所有可能相同的url都在對應的小檔案（a0vsb0,a1vsb1,...,a999vsb999）中，不對應的小檔案不可能有相同的url。然後我們隻要求出1000對小檔案中相同的 url即可。

求每對小檔案中相同的url時，可以把其中一個小檔案的url存儲到hash_set中。然後周遊另一個小檔案的每個url，看其是否在剛才建構的hash_set中，如果是，那麼就是共同的url，存到檔案裡面就可以了。

6、在2.5億個整數中找出不重複的整數，注，記憶體不足以容納這2.5億個整數。

1.采用“分而自治”的思想，将2.5億個整數分撥到N個檔案中（N<1000）。

2.對于每一個小檔案，可以建構一個IP為key，出現次數為value的Hash map，同時記錄目前出現次數，最後塞選出value值為1的。

7、給40億個不重複的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中？

又因為2^32為40億多，是以給定一個數可能在，也可能不在其中；

這裡我們把40億個數中的每一個用32位的二進制來表示

假設這40億個數開始放在一個檔案中。

 然後将這40億個數分成兩類:

      1.最高位為0

      2.最高位為1

并将這兩類分别寫入到兩個檔案中，其中一個檔案中數的個數<=20億，而另一個>=20億（這相當于折半了）；

與要查找的數的最高位比較并接着進入相應的檔案再查找

    再然後把這個檔案為又分成兩類:

      1.次最高位為0

      2.次最高位為1

并将這兩類分别寫入到兩個檔案中，其中一個檔案中數的個數<=10億，而另一個>=10億（這相當于折半了）；

    與要查找的數的次最高位比較并接着進入相應的檔案再查找。

    .......

    以此類推，就可以找到了,而且時間複雜度為O(logn)