|
程序員編程藝術(shù)：第三章續(xù)、Top K算法問題的實(shí)現(xiàn)
作者：July，zhouzhenren，yansha。
致謝：微軟100題實(shí)現(xiàn)組，狂想曲創(chuàng)作組。
時(shí)間：2011年05月08日
微博：http://weibo.com/julyweibo 。
出處：http://blog.csdn.net/v_JULY_v 。
wiki：http://tctop./。
-----------------------------------------------
前奏
在上一篇文章，程序員面試題狂想曲：第三章、尋找最小的k個(gè)數(shù)中，后來(lái)為了論證類似快速排序中partition的方法在最壞情況下，能在O（N）的時(shí)間復(fù)雜度內(nèi)找到最小的k個(gè)數(shù)，而前前后后updated了10余次。所謂功夫不負(fù)苦心人，終于得到了一個(gè)想要的結(jié)果。
簡(jiǎn)單總結(jié)如下（詳情，請(qǐng)參考原文第三章）：
1、RANDOMIZED-SELECT，以序列中隨機(jī)選取一個(gè)元素作為主元，可達(dá)到線性期望時(shí)間O（N）的復(fù)雜度。
2、SELECT，快速選擇算法，以序列中“五分化中項(xiàng)的中項(xiàng)”，或“中位數(shù)的中位數(shù)”作為主元（樞紐元），則不容置疑的可保證在最壞情況下亦為O（N）的復(fù)雜度。
本章，咱們來(lái)闡述尋找最小的k個(gè)數(shù)的反面，即尋找最大的k個(gè)數(shù)，但此刻可能就有讀者質(zhì)疑了，尋找最大的k個(gè)數(shù)和尋找最小的k個(gè)數(shù)，原理不是一樣的么?
是的，的確是一樣，但這個(gè)尋找最大的k個(gè)數(shù)的問題的實(shí)用范圍更廣，因?yàn)樗鼱砍兜搅艘粋€(gè)Top K算法問題，以及有關(guān)搜索引擎，海量數(shù)據(jù)處理等廣泛的問題，所以本文特意對(duì)這個(gè)Top K算法問題，進(jìn)行闡述以及實(shí)現(xiàn)（側(cè)重實(shí)現(xiàn)，因?yàn)槟菢涌雌饋?lái)，會(huì)更令人激動(dòng)人心），算是第三章的續(xù)。ok，有任何問題，歡迎隨時(shí)不吝指正。謝謝。
說(shuō)明
關(guān)于尋找最小K個(gè)數(shù)能做到最壞情況下為O（N）的算法及證明，請(qǐng)參考原第三章，尋找最小的k個(gè)數(shù)，本文的代碼不保證O（N）的平均時(shí)間復(fù)雜度，只是根據(jù)第三章有辦法可以做到而已（如上面總結(jié)的，2、SELECT，快速選擇算法，以序列中“五分化中項(xiàng)的中項(xiàng)”，或“中位數(shù)的中位數(shù)”作為主元或樞紐元的方法，原第三章已經(jīng)嚴(yán)格論證并得到結(jié)果）。
第一節(jié)、尋找最小的第k個(gè)數(shù)
在進(jìn)入尋找最大的k個(gè)數(shù)的主題之前，先補(bǔ)充下關(guān)于尋找最k小的數(shù)的三種簡(jiǎn)單實(shí)現(xiàn)。由于堆的完整實(shí)現(xiàn)，第三章：第五節(jié)，堆結(jié)構(gòu)實(shí)現(xiàn)，處理海量數(shù)據(jù)中已經(jīng)給出，下面主要給出類似快速排序中partition過(guò)程的代碼實(shí)現(xiàn)：
尋找最小的k個(gè)數(shù)，實(shí)現(xiàn)一：
尋找最小的第k個(gè)數(shù)，實(shí)現(xiàn)二：
尋找最小的第k個(gè)數(shù)，實(shí)現(xiàn)三：
測(cè)試：
The average time of searching a date in the array size of 5000 is 0
The average time of searching a date in the array size of 50000 is 1
The average time of searching a date in the array size of 500000 is 12
The average time of searching a date in the array size of 5000000 is 114
The average time of searching a date in the array size of 50000000 is 1159
Press any key to continue
通過(guò)測(cè)試這個(gè)程序，我們竟發(fā)現(xiàn)這個(gè)程序的運(yùn)行時(shí)間是線性的?
或許，你還沒有意識(shí)到這個(gè)問題，ok，聽我慢慢道來(lái)。
我們之前說(shuō)，要保證這個(gè)算法是線性的，就一定要在樞紐元的選取上下足功夫：
1、要么是隨機(jī)選取樞紐元作為劃分元素
2、要么是取中位數(shù)的中位數(shù)作為樞紐元?jiǎng)澐衷?br>
現(xiàn)在，這程序直接選取了數(shù)組中第一個(gè)元素作為樞紐元
竟然，也能做到線性O(shè)（N）的復(fù)雜度，這不是自相矛盾么?
你覺得這個(gè)程序的運(yùn)行時(shí)間是線性O(shè)（N），是巧合還是確定會(huì)是如此?
哈哈，且看1、@well：根據(jù)上面的運(yùn)行結(jié)果不能判斷線性，如果人家是O(n^1.1) 也有可能啊，而且部分?jǐn)?shù)據(jù)始終是擬合，還是要數(shù)學(xué)證明才可靠。2、@July：同時(shí)，隨機(jī)數(shù)組中選取一個(gè)元素作為樞紐元！=> 隨機(jī)數(shù)組中隨機(jī)選取一個(gè)元素作為樞紐元（如果是隨機(jī)選取隨機(jī)數(shù)組中的一個(gè)元素作為主元，那就不同了，跟隨機(jī)選取數(shù)組中一個(gè)元素作為樞紐元一樣了）。3、@飛羽：正是因?yàn)閿?shù)組本身是隨機(jī)的，所以選擇第一個(gè)元素和隨機(jī)選擇其它的數(shù)是等價(jià)的（由等概率產(chǎn)生保證），這第3點(diǎn)，我與飛羽有分歧，至于誰(shuí)對(duì)誰(shuí)錯(cuò)，待時(shí)間讓我考證。
關(guān)于上面第3點(diǎn)我和飛羽的分歧，在我們進(jìn)一步討論之后，一致認(rèn)定（不過(guò)，相信，你看到了上面程序更新的注釋之后，你應(yīng)該有幾分領(lǐng)會(huì)了）：
- 我們說(shuō)輸入一個(gè)數(shù)組的元素，不按其順序輸入：如，1,2,3,4,5,6,7，而是這樣輸入：5,7,6,4,3，1,2，這就叫隨機(jī)輸入，而這種情況就相當(dāng)于上述程序主函數(shù)中所產(chǎn)生的隨機(jī)數(shù)組。然而選取隨機(jī)輸入的數(shù)組或隨機(jī)數(shù)組中第一個(gè)元素作為主元，我們不能稱之為說(shuō)是隨機(jī)選取樞紐元。
- 因?yàn)?，隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的數(shù)據(jù)是隨機(jī)的，沒錯(cuò)，但你要知道，你總是選取隨機(jī)數(shù)組的第一個(gè)元素作為樞紐元，這不叫隨機(jī)選取樞紐元。
- 所以，上述程序的主函數(shù)中隨機(jī)產(chǎn)生的數(shù)組對(duì)這個(gè)程序的算法而言，沒有任何意義，就是幫忙產(chǎn)生了一個(gè)隨機(jī)數(shù)組，幫助我們完成了測(cè)試，且方便我們測(cè)試大數(shù)據(jù)量而已，就這么簡(jiǎn)單。
- 且一般來(lái)說(shuō)，我們看一個(gè)程序的 時(shí)間復(fù)雜度，是不考慮 其輸入情況的，即不考慮主函數(shù)，正如這個(gè) kth number 的程序所見，你每次都是隨機(jī)選取數(shù)組中第一個(gè)元素作為樞紐元，而并不是隨機(jī)選擇樞紐元，所以，做不到平均時(shí)間復(fù)雜度為O（N）。
所以：想要保證此快速選擇算法為O（N）的復(fù)雜度，只有兩種途徑，那就是保證劃分的樞紐元元素的選取是：
1、隨機(jī)的（注，此樞紐元隨機(jī)不等同于數(shù)組隨機(jī)）
2、五分化中項(xiàng)的中項(xiàng)，或中位數(shù)的中位數(shù)。
所以，雖然咱們對(duì)于一切心知肚明，但上面程序的運(yùn)行結(jié)果說(shuō)明不了任何問題，這也從側(cè)面再次佐證了咱們第三章中觀點(diǎn)的正確無(wú)誤性。
updated：
非常感謝飛羽等人的工作，將上述三個(gè)版本綜合到了一起（待進(jìn)一步測(cè)試）：
說(shuō)明：@飛羽：因?yàn)轭A(yù)先設(shè)定了K，經(jīng)過(guò)分割算法后，數(shù)組肯定被劃分為array[0...k-1]和array[k...length-1]，注意到經(jīng)過(guò)Select_K_Version操作后，數(shù)組是被不斷地分割的，使得比array[k-1]的元素小的全在左邊，題目要求的是最小的K個(gè)元素，當(dāng)然也就是array[0...k-1]，所以輸出的結(jié)果就是前k個(gè)最小的數(shù)：
7 8 9 54 6 4 11 1 2 33
4 1 2 6 7 8 9 11 33
7 6 4 1 2 8 9 11 33
7 8 9 6 4 11 1 2 33
Press any key to continue
（更多，請(qǐng)參見：此狂想曲系列tctop修訂wiki頁(yè)面：http://tctop./）
第二節(jié)、尋找最大的k個(gè)數(shù)
把之前第三章的問題，改幾個(gè)字，即成為尋找最大的k個(gè)數(shù)的問題了，如下所述：
查找最大的k個(gè)元素
題目描述：輸入n個(gè)整數(shù)，輸出其中最大的k個(gè)。
例如輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字，則最大的4個(gè)數(shù)字為8，7，6和5。
分析：由于尋找最大的k個(gè)數(shù)的問題與之前的尋找最小的k個(gè)數(shù)的問題，本質(zhì)是一樣的，所以，這里就簡(jiǎn)單闡述下思路，ok，考驗(yàn)?zāi)闩e一反三能力的時(shí)間到了：
1、排序，快速排序。我們知道，快速排序平均所費(fèi)時(shí)間為n*logn，從小到大排序這n個(gè)數(shù)，然后再遍歷序列中后k個(gè)元素輸出，即可，總的時(shí)間復(fù)雜度為O（n*logn+k）=O（n*logn）。
2、排序，選擇排序。用選擇或交換排序，即遍歷n個(gè)數(shù)，先把最先遍歷到得k個(gè)數(shù)存入大小為k的數(shù)組之中，對(duì)這k個(gè)數(shù)，利用選擇或交換排序，找到k個(gè)數(shù)中的最小數(shù)kmin（kmin設(shè)為k個(gè)元素的數(shù)組中最小元素），用時(shí)O（k）（你應(yīng)該知道，插入或選擇排序查找操作需要O（k）的時(shí)間），后再繼續(xù)遍歷后n-k個(gè)數(shù)，x與kmin比較：如果x>kmin，則x代替kmin，并再次重新找出k個(gè)元素的數(shù)組中最大元素kmin‘（多謝jiyeyuran 提醒修正）；如果x<kmin，則不更新數(shù)組。這樣，每次更新或不更新數(shù)組的所用的時(shí)間為O（k）或O（0），整趟下來(lái)，總的時(shí)間復(fù)雜度平均下來(lái)為：n*O（k）=O（n*k）。
3、維護(hù)k個(gè)元素的最小堆，原理與上述第2個(gè)方案一致，即用容量為k的最小堆存儲(chǔ)最先遍歷到的k個(gè)數(shù)，并假設(shè)它們即是最大的k個(gè)數(shù)，建堆費(fèi)時(shí)O（k），并調(diào)整堆（費(fèi)時(shí)O（logk））后，有k1>k2>...kmin（kmin設(shè)為小頂堆中最小元素）。繼續(xù)遍歷數(shù)列，每次遍歷一個(gè)元素x，與堆頂元素比較，若x>kmin，則更新堆（用時(shí)logk），否則不更新堆。這樣下來(lái)，總費(fèi)時(shí)O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各項(xiàng)操作時(shí)間復(fù)雜度均為logk（不然，就如上述思路2所述：直接用數(shù)組也可以找出最大的k個(gè)元素，用時(shí)O（n*k））。
4、按編程之美第141頁(yè)上解法二的所述，類似快速排序的劃分方法，N個(gè)數(shù)存儲(chǔ)在數(shù)組S中，再?gòu)臄?shù)組中隨機(jī)選取一個(gè)數(shù)X，把數(shù)組劃分為Sa和Sb倆部分，Sa>=X>=Sb，如果要查找的k個(gè)元素小于Sa的元素個(gè)數(shù)，則返回Sa中較大的k個(gè)元素，否則返回Sa中所有的元素+Sb中最大的k-|Sa|個(gè)元素。不斷遞歸下去，把問題分解成更小的問題，平均時(shí)間復(fù)雜度為O（N）（編程之美所述的n*logk的復(fù)雜度有誤，應(yīng)為O（N），特此訂正。其嚴(yán)格證明，請(qǐng)參考第三章：程序員面試題狂想曲：第三章、尋找最小的k個(gè)數(shù)、updated 10次）。
.........
其它的方法，在此不再重復(fù)了，同時(shí)，尋找最小的k個(gè)數(shù)借助堆的實(shí)現(xiàn)，代碼在上一篇文章第三章已有給出，更多，可參考第三章，只要把最大堆改成最小堆，即可。
第三節(jié)、Top K 算法問題
3.1、搜索引擎熱門查詢統(tǒng)計(jì)
題目描述：
搜索引擎會(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。
分析：這個(gè)問題在之前的這篇文章十一、從頭到尾徹底解析Hash表算法里，已經(jīng)有所解答。方法是:
第一步、先對(duì)這批海量數(shù)據(jù)預(yù)處理，在O（N）的時(shí)間內(nèi)用Hash表完成統(tǒng)計(jì)（之前寫成了排序，特此訂正。July、2011.04.27）；
第二步、借助堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，找出Top K，時(shí)間復(fù)雜度為N‘logK。
即，借助堆結(jié)構(gòu)，我們可以在log量級(jí)的時(shí)間內(nèi)查找和調(diào)整/移動(dòng)。因此，維護(hù)一個(gè)K(該題目中是10)大小的小根堆（K1>K2>....Kmin，Kmin設(shè)為堆頂元素），然后遍歷300萬(wàn)的Query，分別和根元素Kmin進(jìn)行對(duì)比比較（如上第2節(jié)思路3所述，若X>Kmin，則更新并調(diào)整堆，否則，不更新），我們最終的時(shí)間復(fù)雜度是：O（N） + N'*O（logK），（N為1000萬(wàn)，N’為300萬(wàn)）。ok，更多，詳情，請(qǐng)參考原文。
或者：采用trie樹，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個(gè)元素的最小推來(lái)對(duì)出現(xiàn)頻率進(jìn)行排序。
ok，本章里，咱們來(lái)實(shí)現(xiàn)這個(gè)問題，為了降低實(shí)現(xiàn)上的難度，假設(shè)這些記錄全部是一些英文單詞，即用戶在搜索框里敲入一個(gè)英文單詞，然后查詢搜索結(jié)果，最后，要你統(tǒng)計(jì)輸入單詞中頻率最大的前K個(gè)單詞。ok，復(fù)雜問題簡(jiǎn)單化了之后，編寫代碼實(shí)現(xiàn)也相對(duì)輕松多了，畫的簡(jiǎn)單示意圖（繪制者，yansha），如下：
完整源碼：
程序測(cè)試：咱們接下來(lái)，來(lái)對(duì)下面的通過(guò)用戶輸入單詞后，搜索引擎記錄下來(lái)，“大量”單詞記錄進(jìn)行統(tǒng)計(jì)（同時(shí)，令K=10，即要你找出10個(gè)最熱門查詢的單詞）：
運(yùn)行結(jié)果：根據(jù)程序的運(yùn)行結(jié)果，可以看到，搜索引擎記錄下來(lái)的查詢次數(shù)最多的10個(gè)單詞為（注，并未要求這10個(gè)數(shù)要有序輸出）：in（312次），it（384次），a（432），that（456），MPQ（408），of（504），and（624），is（456），the（1008），to（936）。
3.2、統(tǒng)計(jì)出現(xiàn)次數(shù)最多的數(shù)據(jù)
題目描述：
給你上千萬(wàn)或上億數(shù)據(jù)（有重復(fù)），統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)。
分析：上千萬(wàn)或上億的數(shù)據(jù)，現(xiàn)在的機(jī)器的內(nèi)存應(yīng)該能存下（也許可以，也許不可以）。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來(lái)進(jìn)行統(tǒng)計(jì)次數(shù)。然后就是取出前N個(gè)出現(xiàn)次數(shù)最多的數(shù)據(jù)了。當(dāng)然，也可以堆實(shí)現(xiàn)。
ok，此題與上題類似，最好的方法是用hash_map統(tǒng)計(jì)出現(xiàn)的次數(shù)，然后再借用堆找出出現(xiàn)次數(shù)最多的N個(gè)數(shù)據(jù)。不過(guò)，上一題統(tǒng)計(jì)搜索引擎最熱門的查詢已經(jīng)采用過(guò)hash表統(tǒng)計(jì)單詞出現(xiàn)的次數(shù)，特此，本題咱們改用紅黑樹取代之前的用hash表，來(lái)完成最初的統(tǒng)計(jì)，然后用堆更新，找出出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)。
同時(shí)，正好個(gè)人此前用c && c++ 語(yǔ)言實(shí)現(xiàn)過(guò)紅黑樹，那么，代碼能借用就借用吧。
完整代碼：
程序測(cè)試：咱們來(lái)對(duì)下面這個(gè)小文件進(jìn)行測(cè)試：
運(yùn)行結(jié)果：如下圖所示，
問題補(bǔ)遺：
ok，由于在遍歷紅黑樹采用的是遞歸方式比較耗內(nèi)存，下面給出一個(gè)非遞歸遍歷的程序（下述代碼若要運(yùn)行，需貼到上述程序之后，因?yàn)槠渌拇a未變，只是在遍歷紅黑樹的時(shí)候，采取非遞歸遍歷而已，同時(shí)，主函數(shù)的編寫也要稍微修改下）：
updated：
后來(lái)，我們狂想曲創(chuàng)作組中的3又用hash+堆實(shí)現(xiàn)了上題，很明顯比采用上面的紅黑樹，整個(gè)實(shí)現(xiàn)簡(jiǎn)潔了不少，其完整源碼如下：
完整源碼：
程序測(cè)試：對(duì)65047kb的數(shù)據(jù)量文件，進(jìn)行測(cè)試統(tǒng)計(jì)（不過(guò)，因其數(shù)據(jù)量實(shí)在太大，半天沒打開）：
運(yùn)行結(jié)果：如下，
第四節(jié)、海量數(shù)據(jù)處理問題一般總結(jié)
關(guān)于海量數(shù)據(jù)處理的問題，一般有Bloom filter，Hashing，bit-map，堆，trie樹等方法來(lái)處理。更詳細(xì)的介紹，請(qǐng)查看此文：十道海量數(shù)據(jù)處理面試題與十個(gè)方法大總結(jié)。
余音
反饋：此文發(fā)布后，走進(jìn)搜索引擎的作者&&深入搜索引擎-海量信息的壓縮、索引和查詢的譯者，梁斌老師，對(duì)此文提了點(diǎn)意見，如下：1、首先TopK問題，肯定需要有并發(fā)的，否則串行搞肯定慢，IO和計(jì)算重疊度不高。其次在IO上需要一些技巧，當(dāng)然可能只是驗(yàn)證算法，在實(shí)踐中IO的提升會(huì)非常明顯。最后上文的代碼可讀性雖好，但機(jī)器的感覺可能就會(huì)差，這樣會(huì)影響性能。2、同時(shí)，TopK可以看成從地球上選拔k個(gè)跑的最快的，參加奧林匹克比賽，各個(gè)國(guó)家自行選拔，各個(gè)大洲選拔，層層選拔，最后找出最快的10個(gè)。發(fā)揮多機(jī)多核的優(yōu)勢(shì)。
預(yù)告：程序員面試題狂想曲、第四章，本月月底之前發(fā)布（盡最大努力）。
修訂
程序員面試題狂想曲-tctop（the crazy thingking of programers）的修訂wiki（http://tctop./）已于今天建立，我們急切的想得到讀者的反饋，意見，建議，以及更好的思路，算法，和代碼優(yōu)化的建議。所以，
- 如果你發(fā)現(xiàn)了狂想曲系列中的任何一題，任何一章（http:///hgVPmH）中的錯(cuò)誤，問題，與漏洞，歡迎告知給我們，我們將感激不盡，同時(shí)，免費(fèi)贈(zèng)送本blog內(nèi)的全部博文集錦的CHM文件1期；
- 如果你能對(duì)狂想曲系列的創(chuàng)作提供任何建設(shè)性意見，或指導(dǎo)，歡迎反饋給我們，并真誠(chéng)邀請(qǐng)您加入到狂想曲的wiki修訂工作中；
- 如果你是編程高手，對(duì)狂想曲的任何一章有自己更好的思路，或算法，歡迎加入狂想曲的創(chuàng)作組，以為千千萬(wàn)萬(wàn)的讀者創(chuàng)造更多的價(jià)值，更好的服務(wù)。
Ps：狂想曲tctop的wiki修訂地址為：http://tctop./。歡迎圍觀，更歡迎您加入到狂想曲的創(chuàng)作或wiki修訂中。
聯(lián)系July
·email，zhoulei0907@yahoo.cn
·blog，http://blog.csdn.net/v_JULY_v 。
·weibo，http://weibo.com/julyweibo 。
作者按：有任何問題，或建議，歡迎以上述聯(lián)系方式call me，真誠(chéng)的謝謝各位。
July、狂想曲創(chuàng)作組，二零一一年五月十日。
版權(quán)所有，本人對(duì)本blog內(nèi)所有任何內(nèi)容享有版權(quán)及著作權(quán)。實(shí)要轉(zhuǎn)載，請(qǐng)以鏈接形式注明出處。
|
