十道面試題與十個海量數(shù)據(jù)處理方法總結(jié)(3)

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

    方案1：這題是考慮時間效率。用trie樹統(tǒng)計(jì)每個詞出現(xiàn)的次數(shù)，時間復(fù)雜度是O(n*le)（le表示單詞的平準(zhǔn)長度）。然后是找出出現(xiàn)最頻繁的前10個詞，可以用堆來實(shí)現(xiàn)，前面的題中已經(jīng)講到了，時間復(fù)雜度是O(n*lg10)。所以總的時間復(fù)雜度，是O(n*le)與O(n*lg10)中較大的哪一個。

附、100w個數(shù)中找出最大的100個數(shù)。

    方案1：在前面的題中，我們已經(jīng)提到了，用一個含100個元素的最小堆完成。復(fù)雜度為O(100w*lg100)。

    方案2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比100多的時候，采用傳統(tǒng)排序算法排序，取前100個。復(fù)雜度為O(100w*100)。

    方案3：采用局部淘汰法。選取前100個元素，并排序，記為序列L。然后一次掃描剩余的元素x，與排好序的100個元素中最小的元素比，如果比這個最小的要大，那么把這個最小的元素刪除，并把x利用插入排序的思想，插入到序列L中。依次循環(huán)，知道掃描了所有的元素。復(fù)雜度為O(100w*100)。

第二部分、十個海量數(shù)據(jù)處理方法大總結(jié)

    ok，看了上面這么多的面試題，是否有點(diǎn)頭暈。是的，需要一個總結(jié)。接下來，本文將簡單總結(jié)下一些處理海量數(shù)據(jù)問題的常見方法，而日后，本BLOG內(nèi)會具體闡述這些方法。

一、Bloom filter

　　適用范圍：可以用來實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集

　　基本原理及要點(diǎn)：
　　對于原理來說很簡單，位數(shù)組+k個獨(dú)立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在，很明顯這個過程并不保證查找的結(jié)果是100%正確的。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因?yàn)樵撽P(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字。所以一個簡單的改進(jìn)就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。

　　還有一個比較重要的問題，如何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)。當(dāng)hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應(yīng)該更大些，因?yàn)檫€要保證bit數(shù)組里至少一半為0，則m應(yīng)該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。

　　舉個例子我們假設(shè)錯誤率為0.01，則此時m應(yīng)大概是n的13倍。這樣k大概是8個。

　　注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數(shù)為單位(準(zhǔn)確的說是不同元素的個數(shù))。通常單個元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。

　　擴(kuò)展：
　　Bloom filter將集合中的元素映射到位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴(kuò)展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。

　　問題實(shí)例：給你A,B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？

　　根據(jù)這個問題我們來計(jì)算下內(nèi)存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit?，F(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡單了。