海量处理面试题
轉自：http://www.cnblogs.com/sooner/archive/2013/08/18/3266545.html
?
何謂海量數據處理？
?? 所謂海量數據處理，其實很簡單，海量，海量，何謂海量，就是數據量太大，所以導致要么是無法在較短時間內迅速解決，要么是數據太大，導致無法一次性裝入內存。
??? 那解決辦法呢?針對時間，我們可以采用巧妙的算法搭配合適的數據結構，如Bloom filter/Hash/bit-map/堆/數據庫或倒排索引/trie/，針對空間，無非就一個辦法：大而化小：分而治之/hash映射，你不是說規模太大嘛，那簡單啊，就把規模大化為規模小的，各個擊破不就完了嘛。
??? 至于所謂的單機及集群問題，通俗點來講，單機就是處理裝載數據的機器有限(只要考慮cpu，內存，硬盤的數據交互)，而集群，機器有多輛，適合分布式處理，并行計算(更多考慮節點和節點間的數據交互)。
??? 再者，通過本blog內的有關海量數據處理的文章，我們已經大致知道，處理海量數據問題，無非就是：
下面，本文第一部分、從set/map談到hashtable/hash_map/hash_set，簡要介紹下set/map/multiset/multimap，及hash_set/hash_map/hash_multiset/hash_multimap之區別(萬丈高樓平地起，基礎最重要)，而本文第二部分，則針對上述那6種方法模式結合對應的海量數據處理面試題分別具體闡述
第一部分、從set/map談到hashtable/hash_map/hash_set
? ? 稍后本文第二部分中將多次提到hash_map/hash_set，下面稍稍介紹下這些容器，以作為基礎準備。一般來說，STL容器分兩種，
- 序列式容器(vector/list/deque/stack/queue/heap)，
- 關聯式容器。關聯式容器又分為set(集合)和map(映射表)兩大類，以及這兩大類的衍生體multiset(多鍵集合)和multimap(多鍵映射表)，這些容器均以RB-tree完成。此外，還有第3類關聯式容器，如hashtable(散列表)，以及以hashtable為底層機制完成的hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列多鍵集合)/hash_multimap(散列多鍵映射表)。也就是說，set/map/multiset/multimap都內含一個RB-tree，而hash_set/hash_map/hash_multiset/hash_multimap都內含一個hashtable。
? ? 所謂關聯式容器，類似關聯式數據庫，每筆數據或每個元素都有一個鍵值(key)和一個實值(value)，即所謂的Key-Value(鍵-值對)。當元素被插入到關聯式容器中時，容器內部結構(RB-tree/hashtable)便依照其鍵值大小，以某種特定規則將這個元素放置于適當位置。
? ? ?包括在非關聯式數據庫中，比如，在MongoDB內，文檔(document)是最基本的數據組織形式，每個文檔也是以Key-Value（鍵-值對）的方式組織起來。一個文檔可以有多個Key-Value組合，每個Value可以是不同的類型，比如String、Integer、List等等。?
{ "name" : "July", ?
??"sex" : "male", ?
? ?"age" : 23 } ?
set/map/multiset/multimap
? ? set，同map一樣，所有元素都會根據元素的鍵值自動被排序，因為set/map兩者的所有各種操作，都只是轉而調用RB-tree的操作行為，不過，值得注意的是，兩者都不允許兩個元素有相同的鍵值。
? ? 不同的是：set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，而map的所有元素都是pair，同時擁有實值(value)和鍵值(key)，pair的第一個元素被視為鍵值，第二個元素被視為實值。
? ? 至于multiset/multimap，他們的特性及用法和set/map完全相同，唯一的差別就在于它們允許鍵值重復，即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。
hash_set/hash_map/hash_multiset/hash_multimap
? ? hash_set/hash_map，兩者的一切操作都是基于hashtable之上。不同的是，hash_set同set一樣，同時擁有實值和鍵值，且實質就是鍵值，鍵值就是實值，而hash_map同map一樣，每一個元素同時擁有一個實值(value)和一個鍵值(key)，所以其使用方式，和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具備自動排序功能。為什么?因為hashtable沒有自動排序功能。
? ? 至于hash_multiset/hash_multimap的特性與上面的multiset/multimap完全相同，唯一的差別就是它們hash_multiset/hash_multimap的底層實現機制是hashtable(而multiset/multimap，上面說了，底層實現機制是RB-tree)，所以它們的元素都不會被自動排序，不過也都允許鍵值重復。
? ? 所以，綜上，說白了，什么樣的結構決定其什么樣的性質，因為set/map/multiset/multimap都是基于RB-tree之上，所以有自動排序功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自動排序功能，至于加個前綴multi_無非就是允許鍵值重復而已。
? ? 此外，
- 關于什么hash，請看blog內此篇文章：http://blog.csdn.net/v_JULY_v/article/details/6256463；
- 關于紅黑樹，請參看blog內系列文章：http://blog.csdn.net/v_july_v/article/category/774945，
- 關于hash_map的具體應用：http://blog.csdn.net/sdhongjun/article/details/4517325，關于hash_set：http://blog.csdn.net/morewindows/article/details/7330323。
? ? OK，接下來，請看本文第二部分、處理海量數據問題之六把密匙。
第二部分、處理海量數據問題之六把密匙
密匙一、分而治之/Hash映射 + Hash統計 + 堆/快速/歸并排序
1、海量日志數據，提取出某日訪問百度次數最多的那個IP。
首先是這一天，并且是訪問百度的日志中的IP取出來，逐個寫入到一個大文件中。注意到IP是32位的，最多有個2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大文件映射為1000個小文件，再找出每個小文中出現頻率最大的IP（可以采用hash_map進行頻率統計，然后再找出頻率最大的幾個）及相應的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。或者如下闡述（雪域之鷹）：
算法思想：分而治之+Hash
1.IP地址最多有2^32=4G種取值情況，所以不能完全加載到內存中處理；
2.可以考慮采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分別存儲到1024個小文件中。這樣，每個小文件最多包含4MB個IP地址；
3.對于每一個小文件，可以構建一個IP為key，出現次數為value的Hash_map，同時記錄當前出現次數最多的那個IP地址；
4.可以得到1024個小文件中的出現次數最多的IP，再依據常規的排序算法得到總體上出現次數最多的IP；
分析：有的網友提出以下疑問：我感覺這個值不應該是要求的那個。因為可能某一個ip在某一個小文件中可能出現頻率很高，但是在其他小文件中可能沒出現幾次，即分布不均，但因為某一個小文件中特別多而被選出來了；而另一個ip可能在每個小文件中都不是出現最多的，但是它在每個文件中都出現很多次，即分布均勻，因此非常有可能它就是總的出現次數最多的，但是因為在每個小文件中出現的次數都不是最多的而被刷掉了。所以我感覺上面的方案不行。
這就考慮到“分而治之”中的“分”到底怎么分。。在第二步中我們提到按照IP地址的Hash(IP)%1024的值，將海量IP日志分別存儲到1024個小文件中。。這樣就會致使相似的IP或者同一IP被分到同一小文件中。。滿足分而治之的要求。。故不存在分布均勻情況。。
還有一位網友給出了具體的方法：計數法（原理同上：分而治之）
? ? ? 假設一天之內某個IP訪問百度的次數不超過40億次,則訪問次數可以用unsigned表示.用數組統計出每個IP地址出現的次數, 即可得到訪問次數最大的IP地址。
? ? ? IP地址是32位的二進制數,所以共有N=2^32=4G個不同的IP地址, 創建一個unsigned count[N];的數組,即可統計出每個IP的訪問次數,而sizeof(count) == 4G*4=16G, 遠遠超過了32位計算機所支持的內存大小,因此不能直接創建這個數組.下面采用劃分法解決這個問題.
? ? ? 假設允許使用的內存是512M, 512M/4=128M 即512M內存可以統計128M個不同的IP地址的訪問次數.而N/128M =4G/128M = 32 ,所以只要把IP地址劃分成32個不同的區間,分別統計出每個區間中訪問次數最大的IP, 然后就可以計算出所有IP地址中訪問次數最大的IP了.
? ? ? 因為2^5=32, 所以可以把IP地址的最高5位作為區間編號, 剩下的27為作為區間內的值,建立32個臨時文件,代表32個區間,把相同區間的IP地址保存到同一的臨時文件中.
? ? ? 例如:
? ? ? ip1=0x1f4e2342
? ? ? ip1的高5位是id1 = ip1 >>27 = 0x11 = 3
? ? ? ip1的其余27位是value1 = ip1 &0x07ffffff = 0x074e2342
? ? ? 所以把 value1 保存在tmp3文件中。
? ? ? 由id1和value1可以還原成ip1, 即 ip1 =(id1<<27)|value1
? ? ? 按照上面的方法可以得到32個臨時文件,每個臨時文件中的IP地址的取值范圍屬于[0-128M),因此可以統計出每個IP地址的訪問次數.從而找到訪問次數最大的IP地址
? ? ? 程序源碼:
運行結果：
2、尋找熱門查詢
搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄，這些查詢串的重復讀比較?高，雖然總數是1千萬，但是如果去除重復和，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就越熱門。請你統計最熱門的10個查詢?串，要求使用的內存不能超過1G。?
(1)?請描述你解決這個問題的思路；?
(2)?請給出主要的處理流程，算法，以及算法的復雜度。
方案一：
分析：此問題的解決分為以下倆個步驟：
第一步：Query統計
Query統計有以下倆個方法，可供選擇：
1）、直接排序法
首先我們最先想到的的算法就是排序了，首先對這個日志里面的所有Query都進行排序，然后再遍歷排好序的Query，統計每個Query出現的次數了。
但是題目中有明確要求，那就是內存不能超過1G，一千萬條記錄，每條記錄是255Byte，很顯然要占據2.375G內存，這個條件就不滿足要求了。
讓我們回憶一下數據結構課程上的內容，當數據量比較大而且內存無法裝下的時候，我們可以采用外排序的方法來進行排序，這里我們可以采用歸并排序，因為歸并排序有一個比較好的時間復雜度O(NlgN)。
排完序之后我們再對已經有序的Query文件進行遍歷，統計每個Query出現的次數，再次寫入文件中。
綜合分析一下，排序的時間復雜度是O(NlgN)，而遍歷的時間復雜度是O(N)，因此該算法的總體時間復雜度就是O(N+NlgN)=O（NlgN）。?
2）、Hash Table法
在第1個方法中，我們采用了排序的辦法來統計每個Query出現的次數，時間復雜度是NlgN，那么能不能有更好的方法來存儲，而時間復雜度更低呢？
題目中說明了，雖然有一千萬個Query，但是由于重復度比較高，因此事實上只有300萬的Query，每個Query255Byte，因此我們可以考慮把他們都放進內存中去，而現在只是需要一個合適的數據結構，在這里，Hash Table絕對是我們優先的選擇，因為Hash Table的查詢速度非常的快，幾乎是O(1)的時間復雜度。
那么，我們的算法就有了：維護一個Key為Query字串，Value為該Query出現次數的HashTable，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并且將Value值設為1；如果該字串在Table中，那么將該字串的計數加一即可。最終我們在O(N)的時間復雜度內完成了對該海量數據的處理。
本方法相比算法1：在時間復雜度上提高了一個數量級，為O（N），但不僅僅是時間復雜度上的優化，該方法只需要IO數據文件一次，而算法1的IO次數較多的，因此該算法2比算法1在工程上有更好的可操作性。
第二步：找出Top 10
算法一：普通排序
我想對于排序算法大家都已經不陌生了，這里不在贅述，我們要注意的是排序算法的時間復雜度是NlgN，在本題目中，三百萬條記錄，用1G內存是可以存下的。
算法二：部分排序
題目要求是求出Top 10，因此我們沒有必要對所有的Query都進行排序，我們只需要維護一個10個大小的數組，初始化放入10個Query，按照每個Query的統計次數由大到小排序，然后遍歷這300萬條記錄，每讀一條記錄就和數組最小一個Query對比，如果小于這個Query，那么繼續遍歷，否則，將數組中最后一條數據淘汰，加入當前的Query（并尋找最小元素）。最后當所有的數據都遍歷完畢之后，那么這個數組中的10個Query便是我們要找的Top10了。
不難分析出，這樣，算法的最壞時間復雜度是N*K， 其中K是指top多少。
算法三：堆
在算法二中，我們已經將時間復雜度由NlogN優化到NK，不得不說這是一個比較大的改進了，可是有沒有更好的辦法呢？
分析一下，在算法二中，每次比較完成之后，需要的操作復雜度都是K，因為要把元素插入到一個線性表之中，而且采用的是順序比較。這里我們注意一下，該數組是有序的，一次我們每次查找的時候可以采用二分的方法查找，這樣操作的復雜度就降到了logK，可是，隨之而來的問題就是數據移動，因為移動數據次數增多了。不過，這個算法還是比算法二有了改進。
基于以上的分析，我們想想，有沒有一種既能快速查找，又能快速移動元素的數據結構呢？回答是肯定的，那就是堆。
借助堆結構，我們可以在log量級的時間內查找和調整/移動。因此到這里，我們的算法可以改進為這樣，維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進行對比。
思想與上述算法二一致，只是算法在算法三，我們采用了最小堆這種數據結構代替數組，把查找目標元素的時間復雜度有O（K）降到了O（logK）。
那么這樣，采用堆數據結構，算法三，最終的時間復雜度就降到了N‘logK，和算法二相比，又有了比較大的改進。
總結：
至此，算法就完全結束了，經過上述第一步、先用Hash表統計每個Query出現的次數，O（N）；然后第二步、采用堆數據結構找出Top 10，N*O（logK）。所以，我們最終的時間復雜度是：O（N） + N'*O（logK）。（N為1000萬，N’為300萬）。
方案二：采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最后用10個元素的最小推來對出現頻率進行排序。
3、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。
分而治之 + hash統計 + 堆/快速排序這個套路，我們已經開始有了屢試不爽的感覺。下面，再拿幾道再多多驗證下。請看此第3題：又是文件很大，又是內存受限，咋辦?還能怎么辦呢?無非還是：
讀者反饋@ylqndscylq：本文評論下，有讀者ylqndscylq反應：每個小文件取前100會有問題。是否真如此，咱們先且看下一道題，第4題(稍后，我們將意識到，這第3題給出的算法有問題)。
有網友提出：呵呵
普通解法:分治，hash，歸并，最大（小）堆，map reducer等算法，你的小內存導致了只能用時間換空間的做法， 比如多次的遍歷，big set分裂成小set，使用磁盤索引等。
2B解法： lucene
文藝解法（ibm研究院提供）：基于priori algorithm.
http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf
4、一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。
? ? ?方案1：這題是考慮時間效率。用trie樹統計每個詞出現的次數，時間復雜度是O(n*le)（le表示單詞的平準長度）。然后是找出出現最頻繁的前10個詞，可以用堆來實現，前面的題中已經講到了，時間復雜度是O(n*lg10)。所以總的時間復雜度，是O(n*le)與O(n*lg10)中較大的哪一個。
5、海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10（最大數）。 此題與上面第3題類似，方案1：在前面的題中，我們已經提到了，用一個含100個元素的最小堆完成。復雜度為O(100w*lg100)。
方案2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比100多的時候，采用傳統排序算法排序，取前100個。復雜度為O(100w*100)。
算法如下：根據快速排序劃分的思想
(1) 先對所有數據分成[a,b）b（b,d]兩個區間，(b,d]區間內的數都是大于[a,b)區間內的數
(2) 對(b,d]重復(1)操作，直到最右邊的區間個數小于100個。注意[a,b)區間不用劃分
(3) 向左邊的第一個區間取前100-n.n為已取出的元素個數。方法仍然是對其劃分，取[c,d]區間。如果個數不夠，繼續(3)操作
(4) 有必要的話，對取出的100個數進行快速排序。over~
方案3：采用局部淘汰法。選取前100個元素，并排序，記為序列L。然后一次掃描剩余的元素x，與排好序的100個元素中最小的元素比，如果比這個最小的要大，那么把這個最小的元素刪除，并把x利用插入排序的思想，插入到序列L中。依次循環，知道掃描了所有的元素。復雜度為O(100w*100)。
進一步：1億數據找出最大的1w個
1. 分塊法
解法：A.?采用分塊法，將1億數據分成100w一塊，共100塊。
?? ? ? ? ? ?B. 對每塊進行快速排序，分成兩堆，如果大堆大于1w個，則對大堆再次進行快速排序，直到小于等于1w停止
?? ? ? ? ? ??（假設此時大堆有N個），此時對小堆進行排序，取最大的10000-N個，這樣就找到了這100w中最大的1w個。
?? ? ? ? ? ?C.?100塊，每塊選出最大的1w，再對這100w使用同樣的方法，找出最大的1w個
2. Bit-Map
適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下
解法：用一個例子來說明吧，這樣直觀一點。
?? ? ? ? ? ?假設對7, 6, 3, 5這四個數進行排序，首先初始化一個byte，8位，可表示為0?0?0?0?0?0?0?0
?? ? ? ? ? ?對于7，將第七位置1，對剩下幾個數執行同樣操作，則最后該byte變為 0?0?1?0?1?1?1?0
?? ? ? ? ? ?最后一步，遍歷，將置1位的序號逐個輸出，即3，5， 6，7
3. 紅黑樹
解法：用一個紅黑樹維護這1w個數，然后遍歷其他數字，來替換紅黑樹中最小的數（這是在網上看到的算法，
?? ? ? ? ? ?我感覺用贏 者樹也是可以的）
如果數據中有重復，則對于Bit-Map，找出前1w個數，對這1w個數建立Hash Table，然后再次遍歷這一億個數，同時對Hash Table中的數字 計數，最后根據計數找出前1w個（包含重復）
7、有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求你按照query的頻度排序。? ?直接上：
??? 方案2：一般query的總量是有限的，只是重復的次數比較多而已，可能對于所有的query，一次性就可以加入到內存了。這樣，我們就可以采用trie樹/hash_map等直接來統計每個query出現的次數，然后按出現次數做快速/堆/歸并排序就可以了。
??? 方案3：與方案1類似，但在做完hash，分成多個文件后，可以交給多個文件來處理，采用分布式的架構來處理（比如MapReduce），最后再進行合并。
8、給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？??? 方案1：可以估計每個文件安的大小為50G×64=320G，遠遠大于內存限制的4G。所以不可能將其完全加載到內存中處理。考慮采取分而治之的方法。
??? 方案2：如果允許有一定的錯誤率，可以使用Bloom filter，4G內存大概可以表示340億bit。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應該是共同的url（注意會有一定的錯誤率）。
9、怎么在海量數據中找出重復次數最多的一個？
? ? 方案1：先做hash，然后求模映射為小文件，求出每個小文件中重復次數最多的一個，并記錄重復次數。然后找出上一步求出的數據中重復次數最多的一個就是所求（具體參考前面的題）。
10、上千萬或上億數據（有重復），統計其中出現次數最多的錢N個數據。
? ? 方案1：上千萬或上億的數據，現在的機器的內存應該能存下。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統計次數。然后就是取出前N個出現次數最多的數據了，可以用第2題提到的堆機制完成。
?
11、 1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。請怎么設計和實現？
- 方案1：這題用trie樹比較合適，hash_map也行。
? ? ? 首先映射為內存可以處理的n個小文件，這時相同的字符串肯定在同一個文件中，在每個小文件中使用hash_set取出重復的字符串，之后寫 ? 到一個文件中，依次處理n個文件，即可得到結果。。
- 方案2：from xjbzju:，1000w的數據規模插入操作完全不現實，以前試過在stl下100w元素插入set中已經慢得不能忍受，覺得基于hash的實現不會比紅黑樹好太多，使用vector+sort+unique都要可行許多，建議還是先hash成小文件分開處理再綜合。
- 1、hash_set在千萬級數據下，insert操作優于set? 這位blog：http://t.cn/zOibP7t?給的實踐數據可靠不??
- 2、那map和hash_map的性能比較呢? 誰做過相關實驗?
- 3、那查詢操作呢，如下段文字所述?
或者小數據量時用map，構造快，大數據量時用hash_map?
rbtree PK hashtable
? ? 據朋友№邦卡貓№的做的紅黑樹和hash table的性能測試中發現：當數據量基本上int型key時，hash?table是rbtree的3-4倍，但hash?table一般會浪費大概一半內存。
? ? 因為hash?table所做的運算就是個%，而rbtree要比較很多，比如rbtree要看value的數據 ，每個節點要多出3個指針（或者偏移量） 如果需要其他功能，比如，統計某個范圍內的key的數量，就需要加一個計數成員。
且1s?rbtree能進行大概50w+次插入，hash?table大概是差不多200w次。不過很多的時候，其速度可以忍了，例如倒排索引差不多也是這個速度，而且單線程，且倒排表的拉鏈長度不會太大。正因為基于樹的實現其實不比hashtable慢到哪里去，所以數據庫的索引一般都是用的B/B+樹，而且B+樹還對磁盤友好(B樹能有效降低它的高度，所以減少磁盤交互次數)。比如現在非常流行的NoSQL數據庫，像MongoDB也是采用的B樹索引。關于B樹系列，請參考本blog內此篇文章：從B樹、B+樹、B*樹談到R 樹。? ? OK，更多請待后續實驗論證。接下來，咱們來看第二種方法，雙層捅劃分。
密匙二、雙層桶劃分
雙層桶劃分----其實本質上還是分而治之的思想，重在“分”的技巧上！
適用范圍：第k大，中位數，不重復或重復的數字
基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子。
擴展：
問題實例：
11、2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。
除了用2-Bitmap來計數標記以外,也可以用兩個1-Bitmap來實現(如果考慮正負數的情況,就四個1-Bitmap)
12、5億個int找它們的中位數。
實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。
方法同基數排序有些像，開一個大小為65536的Int數組，第一遍讀取，統計Int32的高16位的情況，也就是0-65535，都算作0,65536 - 131071都算作1。就相當于用該數除以65536。Int32 除以 65536的結果不會超過65536種情況，因此開一個長度為65536的數組計數就可以。每讀取一個數，數組中對應的計數+1，考慮有負數的情況，需要將結果加32768后，記錄在相應的數組內。
第一遍統計之后，遍歷數組，逐個累加統計，看中位數處于哪個區間，比如處于區間k，那么0- k-1的區間里數字的數量sum應該<n/2（2.5億）。而k+1 - 65535的計數和也<n/2，第二遍統計同上面的方法類似，但這次只統計處于區間k的情況，也就是說(x / 65536) + 32768 = k。統計只統計低16位的情況。并且利用剛才統計的sum，比如sum = 2.49億，那么現在就是要在低16位里面找100萬個數(2.5億-2.49億)。這次計數之后，再統計一下，看中位數所處的區間，最后將高位和低位組合一下就是結果了。
密匙三：Bloom filter/Bitmap
Bloom filter
關于什么是Bloom filter，請參看blog內此文：
- 海量數據處理之Bloom Filter詳解
適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集
基本原理及要點：
對于原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。
還有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。
舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。
注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
擴展：
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。
13、給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？
根據這個問題我們來計算下內存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。
? ? 同時，上文的第5題：給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？如果允許有一定的錯誤率，可以使用Bloom filter，4G內存大概可以表示340億bit。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應該是共同的url（注意會有一定的錯誤率）。
Bitmap
- 關于什么是Bitmap，請看blog內此文第二部分：http://blog.csdn.net/v_july_v/article/details/6685962。
? ? 下面關于Bitmap的應用，直接上題，如下第9、10道：
????? 14/11題、在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數。
? ? 方案1：采用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需內存2^32 * 2 bit=1 GB內存，還可以接受。然后掃描這2.5億個整數，查看Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應位是01的整數輸出即可。
? ? 方案2：也可采用與第1題類似的方法，進行劃分小文件的方法。然后在小文件中找出不重復的整數，并排序。然后再進行歸并，注意去除重復的元素。
????? 15、騰訊面試題：給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？
? ? ? 第一反應時快速排序+二分查找。以下是其它更好的方法：? ?
? ? ? 方案1：frome oo，用位圖/Bitmap的方法，申請512M的內存，一個bit位代表一個unsigned int值。讀入40億個數，設置相應的bit位，讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在。
? ? ? 方案2：這個問題在《編程珠璣》里有很好的描述，大家可以參考下面的思路，探討一下：
又因為2^32為40億多，所以給定一個數可能在，也可能不在其中；
這里我們把40億個數中的每一個用32位的二進制來表示
假設這40億個數開始放在一個文件中。
然后將這40億個數分成兩類:
1.最高位為0
2.最高位為1
并將這兩類分別寫入到兩個文件中，其中一個文件中數的個數<=20億，而另一個>=20億（這相當于折半了）；
與要查找的數的最高位比較并接著進入相應的文件再查找
再然后把這個文件為又分成兩類:
1.次最高位為0
2.次最高位為1
并將這兩類分別寫入到兩個文件中，其中一個文件中數的個數<=10億，而另一個>=10億（這相當于折半了）；
與要查找的數的次最高位比較并接著進入相應的文件再查找。
…….
以此類推，就可以找到了,而且時間復雜度為O(logn)，方案2完。
16、給40億個unsigned int的整數，如何判斷這40億個數中哪些數重復？
? ? ? ?同理，可以申請512M的內存空間，然后讀取40億個整數，并且將相應的bit位置1。如果是第一次讀取某個數據，則在將該bit位置1之前，此bit位必定是0；如果是第二次讀取該數據，則可根據相應的bit位是否為1判斷該數據是否重復。
附：這里，再簡單介紹下，位圖方法：
使用位圖法判斷整形數組是否存在重復
判斷集合中存在重復是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。
位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然后再次掃描原數組，遇到幾就給新數組的第幾位置上 1，如遇到5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重復。這 種給新數組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效 率還能提高一倍。
密匙四、Trie樹/數據庫/倒排索引
Trie樹
適用范圍：數據量大，重復多，但是數據種類小可以放入內存
基本原理及要點：實現方式，節點孩子的表示方式
擴展：壓縮實現。
問題實例：
? ? 更多有關Trie樹的介紹，請參見此文：從Trie樹（字典樹）談到后綴樹。
數據庫索引
適用范圍：大數據量的增刪改查
基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。
- 關于數據庫索引及其優化，更多可參見此文：http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html；
- 關于MySQL索引背后的數據結構及算法原理，這里還有一篇很好的文章：http://www.codinglabs.org/html/theory-of-mysql-index.html；
- 關于B 樹、B+ 樹、B* 樹及R 樹，本blog內有篇絕佳文章：http://blog.csdn.net/v_JULY_v/article/details/6530142。
倒排索引(Inverted index)
適用范圍：搜索引擎，關鍵字查詢
基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。
以英文為例，下面是要被索引的文本：
????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"將對應集合的交集。
正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關系。
擴展：
問題實例：文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。
? ? 關于倒排索引的應用，更多請參見：
- 第二十三、四章：楊氏矩陣查找，倒排索引關鍵詞Hash不重復編碼實踐，
- 第二十六章：基于給定的文檔生成倒排索引的編碼與實踐。
密匙五、外排序
適用范圍：大數據的排序，去重
基本原理及要點：外排序的歸并方法，置換選擇敗者樹原理，最優歸并樹
擴展：
問題實例：
1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節，內存限制大小是1M。返回頻數最高的100個詞。
這個數據具有很明顯的特點，詞的大小為16個字節，但是內存只有1M做hash明顯不夠，所以可以用來排序。內存可以當輸入緩沖區使用。
? ? 關于多路歸并算法及外排序的具體應用場景，請參見blog內此文：
- 第十章、如何給10^7個數據量的磁盤文件排序
密匙六、分布式處理之Mapreduce
? ??MapReduce是一種計算模型，簡單的說就是將大批量的工作（數據）分解（MAP）執行，然后再將結果合并成最終結果（REDUCE）。這樣做的好處是可以在任務被分解后，可以通過大量機器進行并行計算，減少整個操作的時間。但如果你要我再通俗點介紹，那么，說白了，Mapreduce的原理就是一個歸并排序。
? ? ? ? 適用范圍：數據量大，但是數據種類小可以放入內存
基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。
擴展：
問題實例：
?
? ? 更多具體闡述請參見blog內：
- 從Hadhoop框架與MapReduce模式中談海量數據處理，
- 及MapReduce技術的初步了解與學習。
其它模式/方法論，結合操作系統知識
至此，六種處理海量數據問題的模式/方法已經闡述完畢。據觀察，這方面的面試題無外乎以上一種或其變形，然題目為何取為是：秒殺99%的海量數據處理面試題，而不是100%呢。OK，給讀者看最后一道題，如下： 非常大的文件，裝不進內存。每行一個int類型數據，現在要你隨機取100個數。 我們發現上述這道題，無論是以上任何一種模式/方法都不好做，那有什么好的別的方法呢？我們可以看看：操作系統內存分頁系統設計(說白了，就是映射+建索引)。 Windows 2000使用基于分頁機制的虛擬內存。每個進程有4GB的虛擬地址空間。基于分頁機制，這4GB地址空間的一些部分被映射了物理內存，一些部分映射硬盤上的交換文 件，一些部分什么也沒有映射。程序中使用的都是4GB地址空間中的虛擬地址。而訪問物理內存，需要使用物理地址。 關于什么是物理地址和虛擬地址，請看：- 物理地址 (physical address): 放在尋址總線上的地址。放在尋址總線上，如果是讀，電路根據這個地址每位的值就將相應地址的物理內存中的數據放到數據總線中傳輸。如果是寫，電路根據這個 地址每位的值就將相應地址的物理內存中放入數據總線上的內容。物理內存是以字節(8位)為單位編址的。?
- 虛擬地址 (virtual address): 4G虛擬地址空間中的地址，程序中使用的都是虛擬地址。?使用了分頁機制之后，4G的地址空間被分成了固定大小的頁，每一頁或者被映射到物理內存，或者被映射到硬盤上的交換文件中，或者沒有映射任何東西。對于一 般程序來說，4G的地址空間，只有一小部分映射了物理內存，大片大片的部分是沒有映射任何東西。物理內存也被分頁，來映射地址空間。對于32bit的 Win2k，頁的大小是4K字節。CPU用來把虛擬地址轉換成物理地址的信息存放在叫做頁目錄和頁表的結構里。?
? ? 操作系統中的方法，先生成4G的地址表，在把這個表劃分為小的4M的小文件做個索引，二級索引。30位前十位表示第幾個4M文件，后20位表示在這個4M文件的第幾個，等等，基于key value來設計存儲，用key來建索引。
? ? 但如果現在只有10000個數，然后怎么去隨機從這一萬個數里面隨機取100個數？請讀者思考。更多海里數據處理面試題，請參見此文第一部分：http://blog.csdn.net/v_july_v/article/details/6685962。
?
轉載于:https://www.cnblogs.com/acSzz/p/5721237.html
總結
- 上一篇： 利用gcc自带的功能-fstack-pr
- 下一篇： android sdk里的各目录作用