在大規(guī)模數(shù)據(jù)處理中芦圾，經(jīng)常會(huì)遇到的一類問題：在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個(gè)數(shù)昔案，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)，這類問題通常被稱為top K問題愚隧。例如蒂阱，在搜索引擎中，統(tǒng)計(jì)搜索最熱門的10個(gè)查詢?cè)~狂塘；在歌曲庫(kù)中統(tǒng)計(jì)下載最高的前10首歌等录煤。
1、最容易想到的方法是將數(shù)據(jù)全部排序荞胡。該方法并不高效妈踊，因?yàn)轭}目的目的是尋找出最大的10000個(gè)數(shù)即可，而排序卻是將所有的元素都排序了泪漂，做了很多的無用功廊营。
2、局部淘汰法萝勤。用一個(gè)容器保存前10000個(gè)數(shù)露筒，然后將剩余的所有數(shù)字一一與容器內(nèi)的最小數(shù)字相比，如果所有后續(xù)的元素都比容器內(nèi)的10000個(gè)數(shù)還小敌卓，那么容器內(nèi)這個(gè)10000個(gè)數(shù)就是最大10000個(gè)數(shù)慎式。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大，則刪掉容器內(nèi)最小元素趟径，并將該元素插入容器瞬捕，最后遍歷完這1億個(gè)數(shù)，得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了舵抹。此時(shí)的時(shí)間復(fù)雜度為O（n+m^2），其中m為容器的大小劣砍。
這個(gè)容器可以用（小頂堆）最小堆來實(shí)現(xiàn)惧蛹。我們知道完全二叉樹有幾個(gè)非常重要的特性，就是假如該二叉樹中總共有N個(gè)節(jié)點(diǎn)刑枝，那么該二叉樹的深度就是log2N香嗓，對(duì)于小頂堆來說移動(dòng)根元素到 底部或者移動(dòng)底部元素到根部只需要log2N，相比N來說時(shí)間復(fù)雜度優(yōu)化太多了（1億的logN值是26-27的一個(gè)浮點(diǎn)數(shù)）装畅】坑椋基本的思路就是先從文件中取出1000個(gè)元素構(gòu)建一個(gè)小頂堆數(shù)組k，然后依次對(duì)剩下的100億-1000個(gè)數(shù)字進(jìn)行遍歷m掠兄，如果m大于小頂堆的根元素像云，即k[0]锌雀，那么用m取代k[0]，對(duì)新的數(shù)組進(jìn)行重新構(gòu)建組成一個(gè)新的小頂堆迅诬。這個(gè)算法的時(shí)間復(fù)雜度是O((100億-1000)log(1000))腋逆，即O((N-M)logM)，空間復(fù)雜度是M
這個(gè)算法優(yōu)點(diǎn)是性能尚可侈贷，空間復(fù)雜度低惩歉，IO讀取比較頻繁，對(duì)系統(tǒng)壓力大俏蛮。
3撑蚌、第三種方法是分治法，即大數(shù)據(jù)里最常用的MapReduce搏屑。
a争涌、將100億個(gè)數(shù)據(jù)分為1000個(gè)大分區(qū)，每個(gè)區(qū)1000萬(wàn)個(gè)數(shù)據(jù)
b睬棚、每個(gè)大分區(qū)再細(xì)分成100個(gè)小分區(qū)第煮。總共就有1000*100=10萬(wàn)個(gè)分區(qū)
c抑党、計(jì)算每個(gè)小分區(qū)上最大的1000個(gè)數(shù)包警。
為什么要找出每個(gè)分區(qū)上最大的1000個(gè)數(shù)？舉個(gè)例子說明底靠，全校高一有100個(gè)班害晦，我想找出全校前10名的同學(xué)，很傻的辦法就是暑中，把高一100個(gè)班的同學(xué)成績(jī)都取出來壹瘟，作比較，這個(gè)比較數(shù)據(jù)量太大了鳄逾。應(yīng)該很容易想到稻轨，班里的第11名，不可能是全校的前10名雕凹。也就是說殴俱，不是班里的前10名，就不可能是全校的前10名枚抵。因此线欲，只需要把每個(gè)班里的前10取出來，作比較就行了汽摹，這樣比較的數(shù)據(jù)量就大大地減少了李丰。我們要找的是100億中的最大1000個(gè)數(shù)，所以每個(gè)分區(qū)中的第1001個(gè)數(shù)一定不可能是所有數(shù)據(jù)中的前1000個(gè)逼泣。
d趴泌、合并每個(gè)大分區(qū)細(xì)分出來的小分區(qū)舟舒。每個(gè)大分區(qū)有100個(gè)小分區(qū)，我們已經(jīng)找出了每個(gè)小分區(qū)的前1000個(gè)數(shù)踱讨。將這100個(gè)分區(qū)的1000*100個(gè)數(shù)合并魏蔗，找出每個(gè)大分區(qū)的前1000個(gè)數(shù)。
e痹筛、合并大分區(qū)莺治。我們有1000個(gè)大分區(qū)，上一步已找出每個(gè)大分區(qū)的前1000個(gè)數(shù)帚稠。我們將這1000*1000個(gè)數(shù)合并谣旁，找出前1000.這1000個(gè)數(shù)就是所有數(shù)據(jù)中最大的1000個(gè)數(shù)。
（a滋早、b榄审、c為map階段，d杆麸、e為reduce階段）
4搁进、Hash法如果這1億個(gè)書里面有很多重復(fù)的數(shù)，先通過Hash法昔头，把這1億個(gè)數(shù)字去重復(fù)饼问，這樣如果重復(fù)率很高的話，會(huì)減少很大的內(nèi)存用量揭斧，從而縮小運(yùn)算空間莱革，然后通過分治法或最小堆法查找最大的10000個(gè)數(shù)。
注：參考sofuzi的博客內(nèi)容
