教你如何迅速秒殺99%的海量數(shù)據(jù)處理面試題

前言

   一般而言，標(biāo)題含有“秒殺”，“99%”，“史上最全/最強(qiáng)”等詞匯的往往都脫不了嘩眾取寵之嫌，但進(jìn)一步來講，如果讀者讀罷此文，卻無任何收獲，那么，我也甘愿背負(fù)這樣的罪名，:-)，同時(shí)，此文可以看做是對這篇文章：十道海量數(shù)據(jù)處理面試題與十個(gè)方法大總結(jié)的一般抽象性總結(jié)。

    畢竟受文章和理論之限，本文摒棄絕大部分的細(xì)節(jié)，只談方法/模式論，且注重用最通俗最直白的語言闡述相關(guān)問題。最后，有一點(diǎn)必須強(qiáng)調(diào)的是，全文行文是基于面試題的分析基礎(chǔ)之上的，具體實(shí)踐過程中，還是得具體情況具體分析，且場景也遠(yuǎn)比本文所述的任何一種場景復(fù)雜得多。

    OK，若有任何問題，歡迎隨時(shí)不吝賜教。謝謝。

何謂海量數(shù)據(jù)處理？

   所謂海量數(shù)據(jù)處理，其實(shí)很簡單，海量，海量，何謂海量，就是數(shù)據(jù)量太大，所以導(dǎo)致要么是無法在較短時(shí)間內(nèi)迅速解決，要么是數(shù)據(jù)太大，導(dǎo)致無法一次性裝入內(nèi)存。

    那解決辦法呢?針對時(shí)間，我們可以采用巧妙的算法搭配合適的數(shù)據(jù)結(jié)構(gòu)，如Bloom filter/Hash/bit-map/堆/數(shù)據(jù)庫或倒排索引/trie/，針對空間，無非就一個(gè)辦法：大而化?。?/span>分而治之/hash映射，你不是說規(guī)模太大嘛，那簡單啊，就把規(guī)模大化為規(guī)模小的，各個(gè)擊破不就完了嘛。

    至于所謂的單機(jī)及集群問題，通俗點(diǎn)來講，單機(jī)就是處理裝載數(shù)據(jù)的機(jī)器有限(只要考慮cpu，內(nèi)存，硬盤的數(shù)據(jù)交互)，而集群，機(jī)器有多輛，適合分布式處理，并行計(jì)算(更多考慮節(jié)點(diǎn)和節(jié)點(diǎn)間的數(shù)據(jù)交互)。

    再者，通過本blog內(nèi)的有關(guān)海量數(shù)據(jù)處理的文章，我們已經(jīng)大致知道，處理海量數(shù)據(jù)問題，無非就是：

1. 分而治之/hash映射 + hash統(tǒng)計(jì) + 堆/快速/歸并排序；
2. 雙層桶劃分
   
3. Bloom filter/Bitmap；
4. Trie樹/數(shù)據(jù)庫/倒排索引；
5. 外排序；
6. 分布式處理之Hadoop/Mapreduce。

    本文接下來的部分，便針對這6種方法模式結(jié)合對應(yīng)的海量數(shù)據(jù)處理面試題分別具體闡述。

處理海量數(shù)據(jù)問題之六把密匙

密匙一、分而治之/Hash映射 + Hash統(tǒng)計(jì) + 堆/快速/歸并排序

1、海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個(gè)IP。

    既然是海量數(shù)據(jù)處理，那么可想而知，給我們的數(shù)據(jù)那就一定是海量的。針對這個(gè)數(shù)據(jù)的海量，我們?nèi)绾沃帜?對的，無非就是分而治之/hash映射 + hash統(tǒng)計(jì) + 堆/快速/歸并排序，說白了，就是先映射，而后統(tǒng)計(jì)，最后排序：

1. 分而治之/hash映射：針對數(shù)據(jù)太大，內(nèi)存受限，只能是：把大文件化成(取模映射)小文件，即16字方針：大而化小，各個(gè)擊破，縮小規(guī)模，逐個(gè)解決
2. hash統(tǒng)計(jì)：當(dāng)大文件轉(zhuǎn)化了小文件，那么我們便可以采用常規(guī)的Hashmap(ip，value)來進(jìn)行頻率統(tǒng)計(jì)。
3. 堆/快速排序：統(tǒng)計(jì)完了之后，便進(jìn)行排序(可采取堆排序)，得到次數(shù)最多的IP。

   具體而論，則是： “首先是這一天，并且是訪問百度的日志中的IP取出來，逐個(gè)寫入到一個(gè)大文件中。注意到IP是32位的，最多有個(gè)2^32個(gè)IP。同樣可以采用映射的方法，比如模1000，把整個(gè)大文件映射為1000個(gè)小文件，再找出每個(gè)小文中出現(xiàn)頻率最大的IP（可以采用Hash_map進(jìn)行頻率統(tǒng)計(jì)，然后再找出頻率最大的幾個(gè)）及相應(yīng)的頻率。然后再在這1000個(gè)最大的IP中，找出那個(gè)頻率最大的IP，即為所求?！?-十道海量數(shù)據(jù)處理面試題與十個(gè)方法大總結(jié)。

