TOP K使用思路是什么

TOP K使用思路是什么，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

TOP K

通用思路：

1、使用Hash取模的方法將大文件劃分成若干小文件；

2、使用HashMap或者字典樹（trie樹）對(duì)小文件進(jìn)行詞頻統(tǒng)計(jì)；

3、對(duì)小文件按照詞頻進(jìn)行排序（堆排序等），取每個(gè)小文件的前N個(gè)；

4、將小文件的結(jié)果歸并排序，再對(duì)歸并后的文件取前N個(gè)。

有1億個(gè)浮點(diǎn)數(shù)，如果找出期中最大的10000個(gè)？

對(duì)于第三部，首先讀入前10000個(gè)數(shù)來(lái)創(chuàng)建大小為10000的最小堆，建堆的時(shí)間復(fù)雜度為O（mlogm）（m為數(shù)組的大小即為10000），然后遍歷后續(xù)的數(shù)字，并于堆頂（最?。?shù)字進(jìn)行比較。如果比最小的數(shù)小，則繼續(xù)讀取后續(xù)數(shù)字；如果比堆頂數(shù)字大，則替換堆頂元素并重新調(diào)整堆為最小堆。整個(gè)過(guò)程直至1億個(gè)數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有10000個(gè)數(shù)字。

有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。

順序讀文件中，對(duì)于每個(gè)詞x，取hash(x)%5000，然后按照該值存到5000個(gè)小文件（記為x0,x1,...x4999）中。這樣每個(gè)文件大概是200k左右。
如果其中的有的文件超過(guò)了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過(guò)1M。 對(duì)每個(gè)小文件，統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率（可以采用trie樹/hash_map等），并取出出現(xiàn)頻率最大的100個(gè)詞（可以用含100個(gè)結(jié)點(diǎn)的最小堆），并把100個(gè)詞及相應(yīng)的頻率存入文件，這樣又得到了5000個(gè)文件。下一步就是把這5000個(gè)文件進(jìn)行歸并（類似與歸并排序）的過(guò)程了。

給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒(méi)排過(guò)序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中？

申請(qǐng)512MB的內(nèi)存，一個(gè)bit位代表一個(gè)unsigned int值。讀入40億個(gè)數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。

已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。

8位整數(shù)可以表示的最大十進(jìn)制數(shù)值為99999999。如果每個(gè)數(shù)字對(duì)應(yīng)于位圖中一個(gè)bit位，那么存儲(chǔ)8位整數(shù)大約需要99MB。因?yàn)?B=8bit，所以99Mbit折合成內(nèi)存為99/8=12.375MB的內(nèi)存，即可以只用12.375MB的內(nèi)存表示所有的8位數(shù)電話號(hào)碼的內(nèi)容。

給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？

如果使用布隆過(guò)濾器，那么問(wèn)題就很好辦了，4G的內(nèi)存足以容納300多億的bit，所以足夠處理了，先將a文件中的url都放入布隆過(guò)濾器，之后遍歷b文件，對(duì)每個(gè)url都詢問(wèn)布隆過(guò)濾器看其是否已經(jīng)存在，如果存在，則此條URL輸入結(jié)果文件。

看完上述內(nèi)容，你們掌握TOP K使用思路是什么的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！