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

   直接上：

1. hash映射：順序讀取10個文件，按照hash(query)%10的結果將query寫入到另外10個文件（記為）中。這樣新生成的文件每個的大小大約也1G（假設hash函數(shù)是隨機的）。
2. hash統(tǒng)計：找一臺內(nèi)存在2G左右的機器，依次對用hash_map(query, query_count)來統(tǒng)計每個query出現(xiàn)的次數(shù)。注：hash_map(query,query_count)是用來統(tǒng)計每個query的出現(xiàn)次數(shù)，不是存儲他們的值，出現(xiàn)一次，則count+1。
3. 堆/快速/歸并排序：利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進行排序。將排序好的query和對應的query_cout輸出到文件中。這樣得到了10個排好序的文件（記為）。對這10個文件進行歸并排序（內(nèi)排序與外排序相結合）。

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

5、 給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？

    可以估計每個文件安的大小為5G×64=320G，遠遠大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理?？紤]采取分而治之的方法。

1. 分而治之/hash映射：遍歷文件a，對每個url求取，然后根據(jù)所取得的值將url分別存儲到1000個小文件（記為）中。這樣每個小文件的大約為300M。遍歷文件b，采取和a相同的方式將url分別存儲到1000小文件中（記為）。這樣處理后，所有可能相同的url都在對應的小文件（）中，不對應的小文件不可能有相同的url。然后我們只要求出1000對小文件中相同的url即可。
2. hash統(tǒng)計：求每對小文件中相同的url時，可以把其中一個小文件的url存儲到hash_set中。然后遍歷另一個小文件的每個url，看其是否在剛才構建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

    OK，此第一種方法：分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序，再看最后三道題，如下：

6、怎么在海量數(shù)據(jù)中找出重復次數(shù)最多的一個？

    方案1：先做hash，然后求模映射為小文件，求出每個小文件中重復次數(shù)最多的一個，并記錄重復次數(shù)。然后找出上一步求出的數(shù)據(jù)中重復次數(shù)最多的一個就是所求（具體參考前面的題）。

7、上千萬或上億數(shù)據(jù)（有重復），統(tǒng)計其中出現(xiàn)次數(shù)最多的錢N個數(shù)據(jù)。

    方案1：上千萬或上億的數(shù)據(jù)，現(xiàn)在的機器的內(nèi)存應該能存下。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統(tǒng)計次數(shù)。然后就是取出前N個出現(xiàn)次數(shù)最多的數(shù)據(jù)了，可以用第2題提到的堆機制完成。

8、一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想，給出時間復雜度分析。

    接下來，咱們來看第二種方法，雙層捅劃分。

密匙二、雙層桶劃分

雙層桶劃分----其實本質(zhì)上還是分而治之的思想，重在“分”的技巧上！
　　適用范圍：第k大，中位數(shù)，不重復或重復的數(shù)字
　　基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行?？梢酝ㄟ^多次縮小，雙層只是一個例子。
　　擴展：
　　問題實例：

        1).2.5億個整數(shù)中找出不重復的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。
　　有點像鴿巢原理，整數(shù)個數(shù)為2^32,也就是，我們可以將這2^32個數(shù)，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

       2).5億個int找它們的中位數(shù)。
　　這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結果就可以判斷中位數(shù)落到那個區(qū)域，同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了。
　　實際上，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成2^20個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進行統(tǒng)計了。

密匙三：Bloom filter/Bitmap

Bloom filter

關于什么是Bloom filter，請參看此文：海量數(shù)據(jù)處理之Bloom Filter詳解。
　　適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重，或者集合求交集
　　基本原理及要點：
　　對于原理來說很簡單，位數(shù)組+k個獨立hash函數(shù)。將hash函數(shù)對應的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應位都是1說明存在，很明顯這個過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經(jīng)插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。
　　還有一個比較重要的問題，如何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數(shù)組里至少一半為0，則m應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。
　　舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。
　　注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數(shù)為單位(準確的說是不同元素的個數(shù))。通常單個元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。
　　擴展：
　　Bloom filter將集合中的元素映射到位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。
　　問題實例：給你A,B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？
　　根據(jù)這個問題我們來計算下內(nèi)存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit?，F(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。

    同時，上文的第5題：給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？如果允許有一定的錯誤率，可以使用Bloom filter，4G內(nèi)存大概可以表示340億bit。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應該是共同的url（注意會有一定的錯誤率）。

Bitmap

    至于什么是Bitmap，請看此文：http://blog.csdn.net/v_july_v/article/details/6685962。下面關于Bitmap的應用，直接上題，如下第9、10道：

9、在2.5億個整數(shù)中找出不重復的整數(shù)，注，內(nèi)存不足以容納這2.5億個整數(shù)。

    方案1：采用2-Bitmap（每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義）進行，共需內(nèi)存2^32 * 2 bit=1 GB內(nèi)存，還可以接受。然后掃描這2.5億個整數(shù)，查看Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應位是01的整數(shù)輸出即可。
    方案2：也可采用與第1題類似的方法，進行劃分小文件的方法。然后在小文件中找出不重復的整數(shù)，并排序。然后再進行歸并，注意去除重復的元素。

10、騰訊面試題：給40億個不重復的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當中？
    方案1：oo，申請512M的內(nèi)存，一個bit位代表一個unsigned int值。讀入40億個數(shù)，設置相應的bit位，讀入要查詢的數(shù)，查看相應bit位是否為1，為1表示存在，為0表示不存在。