海量資料處理的基本方法總結

海量資料處理概述

所謂海量資料處理，就是資料量太大，無法在較短時間內迅速解決，無法一次性裝入記憶體。本文在前人的基礎上總結一下解決此類問題的辦法。那麼有什麼解決辦法呢？

時間複雜度方面，我們可以採用巧妙的演算法搭配合適的資料結構，如Bloom filter/Hash/bit-map/堆/資料庫或倒排索引/trie樹。空間複雜度方面，分而治之/hash對映。

海量資料處理的基本方法總結起來分為以下幾種：

分而治之/hash對映 + hash統計 + 堆/快速/歸併排序；

雙層桶劃分；

Bloom filter/Bitmap；

Trie樹/資料庫/倒排索引；

外排序；

分散式處理之Hadoop/Mapreduce。

前提基礎知識：

1 byte= 8 bit。

int整形一般為4 bytes 共32位bit。

2^32=4G。

1G=2^30=10。7億。

1 分而治之+hash對映+快速/歸併/堆排序

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

分析：50億*64=320G大小空間。

演算法思想1：hash 分解+ 分而治之 + 歸併

遍歷檔案a，對每個url根據某種hash規則求取hash（url）/1024，然後根據所取得的值將url分別儲存到1024個小檔案（

a0~a1023

）中。這樣每個小檔案的大約為300M。如果hash結果很集中使得某個檔案ai過大，可以在對ai進行二級hash（ai0~ai1024）。

這樣url就被hash到1024個不同級別的目錄中。然後可以分別比較檔案，a0VSb0……a1023VSb1023。求每對小檔案中相同的url時，可以把其中一個小檔案的url儲存到hash_map中。然後遍歷另一個小檔案的每個url，看其是否在剛才構建的hash_map中，如果是，那麼就是共同的url，存到檔案裡面就可以了。

把1024個級別目錄下相同的url合併起來。

問題2

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

解決思想1：hash分解+ 分而治之 +歸併

順序讀取10個檔案a0~a9，按照hash（query）%10的結果將query寫入到另外10個檔案（記為 b0~b9）中。這樣新生成的檔案每個的大小大約也1G（假設hash函式是隨機的）。

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

對這10個檔案c0c9進行歸併排序（內排序與外排序相結合）。每次取c0c9檔案的m個數據放到記憶體中，進行10m個數據的歸併，即使把歸併好的資料存到d結果檔案中。如果ci對應的m個數據全歸併完了，再從ci餘下的資料中取m個數據重新載入到記憶體中。直到所有ci檔案的所有資料全部歸併完成。

解決思想2： Trie樹

如果query的總量是有限的，只是重複的次數比較多而已，可能對於所有的query，一次性就可以加入到記憶體了。在這種假設前提下，我們就可以採用trie樹/hash_map等直接來統計每個query出現的次數，然後按出現次數做快速/堆/歸併排序就可以了。

問題3：

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

類似問題：怎麼在海量資料中找出重複次數最多的一個？

解決思想： hash分解+ 分而治之+歸併

順序讀檔案中，對於每個詞x，按照hash（x）/（1024*4）存到4096個小檔案中。這樣每個檔案大概是250k左右。如果其中的有的檔案超過了1M大小，還可以按照hash繼續往下分，直到分解得到的小檔案的大小都不超過1M。

對每個小檔案，統計每個檔案中出現的詞以及相應的頻率（可以採用trie樹/hash_map等），並取出出現頻率最大的100個詞（可以用含100個結點的最小堆），並把100詞及相應的頻率存入檔案。這樣又得到了4096個檔案。

下一步就是把這4096個檔案進行歸併的過程了。（類似與歸併排序）

問題4

海量日誌資料，提取出某日訪問百度次數最多的那個IP

解決思想： hash分解+ 分而治之 + 歸併

把這一天訪問百度的日誌中的IP取出來，逐個寫入到一個大檔案中。注意到IP是32位的，最多有2^32個IP。同樣可以採用hash對映的方法，比如模1024，把整個大檔案對映為1024個小檔案。

再找出每個小文中出現頻率最大的IP（可以採用hash_map進行頻率統計，然後再找出頻率最大的幾個）及相應的頻率。

然後再在這1024組最大的IP中，找出那個頻率最大的IP，即為所求。

問題5

海量資料分佈在100臺電腦中，想個辦法高效統計出這批資料的TOP10。

解決思想： 分而治之 + 歸併。

注意TOP10是取最大值或最小值。如果取頻率TOP10，就應該先hash分解。

在每臺電腦上求出TOP10，採用包含10個元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我們首先取前10個元素調整成最小堆，如果發現，然後掃描後面的資料，並與堆頂元素比較，如果比堆頂元素大，那麼用該元素替換堆頂，然後再調整為最小堆。最後堆中的元素就是TOP10大。

求出每臺電腦上的TOP10後，然後把這100臺電腦上的TOP10組合起來，共1000個數據，再利用上面類似的方法求出TOP10就可以了。

問題6

在2。5億個整數中找出不重複的整數，記憶體不足以容納這2。5億個整數。

解決思路1 ： hash 分解+ 分而治之 + 歸併

