轉(zhuǎn)自http://blog.csdn.net/v_july_v/article/details/7382693
題目為十道海量處理面試題和十個大方法總結(jié)（突然回過神來廊营，這是july的博文幌绍，想起來自己還參加過他辦的機器學(xué)習(xí)班）
方法模式論--解決方法的抽象總結(jié)：
海量數(shù)據(jù)處理包括：海量數(shù)據(jù)上的存儲、處理铸豁、操作。海量數(shù)據(jù)--由于數(shù)據(jù)量太大，無法短時間內(nèi)完成移国，無法一次性載入內(nèi)存。
解決方法：巧妙的算法+合適的數(shù)據(jù)結(jié)構(gòu)荷逞。如Bloom filter/Hash/bit-map/堆/數(shù)據(jù)庫或倒排索引/trie樹媒咳，針對空間，無非就一個辦法：大而化小种远，分而治之（hash映射）涩澡，你不是說規(guī)模太大嘛，那簡單啊坠敷，就把規(guī)模大化為規(guī)模小的妙同，各個擊破不就完了嘛。進而使用集群替代單機膝迎，實現(xiàn)分布式并行計算粥帚。
理海量數(shù)據(jù)問題，無非就是：
1. 分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序限次；
2. 雙層桶劃分
3. Bloom filter/Bitmap芒涡；
4. Trie樹/數(shù)據(jù)庫/倒排索引；
5. 外排序掂恕；
6. 分布式處理之Hadoop/Mapreduce拖陆。
第一部分、從set/map談到hashtable/hash_map/hash_set
一般來說STL容器一般分為兩類：
1. 序列式容器（vector | List | deque | stack | queue| heap）
2. 關(guān)聯(lián)式容器（set集合和map映射表-->multiset和multimap這些容器均以RB-tree完成）第三類關(guān)聯(lián)式容器hashtable（散列表--以hashtable為底層機制hashset懊亡，hashmap...）
非關(guān)聯(lián)式數(shù)據(jù)庫：比如MongoDB依啰，文檔（document）是最基本的組織形式，每個文檔也是以key-value的方式組織起來店枣。一個文檔可以有多個key-value組合速警，每個value可以是不同類型
set/map/multiset/multimap
set同map一樣，所有元素都會根據(jù)元素的鍵值自動被排序鸯两，因為set/map兩者的所有操作闷旧，都是調(diào)用RB-tree的操作行為。都不允許元素有相同的鍵值
區(qū)別：
set的元素不像map同時擁有鍵和值钧唐，set元素的鍵值就是實值忙灼，實值就是鍵值
而map所有的元素都是成對出現(xiàn)，同時擁有key和value
至于multiset和multimap特性與用法和set/map相同钝侠，唯一差別就是它們允許鍵值重復(fù)该园，所有的操作都是基于RB_tree的insert_equal()而非inset_unique()
hash_set/hash_map/hash_multiset/hash_multimap
hashset/hashmap，兩者的一切操作都是基于hashtable之上帅韧。不同的是里初，hashset同set一樣，同時擁有實值和鍵值忽舟，hashmap同map一樣每個元素同時擁有一個實值和鍵值双妨，但都是因為基于hashtable所以不具有自動排序功能淮阐。
關(guān)于hash |?關(guān)于紅黑樹?| hashmap的應(yīng)用?| hashset的應(yīng)用
處理海量數(shù)據(jù)之6把秘密鑰匙
1、海量日志數(shù)據(jù)刁品，提取出某日訪問百度次數(shù)最多的那個IP
既然是海量數(shù)據(jù)處理泣特，那么可想而知，給我們的數(shù)據(jù)那就一定是海量的挑随。針對這個數(shù)據(jù)的海量群扶，我們?nèi)绾沃帜?對的，無非就是分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序镀裤。先映射，后統(tǒng)計缴饭，最后排序：
1） 分而治之 | hash映射：針對數(shù)據(jù)量太大暑劝，內(nèi)存受限，只能是把大文件（取模映射）成小文件：大而化小颗搂，各個擊破担猛，縮小規(guī)模，逐個解決
2） hashmap統(tǒng)計：當大文件轉(zhuǎn)化成了小文件丢氢，那么我們便采取常規(guī)的haspmap（ip傅联，count）來進行頻率統(tǒng)計
3）堆/快速排序：統(tǒng)計完了之后，采用堆排序疚察，得到次數(shù)最多的ip
解：首先得到這一天的日志蒸走，將訪問百度的ip提取出來，逐個寫入到一個大文件中貌嫡。注意到ip是32位的比驻，最多有2^32個ip。采用映射的方法岛抄，比如%1000别惦，將大文件映射到1000個小文件中，再找出每個小文件中出現(xiàn)頻率最大的ip（使用hashmap對ip出現(xiàn)的頻率進行統(tǒng)計）夫椭。最后使用堆排序進行排序掸掸，得到出現(xiàn)次數(shù)最多的ip
關(guān)于本題，還有如下幾個問題：
（1）hash取模是一種等價映射蹭秋，不會存在同一個元素分散到不同小文件中的情況扰付。那么相同ip只能落在同一個小文件中。因此如果兩個ip相等感凤，那么經(jīng)過hash（ip）后值也必然相同悯周。
（2） 到底什么是hash映射？簡單來說就是為了便于計算機在有限的內(nèi)存中處理大數(shù)據(jù)陪竿，從而通過一種映射散列的方式讓數(shù)據(jù)均勻地分布在對應(yīng)的內(nèi)存位置（比如大文件映射成小文件）禽翼，而這個散列方式就是我們說的hash函數(shù)
2屠橄、尋找熱門查詢，300萬個查詢字符串中統(tǒng)計最熱門的10個查詢（微博熱搜）
原題：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來闰挡，每個查詢串的長度為1-255字節(jié)锐墙。假設(shè)目前有一千萬個記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬长酗，但如果除去重復(fù)后溪北，不超過3百萬個。一個查詢串的重復(fù)度越高夺脾，說明查詢它的用戶越多之拨，也就是越熱門），請你統(tǒng)計最熱門的10個查詢串咧叭，要求使用的內(nèi)存不能超過1G蚀乔。
解：根據(jù)上面的第一題，我們知道一億個ip地址太大菲茬，無法一次性載入內(nèi)存吉挣，因此我們需要散列。但如果數(shù)據(jù)規(guī)模比較小婉弹，能夠一次性載入內(nèi)存呢睬魂？雖然有1千萬個查詢，但是由于重復(fù)次數(shù)比較高镀赌，事實上只有300w的查詢氯哮，每個查詢255byte，假設(shè)將它們都載入內(nèi)存(300w假設(shè)沒有重復(fù)佩脊，都是最大長度蛙粘，那么最多占用內(nèi)存3M*1k/4 = 0.75G)，所以現(xiàn)在需要一個合適的數(shù)據(jù)結(jié)構(gòu)威彰，hashtable絕對是最優(yōu)選擇出牧。
所以這道題不用映射，直接hash統(tǒng)計歇盼，然后排序舔痕。對于此類經(jīng)典的topK問題，采取的對策是hashmap+堆：
1) hashMap統(tǒng)計：先對這批海量數(shù)據(jù)進行預(yù)處理豹缀。具體方法是維護一個key為query字段伯复，value為該字段出現(xiàn)次數(shù)的hashtable。每次讀取一個query邢笙，如果該字符串不在table中啸如，那么加入該字符串，并且將value設(shè)為1氮惯，如果該字符串在table中那么該子串計數(shù)+1叮雳。時間復(fù)雜度O(N)
2）堆排序：第二步想暗、借助堆這個數(shù)據(jù)結(jié)構(gòu)，找出Top K帘不，時間復(fù)雜度為N‘logK说莫。即借助堆結(jié)構(gòu)，我們可以在log量級的時間內(nèi)查找和調(diào)整/移動寞焙。因此储狭，維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query捣郊，分別和根元素進行對比辽狈。所以，我們最終的時間復(fù)雜度是：O（N） + N' * O（logK）呛牲，（N為1000萬稻艰，N’為300萬）。
別忘了這篇文章中所述的堆排序思路：“維護k個元素的最小堆侈净，即用容量為k的最小堆存儲最先遍歷到的k個數(shù)，并假設(shè)它們即是最大的k個數(shù)僧凤，建堆費時O（k）畜侦，并調(diào)整堆(費時O（logk）)后，有k1>k2>...kmin（kmin設(shè)為小頂堆中最小元素）躯保。繼續(xù)遍歷數(shù)列旋膳，每次遍歷一個元素x，與堆頂元素比較途事，若x>kmin验懊，則更新堆（x入堆，用時logk）尸变，否則不更新堆义图。這樣下來，總費時O（k*logk+（n-k）*logk）=O（n*logk）召烂。此方法得益于在堆中碱工，查找等各項操作時間復(fù)雜度均為logk∽喾颍”--Top K算法問題的實現(xiàn)怕篷。
3、有一個1G大小的一個文件酗昼，里面每一行是一個詞廊谓，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M麻削。返回頻數(shù)最高的100個詞蒸痹。
解：分析春弥，此題的問題關(guān)鍵是文件很大，內(nèi)存受限电抚。
1）hash映射：順序讀文件惕稻，對于每個詞，取%5000蝙叛，存到5000個小文件中俺祠，每個文件大概是200k左右，如果有文件大小超過1m借帘，繼續(xù)按類似方法往下分蜘渣，直到所以文件大小不超過1m
2）hashmap統(tǒng)計：對于每個文件采用trie樹/hashmap統(tǒng)計每個詞，及其出現(xiàn)的頻率肺然。
3）堆/歸并排序：取出現(xiàn)頻率最大的100個詞（含100個節(jié)點的最小堆）蔫缸，再把100個詞及對應(yīng)的頻率存入文件，這樣又得到5000個文件际起，最后再把5000個文件歸并
4拾碌、海量數(shù)據(jù)分布在100臺電腦中，想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10街望。
如果每個元素只出現(xiàn)一次校翔，而且只出現(xiàn)在某一臺機器中，那么采取下面步驟統(tǒng)計top10
1. 堆排序：在每臺電腦上求出Top10灾前。包含10個元素的堆（top10小防症，用大項堆，top10大哎甲。比如求top10大蔫敲，我們首先取出前十個元素調(diào)整成最小堆，如果發(fā)現(xiàn)后面掃描的元素比根元素大炭玫，則用該元素替換根元素最后再調(diào)整最小堆）
2. 求出每臺電腦上的top10后奈嘿，然后把100臺電腦上的top10組合起來，共1000個數(shù)據(jù)吞加，繼續(xù)按照方法1排序
如果同一個元素重復(fù)出現(xiàn)在不同電腦指么？
這種情況下有兩種方法：遍歷一遍所有數(shù)據(jù)，重新hash取模榴鼎，使得同一個數(shù)據(jù)只出現(xiàn)在同一臺電腦中伯诬，然后按照上述方法處理。
或者暴力求解巫财，統(tǒng)計出所有元素的出現(xiàn)次數(shù)盗似，把不同機器的出現(xiàn)次數(shù)相加，統(tǒng)一求解
5平项、有10個文件赫舒，每個文件1G悍及，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)接癌。要求你按照query的頻度排序心赶。
方法1：直接上
1）hash映射：順序讀取10個文件，按照hash（query）%10將query結(jié)果寫入另外10個文件缺猛，這樣新生成的文件每個的大小也約為1G
2） hashmap統(tǒng)計找一臺內(nèi)存在2G左右的機器缨叫，依次來統(tǒng)計每個query出現(xiàn)的次數(shù)
3）堆/快速/歸并排序：按照出現(xiàn)的次數(shù)進行排序，這樣得到10個排好序的文件荔燎，最后將10個文件歸并
rbtree PK hashtable
據(jù)朋友№邦卡貓№的做的紅黑樹和hash table的性能測試中發(fā)現(xiàn)：當數(shù)據(jù)量基本上int型key時耻姥，hash?table是rbtree的3-4倍，但hash?table一般會浪費大概一半內(nèi)存有咨。
因為hash table所做的運算就是個%琐簇，而rbtree要比較很多，比如rbtree要看value的數(shù)據(jù) 座享，每個節(jié)點要多出3個指針（或者偏移量） 如果需要其他功能婉商，比如，統(tǒng)計某個范圍內(nèi)的key的數(shù)量渣叛，就需要加一個計數(shù)成員据某。
且1s rbtree能進行大概50w+次插入，hash table大概是差不多200w次诗箍。不過很多的時候，其速度可以忍了挽唉，例如倒排索引差不多也是這個速度滤祖，而且單線程，且倒排表的拉鏈長度不會太大瓶籽。正因為基于樹的實現(xiàn)其實不比hashtable慢到哪里去匠童，所以數(shù)據(jù)庫的索引一般都是用的B/B+樹，而且B+樹還對磁盤友好(B樹能有效降低它的高度塑顺，所以減少磁盤交互次數(shù))汤求。比如現(xiàn)在非常流行的NoSQL數(shù)據(jù)庫，像MongoDB也是采用的B樹索引严拒。關(guān)于B樹系列扬绪，請參考本blog內(nèi)此篇文章：從B樹、B+樹裤唠、B*樹談到R 樹挤牛。更多請待后續(xù)實驗論證。
密匙二种蘸、多層劃分
適用范圍：第k大墓赴，中位數(shù)竞膳，不重復(fù)或重復(fù)的數(shù)字
基本原理及要點：因為元素范圍很大，不能利用直接尋址表诫硕，所以通過多次劃分坦辟，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行章办。
13锉走、2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)纲菌。
有點像鴿巢原理挠日，整數(shù)個數(shù)為2^32,也就是，我們可以將這2^32個數(shù)翰舌，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)嚣潜，然后將數(shù)據(jù)分離到不同的區(qū)域刁岸，然后不同的區(qū)域在利用bitmap就可以直接解決了缚陷。也就是說只要有足夠的磁盤空間毅舆，就可以很方便的解決鹿鳖。
14宇葱、5億個int找它們的中位數(shù)吻谋。
思路一：這個例子比上面那個更明顯妻导。首先我們將int劃分為2^16個區(qū)域嗤瞎，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)山橄，之后我們根據(jù)統(tǒng)計結(jié)果就可以判斷中位數(shù)落到那個區(qū)域垮媒，同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了航棱。
實際上睡雇，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度饮醇。即可以先將int64分成2^24個區(qū)域它抱，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成2^20個子區(qū)域朴艰，然后確定是子區(qū)域的第幾大數(shù)观蓄，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進行統(tǒng)計了祠墅。
密匙三：Bloom filter/Bitmap
Bloom filter
關(guān)于什么是Bloom filter侮穿，請參看blog內(nèi)此文：
海量數(shù)據(jù)處理之Bloom Filter詳解
適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重毁嗦，或者集合求交集
基本原理及要點：
對于原理來說很簡單撮珠，位數(shù)組+k個獨立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在芯急，很明顯這個過程并不保證查找的結(jié)果是100%正確的勺届。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字娶耍。所以一個簡單的改進就是 counting Bloom filter免姿，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了榕酒。
還有一個比較重要的問題胚膊，如何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)想鹰。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小紊婉。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合辑舷。但m還應(yīng)該更大些喻犁，因為還要保證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ù)為單位(準確的說是不同元素的個數(shù))谷婆。通常單個元素的長度都是有很多bit的慨蛙。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。
密匙四纪挎、Trie樹/數(shù)據(jù)庫/倒排索引
適用范圍：數(shù)據(jù)量大期贫，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存
基本原理及要點：實現(xiàn)方式廷区，節(jié)點孩子的表示方式
擴展：壓縮實現(xiàn)。
關(guān)于數(shù)據(jù)庫中的算法
關(guān)于數(shù)據(jù)庫索引及其優(yōu)化贾铝，更多可參見此文：http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html隙轻；
關(guān)于MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理，這里還有一篇很好的文章：http://blog.codinglabs.org/articles/theory-of-mysql-index.html垢揩；
關(guān)于B 樹玖绿、B+ 樹、B* 樹及R 樹叁巨，本blog內(nèi)有篇絕佳文章：http://blog.csdn.net/v_JULY_v/article/details/6530142斑匪。
密匙五、外排序
適用范圍：大數(shù)據(jù)的排序锋勺，去重
基本原理及要點：外排序的歸并方法蚀瘸，置換選擇敗者樹原理狡蝶，最優(yōu)歸并樹
問題實例：
1).有一個1G大小的一個文件，里面每一行是一個詞贮勃，詞的大小不超過16個字節(jié)贪惹，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞寂嘉。
這個數(shù)據(jù)具有很明顯的特點奏瞬，詞的大小為16個字節(jié)，但是內(nèi)存只有1M做hash明顯不夠泉孩，所以可以用來排序硼端。內(nèi)存可以當輸入緩沖區(qū)使用。
關(guān)于多路歸并算法及外排序的具體應(yīng)用場景寓搬，請參見blog內(nèi)此文：
第十章珍昨、如何給10^7個數(shù)據(jù)量的磁盤文件排序
密匙六、分布式處理之Mapreduce
MapReduce是一種計算模型订咸，簡單的說就是將大批量的工作（數(shù)據(jù)）分解（MAP）執(zhí)行曼尊，然后再將結(jié)果合并成最終結(jié)果（REDUCE）。這樣做的好處是可以在任務(wù)被分解后脏嚷，可以通過大量機器進行并行計算骆撇，減少整個操作的時間。但如果你要我再通俗點介紹父叙，那么神郊，說白了，Mapreduce的原理就是一個歸并排序趾唱。
適用范圍：數(shù)據(jù)量大涌乳，但是數(shù)據(jù)種類小可以放入內(nèi)存
基本原理及要點：將數(shù)據(jù)交給不同的機器去處理，數(shù)據(jù)劃分甜癞，結(jié)果歸約夕晓。問題實例：
The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
海量數(shù)據(jù)分布在100臺電腦中，想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10悠咱。
一共有N個機器蒸辆，每個機器上有N個數(shù)。每個機器最多存O(N)個數(shù)并對它們操作析既。如何找到N^2個數(shù)的中數(shù)(median)躬贡？
更多具體闡述請參見blog內(nèi)：
