海量數(shù)據(jù)處理常用方法

1、大數(shù)據(jù)量的問題是很多面試筆試中經(jīng)常出現(xiàn)的問題,比如 google、淘寶、百度、騰訊這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會(huì)問到。下面的方法是我對海量數(shù)據(jù)的處理方法進(jìn)行了一個(gè)一般性的總結(jié),當(dāng)然這些方法可能并不能完全覆蓋所有的問題,但是這樣的一些方法也基本可以處理絕大多數(shù)遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目,方法不一定最優(yōu),如果你有更好的處理方法,歡迎與我討論。1.Bloom filter適用范圍:可以用來實(shí)現(xiàn)數(shù)據(jù)字典,進(jìn)行數(shù)據(jù)的判重,或者集合求交集基本原理及要點(diǎn):對于原理來說很簡單,位數(shù)組+k個(gè)獨(dú)立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1,查找時(shí)如果發(fā)現(xiàn)所有hash函數(shù)

2、對應(yīng)位都是1說明存在,很明顯這個(gè)過程并不保證查找的結(jié)果是100%正確的。同時(shí)也不支持刪除一個(gè)已經(jīng)插入的關(guān)鍵字,因?yàn)樵撽P(guān)鍵字對應(yīng)的位會(huì)牽動(dòng)到其他的關(guān)鍵字。所以一個(gè)簡單的改進(jìn)就是counting Bloom filter,用一個(gè)counter數(shù)組代替位數(shù)組,就可以支持刪除了。還有一個(gè)比較重要的問題,如何根據(jù)輸入元素個(gè)數(shù)n,確定位數(shù)組m的大小及hash 函數(shù)個(gè)數(shù)。當(dāng)hash函數(shù)個(gè)數(shù)k=(ln2*(m/n時(shí)錯(cuò)誤率最小。在錯(cuò)誤率不大于E 的情況下,m至少要等于n*lg(1/E才能表示任意n個(gè)元素的集合。但m還應(yīng)該更大些,因?yàn)檫€要保證bit數(shù)組里至少一半為 0,則m應(yīng)該>=nlg(1/E*lge 大

3、概就是nlg(1/E1.44倍(lg表示以2為底的對數(shù)。舉個(gè)例子我們假設(shè)錯(cuò)誤率為0.01,則此時(shí)m應(yīng)大概是n的13倍。這樣k大概是8個(gè)。注意這里m與n的單位不同,m是bit為單位,而n則是以元素個(gè)數(shù)為單位(準(zhǔn)確的說是不同元素的個(gè)數(shù)。通常單個(gè)元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。擴(kuò)展:Bloom filter將集合中的元素映射到位數(shù)組中,用k(k為哈希函數(shù)個(gè)數(shù)個(gè)映射位是否全1表示元素在不在這個(gè)集合中。Counting bloom filter(CBF將位數(shù)組中的每一位擴(kuò)展為一個(gè)counter,從而支持了元素的刪除操作。Spectral Bloom F

4、ilter(SBF將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。問題實(shí)例:給你A,B兩個(gè)文件,各存放50億條URL,每條URL占用64字節(jié),內(nèi)存限制是4G,讓你找出A,B文件共同的URL。如果是三個(gè)乃至n個(gè)文件呢?根據(jù)這個(gè)問題我們來計(jì)算下內(nèi)存的占用,4G=232大概是40億*8大概是340億, n=50億,如果按出錯(cuò)率0.01算需要的大概是650億個(gè) bit?，F(xiàn)在可用的是340億,相差并不多,這樣可能會(huì)使出錯(cuò)率上升些。另外如果這些urlip是一一對應(yīng)的,就可以轉(zhuǎn)換成ip,則大大簡單了。2.Hashing適用范圍:快速查找,刪除的基本數(shù)據(jù)結(jié)構(gòu),通常需要

5、總數(shù)據(jù)量可以放入內(nèi)存基本原理及要點(diǎn):hash函數(shù)選擇,針對字符串,整數(shù),排列,具體相應(yīng)的hash方法。碰撞處理,一種是open hashing,也稱為拉鏈法;另一種就是closed hashing,也稱開地址法,opened addressing。擴(kuò)展:d-left hashing中的d是多個(gè)的意思,我們先簡化這個(gè)問題,看一看2-left hashing。2-left hashing指的是將一個(gè)哈希表分成長度相等的兩半,分別叫做T1和T2,給T1和T2分別配備一個(gè)哈希函數(shù),h1和h2。在存儲(chǔ)一個(gè)新的key 時(shí),同時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算,得出兩個(gè)地址h1key和h2key。這時(shí)需要檢查T1中的

6、h1key位置和T2中的h2key位置,哪一個(gè)位置已經(jīng)存儲(chǔ)的(有碰撞的key比較多,然后將新key存儲(chǔ)在負(fù)載少的位置。如果兩邊一樣多,比如兩個(gè)位置都為空或者都存儲(chǔ)了一個(gè)key,就把新key 存儲(chǔ)在左邊的T1子表中, 2-left也由此而來。在查找一個(gè)key時(shí),必須進(jìn)行兩次hash,同時(shí)查找兩個(gè)位置。問題實(shí)例:1.海量日志數(shù)據(jù),提取出某日訪問百度次數(shù)最多的那個(gè)IP。IP的數(shù)目還是有限的,最多232個(gè),所以可以考慮使用hash將ip直接存入內(nèi)存,然后進(jìn)行統(tǒng)計(jì)。3.bit-map適用范圍:可進(jìn)行數(shù)據(jù)的快速查找,判重,刪除,一般來說數(shù)據(jù)范圍是int的10倍以下基本原理及要點(diǎn):使用bit數(shù)組來表示某些元

7、素是否存在,比如8位電話號(hào)碼擴(kuò)展:bloom filter可以看做是對bit-map的擴(kuò)展問題實(shí)例:1已知某個(gè)文件內(nèi)包含一些電話號(hào)碼,每個(gè)號(hào)碼為8位數(shù)字,統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。8位最多99 999 999,大概需要99m個(gè)bit,大概10幾m字節(jié)的內(nèi)存即可。22.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù),內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。將bit-map擴(kuò)展一下,用2bit表示一個(gè)數(shù)即可,0表示未出現(xiàn),1表示出現(xiàn)一次, 2表示出現(xiàn)2次及以上?；蛘呶覀儾挥?bit來進(jìn)行表示,我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map。4.堆適用范圍:海量數(shù)據(jù)前n大,并且n比較小,堆可以放入內(nèi)存基本原理及

8、要點(diǎn):最大堆求前n小,最小堆求前n大。方法,比如求前n小,我們比較當(dāng)前元素與最大堆里的最大元素,如果它小于最大元素,則應(yīng)該替換那個(gè)最大元素。這樣最后得到的n個(gè)元素就是最小的n個(gè)。適合大數(shù)據(jù)量,求前n 小,n的大小比較小的情況,這樣可以掃描一遍即可得到所有的前n元素,效率很高。擴(kuò)展:雙堆,一個(gè)最大堆與一個(gè)最小堆結(jié)合,可以用來維護(hù)中位數(shù)。問題實(shí)例:1100w個(gè)數(shù)中找最大的前100個(gè)數(shù)。用一個(gè)100個(gè)元素大小的最小堆即可。5.雙層桶劃分-其實(shí)本質(zhì)上就是【分而治之】的思想,重在“分”的技巧上!適用范圍:第k大,中位數(shù),不重復(fù)或重復(fù)的數(shù)字基本原理及要點(diǎn):因?yàn)樵胤秶艽?不能利用直接尋址表,所以通過多次

9、劃分,逐步確定范圍,然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行?？梢酝ㄟ^多次縮小,雙層只是一個(gè)例子。擴(kuò)展:問題實(shí)例:有點(diǎn)像鴿巢原理,整數(shù)個(gè)數(shù)為232,也就是,我們可以將這232個(gè)數(shù),劃分為28個(gè)區(qū)域(比如用單個(gè)文件代表一個(gè)區(qū)域,然后將數(shù)據(jù)分離到不同的區(qū)域,然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間,就可以很方便的解決。2.5億個(gè)int找它們的中位數(shù)。這個(gè)例子比上面那個(gè)更明顯。首先我們將int劃分為216個(gè)區(qū)域,然后讀取數(shù)據(jù)統(tǒng)計(jì)落到各個(gè)區(qū)域里的數(shù)的個(gè)數(shù),之后我們根據(jù)統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到那個(gè)區(qū)域,同時(shí)知道這個(gè)區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計(jì)

10、落在這個(gè)區(qū)域中的那些數(shù)就可以了。實(shí)際上,如果不是int是int64,我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成224個(gè)區(qū)域,然后確定區(qū)域的第幾大數(shù),在將該區(qū)域分成220個(gè)子區(qū)域,然后確定是子區(qū)域的第幾大數(shù),然后子區(qū)域里的數(shù)的個(gè)數(shù)只有220,就可以直接利用direct addr table進(jìn)行統(tǒng)計(jì)了。6.數(shù)據(jù)庫索引適用范圍:大數(shù)據(jù)量的增刪改查基本原理及要點(diǎn):利用數(shù)據(jù)的設(shè)計(jì)實(shí)現(xiàn)方法,對海量數(shù)據(jù)的增刪改查進(jìn)行處理。擴(kuò)展:問題實(shí)例:7.倒排索引(Inverted index適用范圍:搜索引擎,關(guān)鍵字查詢基本原理及要點(diǎn):為何叫倒排索引?一種索引方法,被用來存儲(chǔ)在全文搜索

11、下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。以英文為例,下面是要被索引的文本:T0 = “it is what it is”T1 = “what is it”T2 = “it is a banana”我們就能得到下面的反向文件索引:“a”: 2“banana”: 2“is”: 0, 1, 2“it”: 0, 1, 2“what”: 0, 1檢索的條件”what”, “is” 和“it” 將對應(yīng)集合的交集。正向索引開發(fā)出來用來存儲(chǔ)每個(gè)文檔的單詞的列表。正向索引的查詢往往滿足每個(gè)文檔有序頻繁的全文查詢和每個(gè)單詞在校驗(yàn)文檔中的驗(yàn)證這樣的查詢。在正向索引中,文檔占據(jù)了中心的位置,每個(gè)文檔指向了

12、一個(gè)它所包含的索引項(xiàng)的序列。也就是說文檔指向了它包含的那些單詞,而反向索引則是單詞指向了包含它的文檔,很容易看到這個(gè)反向的關(guān)系。擴(kuò)展:問題實(shí)例:文檔檢索系統(tǒng),查詢那些文件包含了某單詞,比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索。8.外排序適用范圍:大數(shù)據(jù)的排序,去重基本原理及要點(diǎn):外排序的歸并方法,置換選擇敗者樹原理,最優(yōu)歸并樹擴(kuò)展:問題實(shí)例:1.有一個(gè)1G大小的一個(gè)文件,里面每一行是一個(gè)詞,詞的大小不超過16個(gè)字節(jié),內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。這個(gè)數(shù)據(jù)具有很明顯的特點(diǎn),詞的大小為16個(gè)字節(jié),但是內(nèi)存只有1m做hash 有些不夠,所以可以用來排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用。9.trie樹

13、適用范圍:數(shù)據(jù)量大,重復(fù)多,但是數(shù)據(jù)種類小可以放入內(nèi)存基本原理及要點(diǎn):實(shí)現(xiàn)方式,節(jié)點(diǎn)孩子的表示方式擴(kuò)展:壓縮實(shí)現(xiàn)。問題實(shí)例:1.有10個(gè)文件,每個(gè)文件1G,每個(gè)文件的每一行都存放的是用戶的query,每個(gè)文件的query都可能重復(fù)。要你按照query的頻度排序。2.1000萬字符串,其中有些是相同的(重復(fù),需要把重復(fù)的全部去掉,保留沒有重復(fù)的字符串。請問怎么設(shè)計(jì)和實(shí)現(xiàn)?3.尋找熱門查詢:查詢串的重復(fù)度比較高,雖然總數(shù)是1千萬,但如果除去重復(fù)后,不超過3百萬個(gè),每個(gè)不超過255字節(jié)。10.分布式處理 mapreduce適用范圍:數(shù)據(jù)量大,但是數(shù)據(jù)種類小可以放入內(nèi)存基本原理及要點(diǎn):將數(shù)據(jù)交給不同的

14、機(jī)器去處理,數(shù)據(jù)劃分,結(jié)果歸約。擴(kuò)展:問題實(shí)例:1.The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents: void map(String name, String document: / name: document name / document: document contents for each word w in document: EmitIntermediate(w, 1;

15、void reduce(String word, Iterator partialCounts: / key: a word / values: a list of aggregated partial counts int result = 0; for each v in partialCounts: result += ParseInt(v; Emit(result; Here, each document is split in words, and each word is counted initially with a “1 value by the Map function,

16、using the word as the result key. The framework puts together all the pairs with the same key and feeds them to the same call to Reduce, thus this function just needs to sum all of its input values to find the total appearances of that word. 2.海量數(shù)據(jù)分布在 100 臺(tái)電腦中，想個(gè)辦法高效統(tǒng)計(jì)出這批數(shù)據(jù)的 TOP10。 3.一共有 N 個(gè)機(jī)器，每個(gè)機(jī)器上有 N 個(gè)數(shù)。每個(gè)機(jī)器最多存 O(N個(gè)數(shù)并對它們 操作。