2。5億個int資料hash到1024個小檔案中a0a1023，如果某個小檔案大小還大於記憶體，進行多級hash。每個小檔案讀進記憶體，找出只出現一次的資料，輸出到b0b1023。最後資料合併即可。

解決思路2 ： 2-Bitmap

如果記憶體夠1GB的話，採用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需記憶體2^32*2bit=1GB記憶體。然後掃描這2。5億個整數，檢視Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事後，檢視bitmap，把對應位是01的整數輸出即可。

注意，如果是找出重複的資料，可以用1-bitmap。第一次bit位由0變1，第二次查詢到相應bit位為1說明是重複資料，輸出即可。

問題7

一共有N個機器，每個機器上有N個數。每個機器最多存O（N）個數並對它們操作。如何找到N^2個數中的中數？

解決思想1 ： hash分解 + 排序

按照升序順序把這些數字，hash劃分為N個範圍段。假設資料範圍是2^32 的unsigned int 型別。理論上第一臺機器應該存的範圍為0（2^32）/N，第i臺機器存的範圍是（2^32）*（i-1）/N（2^32）*i/N。hash過程可以掃描每個機器上的N個數，把屬於第一個區段的數放到第一個機器上，屬於第二個區段的數放到第二個機器上，…，屬於第N個區段的數放到第N個機器上。注意這個過程每個機器上儲存的數應該是O（N）的。

然後我們依次統計每個機器上數的個數，一次累加，直到找到第k個機器，在該機器上累加的數大於或等於（N2）/2，並把這個數記為x。那麼我們要找的中位數在第k個機器中，排在第（N2）/2-x個數，即為所求的中位數的複雜度是O（N^2）的。

解決思想2： 分而治之 + 歸併

先對每臺機器上的數進行排序。排好序後，我們採用歸併排序的思想，將這N個機器上的數歸併起來得到最終的排序。找到第（N2 * lgN^2）的。

2 Trie樹+紅黑樹+hash_map

這裡Trie樹木、紅黑樹或者hash_map可以認為是第一部分中分而治之演算法的具體實現方法之一。

問題1

上千萬或上億資料（有重複），統計其中出現次數最多的錢N個數據。

解決思路： 紅黑樹 + 堆排序

如果是上千萬或上億的int資料，現在的機器4G記憶體可以能存下。所以考慮採用hash_map/搜尋二叉樹/紅黑樹等來進行統計重複次數。

然後取出前N個出現次數最多的資料，可以用包含N個元素的最小堆找出頻率最大的N個數據。

問題2

1000萬字符串，其中有些是重複的，需要把重複的全部去掉，保留沒有重複的字串。請怎麼設計和實現？

解決思路：trie樹。

這題用trie樹比較合適，hash_map也應該能行。

問題3

一個文字檔案，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間複雜度分析。

解決思路： trie樹 + 堆排序

這題是考慮時間效率。

用trie樹統計每個詞出現的次數，時間複雜度是O（n*len）（len表示單詞的平準長度）。

然後找出出現最頻繁的前10個詞，可以用堆來實現，前面的題中已經講到了，時間複雜度是O（n

lg10）。

總的時間複雜度，是O（n

le）與O（n*lg10）中較大的哪一個。

問題4

搜尋引擎會透過日誌檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255位元組。假設目前有一千萬個記錄，這些查詢串的重複讀比較高，雖然總數是1千萬，但是如果去除重複和，不超過3百萬個。一個查詢串的重複度越高，說明查詢它的使用者越多，也就越熱門。請你統計最熱門的10個查詢串，要求使用的記憶體不能超過1G。

解決思想 ： trie樹 + 堆排序

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

3 BitMap或者Bloom Filter

3。1 BitMap

BitMap說白了很easy，就是透過bit位為1或0來標識某個狀態存不存在。可進行資料的快速查詢，判重，刪除，一般來說適合的處理資料範圍小於8*2^32。否則記憶體超過4G，記憶體資源消耗有點多。

問題1

已知某個檔案內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

解決思路： bitmap

8位最多99 999 999，需要100M個bit位，不到12M的記憶體空間。我們把0-99 999 999的每個數字對映到一個Bit位上，所以只需要99M個Bit==12MBytes，這樣，就用了小小的12M左右的記憶體表示了所有的8位數的電話

問題2

2。5億個整數中找出不重複的整數的個數，記憶體空間不足以容納這2。5億個整數。

解決思路：2bit map 或者兩個bitmap。

將bit-map擴充套件一下，用2bit表示一個數即可，00表示未出現，01表示出現一次，10表示出現2次及以上，11可以暫時不用。

在遍歷這些數的時候，如果對應位置的值是00，則將其置為01；如果是01，將其置為10；如果是10，則保持不變。需要記憶體大小是2^32/8*2=1G記憶體。

或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map，都是一樣的道理。

3。2 Bloom filter

Bloom filter可以看做是對bit-map的擴充套件。

參考july大神csdn文章 Bloom Filter 詳解

4 Hadoop+MapReduce

參考引用july大神 csdn文章

MapReduce的初步理解

Hadoop框架與MapReduce模式

參考July大神的csdn部落格文章 => 海量處理面試題