TopN解決方式期揪？
答：
1. 10億個數(shù)中如何高效地找到最大的一個數(shù)
將10億個數(shù)據(jù)分成1000份掉奄，每份100萬個數(shù)據(jù)，找到每份數(shù)據(jù)中最大的那個數(shù)據(jù)凤薛，最后在剩下的1000個數(shù)據(jù)里面找出最大的數(shù)據(jù)姓建。 從100萬個數(shù)據(jù)遍歷選擇最大的數(shù)诞仓，此方法需要每次的內存空間為10^6*4=4MB，一共需要1000次這樣的比較速兔。
2. 10億個數(shù)中如何高效地找到第K個數(shù)
對于top K類問題狂芋，通常比較好的方案是分治+hash+小頂堆：
先將數(shù)據(jù)集按照Hash方法分解成多個小數(shù)據(jù)集
然后用小頂堆求出每個數(shù)據(jù)集中最大的K個數(shù)
最后在所有top K中求出最終的top K。
如果是top詞頻可以使用分治+ Trie樹/hash +小頂堆：
先將數(shù)據(jù)集按照Hash方法分解成多個小數(shù)據(jù)集
然后使用Trie樹或者Hash統(tǒng)計每個小數(shù)據(jù)集中的query詞頻
之后用小頂堆求出每個數(shù)據(jù)集中出頻率最高的前K個數(shù)
最后在所有top K中求出最終的top K憨栽。
時間復雜度：建堆時間復雜度是O(K),算法的時間復雜度為O(NlogK)帜矾。
3. top K常用的方法
快排+選擇排序：排序后的集合中進行查找
時間復雜度： 時間復雜度為O(NlogN)
缺點：需要比較大的內存，且效率低
局部淘汰：取前K個元素并排序屑柔，然后依次掃描剩余的元素屡萤，插入到排好序的序列中(二分查找)，并淘汰最小值掸宛。
時間復雜度： 時間復雜度為O(NlogK) (logK為二分查找的復雜度)死陆。
分治法：將10億個數(shù)據(jù)分成1000份，每份100萬個數(shù)據(jù)唧瘾，找到每份數(shù)據(jù)中最大的K個措译，最后在剩下的1000K個數(shù)據(jù)里面找出最大的K個，100萬個數(shù)據(jù)里面查找最大的K個數(shù)據(jù)可以使用Partition的方法
時間復雜度： 時間復雜度為O(N+1000K)
Hash法： 如果這10億個數(shù)里面有很多重復的數(shù)饰序，先通過Hash法领虹，把這10億個數(shù)字去重復，這樣如果重復率很高的話求豫，會減少很大的內存用量塌衰，從而縮小運算空間，然后通過分治法或最小堆法查找最大的K個數(shù)蝠嘉。
小頂堆： 首先讀入前K個數(shù)來創(chuàng)建大小為K的小頂堆最疆，建堆的時間復雜度為O(K)，然后遍歷后續(xù)的數(shù)字蚤告，并于堆頂（最信帷）數(shù)字進行比較。如果比最小的數(shù)小杜恰，則繼續(xù)讀取后續(xù)數(shù)字获诈；如果比堆頂數(shù)字大，則替換堆頂元素并重新調整堆為最小堆箫章。
時間復雜度： 時間復雜度為O(NlogK)
Trie樹： 如果是從10億個重復比較多的單詞找高頻詞匯烙荷，數(shù)據(jù)集按照Hash方法分解成多個小數(shù)據(jù)集镜会，然后使用Trie樹統(tǒng)計每個小數(shù)據(jù)集中的query詞頻檬寂，之后用小頂堆求出每個數(shù)據(jù)集中出現(xiàn)頻率最高的前K個數(shù)，最后在所有top K中求出最終的top K戳表。
適用范圍：數(shù)據(jù)量大桶至，重復多昼伴，但是數(shù)據(jù)種類小可以放入內存
時間復雜度：O(Len*N)，N為字符串的個數(shù),Len為字符串長度
桶排序：一個數(shù)據(jù)表分割成許多buckets镣屹，然后每個bucket各自排序圃郊，或用不同的排序算法，或者遞歸的使用bucket sort算法女蜈。也是典型的divide-and-conquer分而治之的策略持舆。
使用范圍：如果已知了數(shù)據(jù)的范圍，那么可以劃分合適大小的桶伪窖，直接借用桶排序的思路
時間復雜度：O(N*logM)逸寓，N 為待排序的元素的個數(shù)，M為桶的個數(shù)
計數(shù)排序：計數(shù)排序其實是桶排序的一種特殊情況覆山。當要排序的 n 個數(shù)據(jù)竹伸，所處的范圍并不大的時候，比如最大值是 k簇宽，我們就可以把數(shù)據(jù)劃分成 k 個桶勋篓。每個桶內的數(shù)據(jù)值都是相同的，省掉了桶內排序的時間魏割。
適用范圍：只能用在數(shù)據(jù)范圍不大的場景
時間復雜度：O(N)
基數(shù)排序：將整數(shù)按位數(shù)切割成不同的數(shù)字譬嚣，然后按每個位數(shù)分別比較。
適用范圍：可以對字符串類型的關鍵字進行排序钞它。
時間復雜度： O(N*M)孤荣，M為要排序的數(shù)據(jù)的位數(shù)
4. 實際情況
（1）單機+單核+足夠大內存
- 順序遍歷（或先用HashMap求出每個詞出現(xiàn)的頻率）
- 查找10億個查詢次（每個占8B）中出現(xiàn)頻率最高的10個，考慮到每個查詢詞占8B须揣，則10億個查詢次所需的內存大約是10^9 * 8B=8GB內存盐股。如果有這么大內存，直接在內存中對查詢次進行排序耻卡，順序遍歷找出10個出現(xiàn)頻率最大的即可疯汁。
- 優(yōu)點： 簡單快速
（2）單機+多核+足夠大內存
- partition
- 直接在內存總使用Hash方法將數(shù)據(jù)劃分成n個partition，每個partition交給一個線程處理卵酪，線程的處理邏輯同（1）類似幌蚊，最后一個線程將結果歸并。
- 瓶頸：數(shù)據(jù)傾斜溃卡。每個線程的處理速度可能不同溢豆，快的線程需要等待慢的線程。
- 解決的方法：將數(shù)據(jù)劃分成c×n個partition（c>1）瘸羡，每個線程處理完當前partition后主動取下一個partition繼續(xù)處理漩仙，知道所有數(shù)據(jù)處理完畢，最后由一個線程進行歸并。
（3）單機+單核+受限內存
- 分治 + （1）
- 將原文件中的數(shù)據(jù)切割成M小文件队他，如果小文件仍大于內存大小卷仑，繼續(xù)采用Hash的方法對數(shù)據(jù)文件進行分割，直到每個小文件小于內存大小麸折，這樣每個文件可放到內存中處理锡凝。采用（1）的方法依次處理每個小文件。
（4）多機+受限內存
- 數(shù)據(jù)分發(fā) + （3）
- 將數(shù)據(jù)分發(fā)到多臺機器上垢啼，每臺機器采用（3）中的策略解決本地的數(shù)據(jù)窜锯。可采用hash+socket方法進行數(shù)據(jù)分發(fā)芭析。
- MapReduce
- top K問題很適合采用MapReduce框架解決衬浑，用戶只需編寫一個Map函數(shù)和兩個Reduce 函數(shù)，然后提交到Hadoop
- 首先根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(MD5)后的值按照范圍劃分到不同的機器上放刨，最好可以讓數(shù)據(jù)劃分后一次讀入內存工秩，這樣不同的機器負責處理不同的數(shù)值范圍，實際上就是Map进统。
- 得到結果后助币，各個機器只需拿出各自出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，然后匯總螟碎，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)眉菱，這實際上就是Reduce過程。
- 對于Map函數(shù)掉分，采用Hash算法俭缓，將Hash值相同的數(shù)據(jù)交給同一個Reduce task；對于第一個Reduce函數(shù)酥郭，采用HashMap統(tǒng)計出每個詞出現(xiàn)的頻率华坦，對于第二個Reduce 函數(shù)，統(tǒng)計所有Reduce task不从，輸出數(shù)據(jù)中的top K即可惜姐。