2、搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的長度為1-255字節(jié)。

    假設(shè)目前有一千萬個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。），請你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1G。

    由上面第1題，我們知道，數(shù)據(jù)大則劃為小的，但如果數(shù)據(jù)規(guī)模比較小，能一次性裝入內(nèi)存呢?比如這第2題，雖然有一千萬個(gè)Query，但是由于重復(fù)度比較高，因此事實(shí)上只有300萬的Query，每個(gè)Query255Byte，因此我們可以考慮把他們都放進(jìn)內(nèi)存中去，而現(xiàn)在只是需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，在這里，Hash Table絕對是我們優(yōu)先的選擇。所以我們摒棄分而治之/hash映射的方法，直接上hash統(tǒng)計(jì)，然后排序。So，

1. hash統(tǒng)計(jì)：先對這批海量數(shù)據(jù)預(yù)處理(維護(hù)一個(gè)Key為Query字串，Value為該Query出現(xiàn)次數(shù)的HashTable，即Hashmap(Query，Value)，每次讀取一個(gè)Query，如果該字串不在Table中，那么加入該字串，并且將Value值設(shè)為1；如果該字串在Table中，那么將該字串的計(jì)數(shù)加一即可。最終我們在O(N)的時(shí)間復(fù)雜度內(nèi)用Hash表完成了統(tǒng)計(jì)；
2. 堆排序：第二步、借助堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，找出Top K，時(shí)間復(fù)雜度為N‘logK。即借助堆結(jié)構(gòu)，我們可以在log量級的時(shí)間內(nèi)查找和調(diào)整/移動。因此，維護(hù)一個(gè)K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進(jìn)行對比所以，我們最終的時(shí)間復(fù)雜度是：O（N） + N'*O（logK），（N為1000萬，N’為300萬）。

    別忘了這篇文章中所述的堆排序思路：“維護(hù)k個(gè)元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個(gè)數(shù)，并假設(shè)它們即是最大的k個(gè)數(shù)，建堆費(fèi)時(shí)O（k），并調(diào)整堆（費(fèi)時(shí)O（logk））后，有k1>k2>...kmin（kmin設(shè)為小頂堆中最小元素）。繼續(xù)遍歷數(shù)列，每次遍歷一個(gè)元素x，與堆頂元素比較，若x>kmin，則更新堆（用時(shí)logk），否則不更新堆。這樣下來，總費(fèi)時(shí)O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各項(xiàng)操作時(shí)間復(fù)雜度均為logk。”--第三章續(xù)、Top K算法問題的實(shí)現(xiàn)。
    當(dāng)然，你也可以采用trie樹，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個(gè)元素的最小推來對出現(xiàn)頻率進(jìn)行排序。

3、有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。
       由上面那兩個(gè)例題，分而治之 + hash統(tǒng)計(jì) + 堆/快速排序這個(gè)套路，我們已經(jīng)開始有了屢試不爽的感覺。下面，再拿幾道再多多驗(yàn)證下。請看此第3題：又是文件很大，又是內(nèi)存受限，咋辦?還能怎么辦呢?無非還是：

1. 分而治之/hash映射：順序讀文件中，對于每個(gè)詞x，取hash(x)%5000，然后按照該值存到5000個(gè)小文件（記為x0,x1,...x4999）中。這樣每個(gè)文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。
2. hash統(tǒng)計(jì)：對每個(gè)小文件，采用trie樹/hash_map等統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率。
3. 堆/歸并排序：取出出現(xiàn)頻率最大的100個(gè)詞（可以用含100個(gè)結(jié)點(diǎn)的最小堆），并把100個(gè)詞及相應(yīng)的頻率存入文件，這樣又得到了5000個(gè)文件。最后就是把這5000個(gè)文件進(jìn)行歸并（類似于歸并排序）的過程了。