使用堆實(shí)現(xiàn)Top K算法(JS實(shí)現(xiàn))
先來(lái)聊一聊Top K算法,具體內(nèi)容如下
應(yīng)用場(chǎng)景:
搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái),每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。
假設(shè)目前有一千萬(wàn)個(gè)記錄(這些查詢串的重復(fù)度比較高,雖然總數(shù)是1千萬(wàn),但如果除去重復(fù)后,不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢串的重復(fù)度越高,說(shuō)明查詢它的用戶越多,也就是越熱門。),請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串,要求使用的內(nèi)存不能超過(guò)1G。
必備知識(shí):
什么是哈希表?
哈希表(Hash table,也叫散列表),是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。
也就是說(shuō),它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄,以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表。
哈希表的做法其實(shí)很簡(jiǎn)單,就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字,然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余,取余結(jié)果就當(dāng)作數(shù)組的下標(biāo),將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。
而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候,就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo),并定位到該空間獲取value,如此一來(lái),就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位。
問(wèn)題解析:
要統(tǒng)計(jì)最熱門查詢,首先就是要統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù),然后根據(jù)統(tǒng)計(jì)結(jié)果,找出Top 10。所以我們可以基于這個(gè)思路分兩步來(lái)設(shè)計(jì)該算法。
即,此問(wèn)題的解決分為以下倆個(gè)步驟:
第一步:Query統(tǒng)計(jì) (統(tǒng)計(jì)出每個(gè)Query出現(xiàn)的次數(shù))
Query統(tǒng)計(jì)有以下倆個(gè)方法,可供選擇:
1)、直接排序法 (經(jīng)常在日志文件中統(tǒng)計(jì)時(shí),使用cat file|format key|sort | uniq -c | sort -nr | head -n 10,就是這種方法)
首先我們最先想到的的算法就是排序了,首先對(duì)這個(gè)日志里面的所有Query都進(jìn)行排序,然后再遍歷排好序的Query,統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)了。
但是題目中有明確要求,那就是內(nèi)存不能超過(guò)1G,一千萬(wàn)條記錄,每條記錄是255Byte,很顯然要占據(jù)2.375G內(nèi)存,這個(gè)條件就不滿足要求了。
讓我們回憶一下數(shù)據(jù)結(jié)構(gòu)課程上的內(nèi)容,當(dāng)數(shù)據(jù)量比較大而且內(nèi)存無(wú)法裝下的時(shí)候,我們可以采用外排序的方法來(lái)進(jìn)行排序,這里我們可以采用歸并排序,因?yàn)闅w并排序有一個(gè)比較好的時(shí)間復(fù)雜度O(NlgN)。
排完序之后我們?cè)賹?duì)已經(jīng)有序的Query文件進(jìn)行遍歷,統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù),再次寫入文件中。
綜合分析一下,排序的時(shí)間復(fù)雜度是O(NlgN),而遍歷的時(shí)間復(fù)雜度是O(N),因此該算法的總體時(shí)間復(fù)雜度就是O(N+NlgN)=O(NlgN)。
2)、Hash Table法 (這種方法統(tǒng)計(jì)字符串出現(xiàn)的次數(shù)非常好)
在第1個(gè)方法中,我們采用了排序的辦法來(lái)統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù),時(shí)間復(fù)雜度是NlgN,那么能不能有更好的方法來(lái)存儲(chǔ),而時(shí)間復(fù)雜度更低呢?
題目中說(shuō)明了,雖然有一千萬(wàn)個(gè)Query,但是由于重復(fù)度比較高,因此事實(shí)上只有300萬(wàn)的Query,每個(gè)Query 255Byte,因此我們可以考慮把他們都放進(jìn)內(nèi)存中去,而現(xiàn)在只是需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu),在這里,Hash Table絕對(duì)是我們優(yōu)先的選擇,因?yàn)镠ash Table的查詢速度非常的快,幾乎是O(1)的時(shí)間復(fù)雜度。
那么,我們的算法就有了:
維護(hù)一個(gè)Key為Query字串,Value為該Query出現(xiàn)次數(shù)的HashTable,每次讀取一個(gè)Query,如果該字串不在Table中,那么加入該字串,并且將Value值設(shè)為1;如果該字串在Table中,那么將該字串的計(jì)數(shù)加一即可。最終我們?cè)贠(N)的時(shí)間復(fù)雜度內(nèi)完成了對(duì)該海量數(shù)據(jù)的處理。
本方法相比算法1:在時(shí)間復(fù)雜度上提高了一個(gè)數(shù)量級(jí),為O(N),但不僅僅是時(shí)間復(fù)雜度上的優(yōu)化,該方法只需要IO數(shù)據(jù)文件一次,而算法1的IO次數(shù)較多的,因此該算法2比算法1在工程上有更好的可操作性。
第二步:找出Top 10(找出出現(xiàn)次數(shù)最多的10個(gè))
算法一:普通排序(我們只用找出top10,所以全部排序有冗余)
我想對(duì)于排序算法大家都已經(jīng)不陌生了,這里不在贅述,我們要注意的是排序算法的時(shí)間復(fù)雜度是NlgN,在本題目中,三百萬(wàn)條記錄,用1G內(nèi)存是可以存下的。
算法二:部分排序
題目要求是求出Top 10,因此我們沒(méi)有必要對(duì)所有的Query都進(jìn)行排序,我們只需要維護(hù)一個(gè)10個(gè)大小的數(shù)組,初始化放入10個(gè)Query,按照每個(gè)Query的統(tǒng)計(jì)次數(shù)由大到小排序,然后遍歷這300萬(wàn)條記錄,每讀一條記錄就和數(shù)組最后一個(gè)Query對(duì)比,如果小于這個(gè)Query,那么繼續(xù)遍歷,否則,將數(shù)組中最后一條數(shù)據(jù)淘汰(還是要放在合適的位置,保持有序),加入當(dāng)前的Query。最后當(dāng)所有的數(shù)據(jù)都遍歷完畢之后,那么這個(gè)數(shù)組中的10個(gè)Query便是我們要找的Top10了。
不難分析出,這樣,算法的最壞時(shí)間復(fù)雜度是N*K, 其中K是指top多少。
算法三:堆
在算法二中,我們已經(jīng)將時(shí)間復(fù)雜度由NlogN優(yōu)化到N*K,不得不說(shuō)這是一個(gè)比較大的改進(jìn)了,可是有沒(méi)有更好的辦法呢?
分析一下,在算法二中,每次比較完成之后,需要的操作復(fù)雜度都是K,因?yàn)橐言夭迦氲揭粋€(gè)線性表之中,而且采用的是順序比較。這里我們注意一下,該數(shù)組是有序的,一次我們每次查找的時(shí)候可以采用二分的方法查找,這樣操作的復(fù)雜度就降到了logK,可是,隨之而來(lái)的問(wèn)題就是數(shù)據(jù)移動(dòng),因?yàn)橐苿?dòng)數(shù)據(jù)次數(shù)增多了。不過(guò),這個(gè)算法還是比算法二有了改進(jìn)。
基于以上的分析,我們想想,有沒(méi)有一種既能快速查找,又能快速移動(dòng)元素的數(shù)據(jù)結(jié)構(gòu)呢?
回答是肯定的,那就是堆。
借助堆結(jié)構(gòu),我們可以在log量級(jí)的時(shí)間內(nèi)查找和調(diào)整/移動(dòng)。因此到這里,我們的算法可以改進(jìn)為這樣,維護(hù)一個(gè)K(該題目中是10)大小的小根堆,然后遍歷300萬(wàn)的Query,分別和根元素進(jìn)行對(duì)比。
思想與上述算法二一致,只是在算法三,我們采用了最小堆這種數(shù)據(jù)結(jié)構(gòu)代替數(shù)組,把查找目標(biāo)元素的時(shí)間復(fù)雜度有O(K)降到了O(logK)。
那么這樣,采用堆數(shù)據(jù)結(jié)構(gòu),算法三,最終的時(shí)間復(fù)雜度就降到了N*logK,和算法二相比,又有了比較大的改進(jìn)。
至此,算法就完全結(jié)束了,經(jīng)過(guò)上述第一步、先用Hash表統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù),O(N);然后第二步、采用堆數(shù)據(jù)結(jié)構(gòu)找出Top 10,N*O(logK)。所以,我們最終的時(shí)間復(fù)雜度是:O(N) + N'*O(logK)。(N為1000萬(wàn),N'為300萬(wàn))。
js如何使用堆實(shí)現(xiàn)Top K 算法?
1. 使用堆算法實(shí)現(xiàn)Top,時(shí)間復(fù)雜度為 O(LogN)
function top(arr,comp){ if(arr.length == 0){return ;} var i = arr.length / 2 | 0 ; for(;i >= 0; i--){ if(comp(arr[i], arr[i * 2])){exch(arr, i, i*2);} if(comp(arr[i], arr[i * 2 + 1])) {exch(arr, i, i*2 + 1);} } return arr[0]; } function exch(arr,i,j){ var t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
2. 調(diào)用K次堆實(shí)現(xiàn),時(shí)間復(fù)雜度為 O(K * LogN)
function topK(arr,n,comp){ if(!arr || arr.length == 0 || n <=0 || n > arr.length){ return -1; } var ret = new Array(); for(var i = 0;i < n; i++){ var max = top(arr,comp); ret.push(max); arr.splice(0,1); } return ret; }
3.測(cè)試
var ret = topK(new Array(16,22,91,0,51,44,23),3,function (a,b){return a < b;}); console.log(ret);
以上就是為大家分享的使用堆實(shí)現(xiàn)Top K算法,何為Top K算法,希望對(duì)大家的學(xué)習(xí)有所幫助。
- 原生js獲取left值和top值的三種方法
- js瀏覽器滾動(dòng)條卷去的高度scrolltop(實(shí)例講解)
- Javascript實(shí)現(xiàn)的StopWatch功能示例
- JavaScript限制在客戶區(qū)可見(jiàn)范圍的拖拽(解決scrollLeft和scrollTop的問(wèn)題)(2)
- js中scrollTop()方法和scroll()方法用法示例
- 深入淺析JavaScript中的scrollTop
- js+css實(shí)現(xiàn)回到頂部按鈕(back to top)
- 解決js頁(yè)面滾動(dòng)效果scrollTop在FireFox與Chrome瀏覽器間的兼容問(wèn)題的方法
- js中不同的height, top的區(qū)別對(duì)比
- javascript獲取圖片的top N主色值方法詳解
相關(guān)文章
JavaScript設(shè)計(jì)模式之裝飾者模式實(shí)例詳解
這篇文章主要介紹了JavaScript設(shè)計(jì)模式之裝飾者模式,結(jié)合實(shí)例形式較為詳細(xì)的分析了裝飾者模式的概念、原理及javascript定義、使用裝飾者模式的相關(guān)操作技巧,需要的朋友可以參考下2019-01-01Javascript 調(diào)試?yán)?Firebug使用詳解六
有時(shí)候,為了更清楚方便的查看輸出信息,我們可能需要將一些調(diào)試信息進(jìn)行分組輸出,那么可以使用console.group來(lái)對(duì)信息進(jìn)行分組,在組信息輸出完成后用console.groupEnd結(jié)束分組。2009-07-07js中的時(shí)間轉(zhuǎn)換—毫秒轉(zhuǎn)換成日期時(shí)間的示例代碼
本篇文章主要是對(duì)js中的時(shí)間轉(zhuǎn)換—毫秒轉(zhuǎn)換成日期時(shí)間的示例代碼進(jìn)行了介紹,需要的朋友可以過(guò)來(lái)參考下,希望對(duì)大家有所幫助2014-01-01學(xué)習(xí)JavaScript鼠標(biāo)響應(yīng)事件
這篇文章主要帶領(lǐng)大家學(xué)習(xí)JavaScript鼠標(biāo)響應(yīng)事件,為大家分享了一個(gè)簡(jiǎn)單的鼠標(biāo)模擬案例,感興趣的小伙伴們可以參考一下2015-12-12JavaScript相等判斷的避坑實(shí)戰(zhàn)指南
JavaScript中的相等性判斷,在項(xiàng)目開發(fā)中,我經(jīng)常會(huì)遇到,今天我們一起探討下,下面這篇文章主要給大家介紹了關(guān)于JavaScript相等判斷的避坑實(shí)戰(zhàn)指南,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-08-08JavaScript中5個(gè)重要的Observer函數(shù)小結(jié)
瀏覽器為開發(fā)者提供了功能豐富的Observer,本文主要介紹了JavaScript中5個(gè)重要的Observer函數(shù)小結(jié),具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01