十道面試題與十個海量數據處理方法總結(5)

八、外排序

　　適用范圍：大數據的排序，去重

　　基本原理及要點：外排序的歸并方法，置換選擇敗者樹原理，最優歸并樹

　　擴展：

　　問題實例：
　　1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節，內存限制大小是1M。返回頻數最高的100個詞。

　　這個數據具有很明顯的特點，詞的大小為16個字節，但是內存只有1m做hash有些不夠，所以可以用來排序。內存可以當輸入緩沖區使用。

九、trie樹

　　適用范圍：數據量大，重復多，但是數據種類小可以放入內存

　　基本原理及要點：實現方式，節點孩子的表示方式

　　擴展：壓縮實現。

　　問題實例：
　　1).有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序。
　　2).1000萬字符串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒有重復的字符串。請問怎么設計和實現？
　　3).尋找熱門查詢：查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個，每個不超過255字節。

十、分布式處理 mapreduce

　　適用范圍：數據量大，但是數據種類小可以放入內存

　　基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。

　　擴展：
　　問題實例：
　　1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
　　2).海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10。
　　3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數并對它們操作。如何找到N^2個數的中數(median)？

經典問題分析
　　上千萬or億數據（有重復），統計其中出現次數最多的前N個數據,分兩種情況：可一次讀入內存，不可一次讀入。

　　可用思路：trie樹+堆，數據庫索引，劃分子集分別統計，hash，分布式計算，近似統計，外排序

　　所謂的是否能一次讀入內存，實際上應該指去除重復后的數據量。如果去重后數據可以放入內存，我們可以為數據建立字典，比如通過 map，hashmap，trie，然后直接進行統計即可。當然在更新每條數據的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前N個數據，當然這樣導致維護次數增加，不如完全統計后在求前N大效率高。

　　如果數據無法放入內存。一方面我們可以考慮上面的字典方法能否被改進以適應這種情形，可以做的改變就是將字典存放到硬盤上，而不是內存，這可以參考數據庫的存儲方法。

　　當然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過程，首先可以根據數據值或者把數據hash(md5)后的值，將數據按照范圍劃分到不同的機子，最好可以讓數據劃分后可以一次讀入內存，這樣不同的機子負責處理各種的數值范圍，實際上就是map。得到結果后，各個機子只需拿出各自的出現次數最多的前N個數據，然后匯總，選出所有的數據中出現次數最多的前N個數據，這實際上就是reduce過程。

　　實際上可能想直接將數據均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數據可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可能存在具有相同數目的數據。比如我們要找出現次數最多的前100個，我們將1000萬的數據分布到10臺機器上，找到每臺出現次數最多的前 100個，歸并之后這樣不能保證找到真正的第100個，因為比如出現次數最多的第100個可能有1萬個，但是它被分到了10臺機子，這樣在每臺上只有1千個，假設這些機子排名在1000個之前的那些都是單獨分布在一臺機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每臺機子選出出現次數最多的1000個再歸并，仍然會出錯，因為可能存在大量個數為1001個的發生聚集。因此不能將數據隨便均分到不同機子上，而是要根據hash 后的值將它們映射到不同的機子上處理，讓不同的機器處理一個數值范圍。

　 而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用于單機版本，也就是將總的數據根據值的范圍，劃分成多個不同的子文件，然后逐個處理。處理完畢之后再對這些單詞的及其出現頻率進行一個歸并。實際上就可以利用一個外排序的歸并過程。

　 另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規?？梢苑湃雰却?。