安防之家訊： 海量數(shù)據(jù)處理時候常用的方法，因為在處理海量數(shù)據(jù)的時候最大的難點就是無法把數(shù)據(jù)一次性讀入內(nèi)存進行排序、超找等操作，關鍵點就是如何把這海量數(shù)據(jù)劃分成盡可能接近內(nèi)存大小的數(shù)據(jù)塊進行處理，之后再把各個塊根據(jù)需要進行合并的操作處理。所以一般可以分為分塊處理或者Bit-Map。

海量數(shù)據(jù)處理在進行分塊處理的時候一般包括以下步驟：

首先進行數(shù)據(jù)預處理，一般采用的方法就是使用hash把大文件映射成小文件，這樣的好處就是每個相同類型的值肯定被映射到了同一個文件中，如：在處理url的時候采用hash(url)%1000，或者在處理ip的時候采用hash(ip)%1000，則可以保證相同的重復出現(xiàn)的url或者ip會映射到相同的小文件內(nèi)，如果設計的hash函數(shù)分布不均勻，導致映射后的小文件還是超出了內(nèi)存的大小，則可以在這個小文件上再采用hash映射，映射長跟小的文件，直至符合內(nèi)存大小位置。

然后進行各個映射到小文件中的海量數(shù)據(jù)處理：根據(jù)需要把各個小文件讀入內(nèi)存，之后在這個文件上根據(jù)需要進行排序、去重、統(tǒng)計重復出現(xiàn)的關鍵字的次數(shù)、查找前k大/小的元素等操作，在進行這些操作的時候一般采用的算法可以使用內(nèi)部排序算法、STL的hash_map或者hash_set容器進行排序、去重、統(tǒng)計、查找前k大/小的元素的操作

最后將各個經(jīng)過處理的小文件結果進行歸并得出最終結果：這個時候一般使用的算法就是trie樹、敗者樹、堆、外排序，以及內(nèi)排和外排相結合的方法進行處理。

以下幾個問題采用了這種海量數(shù)據(jù)處理方式：

1. 給定a、b連個文件，各存放50億調(diào)url，每個url最大為64字節(jié)，內(nèi)存限制是4G，找出兩個文件中相同的url

方案：將a、b兩個文件分別使用hash(url)%1000的hash函數(shù)映射為1000個大小約為300M的文件，這樣大小的文件就可以讀入內(nèi)存進行處理，并且二者如果存在相同的url則比存在于對應的ai和bi小文件中，之后分別對比ai和bi文件對比即可，具體方法可以是將ai讀入內(nèi)存存入到一個hash_set中，分別遍歷bi中的每個url看是否存在于這個hash_set中，若存在則重復，此外由于ai和bi與其他文件沒有任何關系，可以通過多線程或GPU并行處理進行加速。

2. 有10個文件，每個文件大小是1G，每個文件中的每一行存放的都是用戶的query，每個文件中的query都可能重復，要求按照query的頻度進行排序。

方案：順序讀取這10個文件，使用hash(query)%10的hash函數(shù)將每條query映射到10個文件中，這樣處理的目的在于使得存在于不同文件中的相同的query存儲到同一個文件中。然后找一臺內(nèi)存為2G大小的機器，一次將這10個文件讀入內(nèi)存使用hash_map(query,query_count)進行統(tǒng)計，將統(tǒng)計后的結果使用快排/堆/歸并排序等內(nèi)存排序算法進行排序，將排序之后的結果寫會到文件中；分別對這10個文件進行處理之后，利用歸并排序?qū)⑦@個10個文件處理后的結果進行排序即可，這個時候使用外排序和內(nèi)排序相結合的方法進行

3. 有一個1G大小的文件，其中每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存大小限制是1M，返回頻數(shù)最高的100個詞

方案：順序讀取文件，對于每個詞使用hash(x)%5000的hash函數(shù)映射到5000個大小為200kB大小的小文件中，這個時候相同的詞肯定都映射到了相同的文件中，之后將每一個小文件順序讀入內(nèi)存，使用hash_map或者tri樹統(tǒng)計詞頻，并去除出現(xiàn)頻率最大的100個詞，可以使用100個節(jié)點的堆，之后把結果寫回文件，最后把這5000個文件進行歸并得出5000個文件中出現(xiàn)頻率最高的100個詞，這個過程可以使用敗者樹來進行。

4. 海量數(shù)據(jù)日志數(shù)據(jù)處理，提取出某日訪問百度次數(shù)最多的那個IP

方案：和第三個題目處理過程相似，只是每次取最大的即可

5. 海量數(shù)據(jù)分布在100臺電腦中，想辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10

方案：和第二題的解決方案類似，這里不比進行詞頻統(tǒng)計了。分別在每臺電腦上求出TOP10，每個求取TOP10的時候可以使用10個頂點的堆來完成，之后歸并100臺電腦上的TOP10來得出最終的TOP10數(shù)據(jù)。

6. 在海量數(shù)據(jù)中找出重復次數(shù)最多的一個、最大的一個、（重復次數(shù)）最大的n個

方案：分別題目二、四、三結題思路相同

7. 有海量字符串數(shù)據(jù)處理，其中有些是重復的，需要把重復的全部去掉保留沒有重復的字符串

方案：首先映射為內(nèi)存可以處理的n個小文件，這時相同的字符串肯定在同一個文件中，在每個小文件中使用hash_set取出重復的字符串，之后寫到一個文件中，依次處理n個文件，即可得到結果

8. 100W個數(shù)中找出最大的100個數(shù)

方案：使用一個100個節(jié)點的小頂堆來進行查找即可，復雜度為100w*log100

使用Bit-Map一般處理的是數(shù)字的問題，其中心思想就是使用bit數(shù)組來表示某些key值的存在，一般用來處理查找某些數(shù)值型值是否存在的問題：

1. 在2.5億個整數(shù)中找出不重復的整數(shù)，內(nèi)存不足以容納著2.5億個整數(shù)

方案：整數(shù)是4個字節(jié)32bit的，所以一共可能有2^32個整數(shù)，為了表示這些整數(shù)是否存在，使用2bit來表示，00表示這個整數(shù)不存在，01表示出現(xiàn)1次，10表示出現(xiàn)多次，11表示無意義，這個bit數(shù)組共需要2^32*2bit=1GB內(nèi)存。數(shù)組的下標對應整數(shù)值，當該整數(shù)不存在是，這個下標中元素為00，出現(xiàn)1次時為01，多次時為10；最后將元素為10的下標輸出就是重復出現(xiàn)的整數(shù)

2. 使用bit-mao可以對不重復出現(xiàn)的數(shù)字序列進行排序，效率會比較高

3. 某個文件中包含一些電話號碼，每個號碼是8位數(shù)，統(tǒng)計不同號碼的個數(shù)

方案：8位的電話號碼最多可以表示99999999個電話號碼，現(xiàn)在使用1bit對應一個電話號碼，即99999999bit大約為10M+的內(nèi)存，每個bit若為0則表示這個號碼不存在，為1則表示這個號碼存在。每個bit對應的下標就是電話號碼對應的整數(shù)，最后遍歷整個數(shù)組，統(tǒng)計元素為1的個數(shù)即可。



安防之家專注于各種家居的安防,監(jiān)控,防盜,安防監(jiān)控,安防器材,安防設備的新聞資訊和O2O電商導購服務，敬請登陸安防之家：http://anfang.jc68.com/