1、海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。
首先是這一天，并且是訪問百度的日志中的IP取出來，逐個寫入到一個大文件中。注意到IP是32位的，最多有個2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大文件映射為1000個小文件，再找出每個小文中出現(xiàn)頻率最大的IP（可以采用hash_map進(jìn)行頻率統(tǒng)計(jì)，然后再找出頻率最大的幾個）及相應(yīng)的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。
或者如下闡述：
算法思想：分而治之+Hash
- IP地址最多有2^32=4G種取值情況，所以不能完全加載到內(nèi)存中處理；
- 可以考慮采用“分而治之”的思想，按照IP地址的Hash(IP)24值，把海量IP日志分別存儲到1024個小文件中。這樣，每個小文件最多包含4MB個IP地址；
- 對于每一個小文件，可以構(gòu)建一個IP為key，出現(xiàn)次數(shù)為value的Hash map，同時記錄當(dāng)前出現(xiàn)次數(shù)最多的那個IP地址；
- 可以得到1024個小文件中的出現(xiàn)次數(shù)最多的IP，再依據(jù)常規(guī)的排序算法得到總體上出現(xiàn)次數(shù)最多的IP；
2、搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。
假設(shè)目前有一千萬個記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個。一個查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。），請你統(tǒng)計(jì)最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G。
典型的Top K算法，還是在這篇文章里頭有所闡述，
文中，給出的最終算法是：
- 第一步、先對這批海量數(shù)據(jù)預(yù)處理，在O（N）的時間內(nèi)用Hash表完成統(tǒng)計(jì)（之前寫成了排序，特此訂正。July、2011.04.27）；
- 第二步、借助堆這個數(shù)據(jù)結(jié)構(gòu)，找出Top K，時間復(fù)雜度為N‘logK。
即，借助堆結(jié)構(gòu)，我們可以在log量級的時間內(nèi)查找和調(diào)整/移動。因此，維護(hù)一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進(jìn)行對比所以，我們最終的時間復(fù)雜度是：O（N） + N’*O（logK），（N為1000萬，N’為300萬）。ok，更多，詳情，請參考原文。
或者：采用trie樹，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個元素的最小推來對出現(xiàn)頻率進(jìn)行排序。
3、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。
方案：順序讀文件中，對于每個詞x，取hash(x)P00，然后按照該值存到5000個小文件（記為x0,x1,…x4999）中。這樣每個文件大概是200k左右。
如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。
對每個小文件，統(tǒng)計(jì)每個文件中出現(xiàn)的詞以及相應(yīng)的頻率（可以采用trie樹/hash_map等），并取出出現(xiàn)頻率最大的100個詞（可以用含100個結(jié)點(diǎn)的最小堆），并把100個詞及相應(yīng)的頻率存入文件，這樣又得到了5000個文件。下一步就是把這5000個文件進(jìn)行歸并（類似與歸并排序）的過程了。
4、有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)。要求你按照query的頻度排序。
還是典型的TOP K算法，解決方案如下：
方案1：
順序讀取10個文件，按照hash(query)的結(jié)果將query寫入到另外10個文件（記為）中。這樣新生成的文件每個的大小大約也1G（假設(shè)hash函數(shù)是隨機(jī)的）。
找一臺內(nèi)存在2G左右的機(jī)器，依次對用hash_map(query, query_count)來統(tǒng)計(jì)每個query出現(xiàn)的次數(shù)。利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的query和對應(yīng)的query_cout輸出到文件中。這樣得到了10個排好序的文件（記為）。
對這10個文件進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。
方案2：
一般query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對于所有的query，一次性就可以加入到內(nèi)存了。這樣，我們就可以采用trie樹/hash_map等直接來統(tǒng)計(jì)每個query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。
更多詳細(xì)信息，請您微信關(guān)注“計(jì)算網(wǎng)”公眾號：
