海量数据处理方法的分析
本文可以認為是http://blog.csdn.net/v_JULY_v/article/details/6279498的讀后感，我是按照我理解的語言重新表述了一下而已。
海量數據處理的常用方法包括一下幾種：
1.分而治之/hash映射 + hash統計 + 堆/快速/歸并排序；
2.雙層桶劃分
3.Bloom filter/Bitmap；
4.Trie樹/數據庫/倒排索引；
5.外排序；
6.分布式處理之Hadoop/Mapreduce。
?
1. 分而治之/hash映射 + hash統計 + 堆/快速/歸并排序；
分治是算法的核心思想，不過需要證明分治是適用的才行。 如何分呢，就是用Hash函數來做，用hash函數把大數據集分成幾個小數據集，然后對小數據集進行統計，將多個子數據集的統計結果進行歸并排序。例如：
海量日志數據，提取出某日訪問百度次數最多的那個IP
可以IP地址按照IP%100，將IP地址分為100個子集，對各個子集分別統計頻度，然后取出各個子集出現最多的IP，進而得到整體出現最多的IP
?
假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門），請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。
這個也可以使用Trie樹,
有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。
?
海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10。
?
有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求你按照query的頻度排序。
?
給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？
?
?
2.雙層桶劃分
適用范圍：第k大，中位數，不重復或重復的數字
2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。
?
5億個int找它們的中位數。
這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。
?
實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。
3.Bloom filter/Bitmap
適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集
給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？
?
已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。
?
8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。
2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。
4.Trie樹/數據庫/倒排索引
適用范圍：數據量大，重復多，但是數據種類小可以放入內存
Trie樹主要用來實現詞頻統計
5.外排序
6.分布式處理之Hadoop/Mapreduce
?
http://blog.csdn.net/v_july_v/article/details/7382693
轉載于:https://www.cnblogs.com/whyandinside/archive/2012/07/07/2580755.html
總結
以上是生活随笔為你收集整理的海量数据处理方法的分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 转载.Android HAL实现的三种方
- 下一篇： [原] jQuery EasyUI 1.