從一道筆試題談算法優(yōu)化-

1、從一道筆試題談算法優(yōu)化引子每年十一月各大IT公司都不約而同、爭后恐后地到各大高校進行全國巡回招聘。與此同時,網(wǎng)上也開始出現(xiàn)大量筆試面試題;網(wǎng)上流傳的題目往往都很精巧,既能讓考查基礎知識,又在平淡中隱含了廣闊的天地供優(yōu)秀學生馳騁。這兩天在網(wǎng)上淘到一道筆試題目(注1,雖然真假未知,但的確是道好題,題目如下:從10億個浮點數(shù)中找出最大的1萬個。這是一道似易實難的題目,一般同學最容易中的陷阱就是沒有重視這個“億”字。因為有10億個單精度浮點數(shù)元素的數(shù)組在32位平臺上已經(jīng)達到3.7GB之巨,在常見計算機平臺(如Win32上聲明一個這樣的數(shù)組將導致堆棧溢出。正確的解決方法是分治法,比如每次處理100萬個數(shù)

2、,然后再綜合起來。不過這不是本文要討論的主旨,所以本文把上題的10億改為1億,把浮點數(shù)改為整數(shù),這樣可以直接地完成這個問題,有利于清晰地討論相關算法的優(yōu)化(注2。不假思索拿到這道題,馬上就會想到的方法是建立一個數(shù)組把1億個數(shù)裝起來,然后用for循環(huán)遍歷這個數(shù)組,找出最大的1萬個數(shù)來。原因很簡單,因為如果要找出最大的那個數(shù),就是這樣解決的;而找最大的1萬個數(shù),只是重復1萬遍而已。template< class T >void solution_1( T BigArr, T ResArr for( int i = 0; i < RES_ARR_SIZE; +i int idx =

3、 i;for( int j = i+1; j < BIG_ARR_SIZE; +j if( BigArrj > BigArridx idx = j;ResArri = BigArridx;std:swap( BigArridx, BigArri ;設BIG_ARR_SIZE =1億,RES_ARR_SIZE = 1萬,運行以上算法已經(jīng)超過40分鐘(注3,遠遠超過我們的可接受范圍。稍作思考從上面的代碼可以看出跟SelectSort算法的核心代碼是一樣的。因為SelectSort是一個O(n2的算法(solution_1的時間復雜度為O(n*m,因為solution_1沒有將整個大數(shù)組

4、全部排序,而我們又知道排序算法可以優(yōu)化到O(nlogn,那們是否可以從這方面入手使用更快的排序算法如MergeSor、QuickSort呢?但這些算法都不具備從大至小選擇最大的N個數(shù)的功能,因此只有將1億個數(shù)按從大到小用QuickSort排序,然后提取最前面的1萬個。template< class T, class I >void solution_2( T BigArr, T ResArr std:sort( BigArr, BigArr + BIG_ARR_SIZE, std:greater_equal( ;memcpy( ResArr, BigArr, sizeof(T *

5、RES_ARR_SIZE ;因為STL里的sort算法使用的是QuickSort,在這里直接拿來用了,是因為不想寫一個寫一個眾人皆知的QuickSort代碼來占篇幅(而且STL的sort高度優(yōu)化、速度快。對solution_2進行測試,運行時間是32秒,約為solution_1的1.5%的時間,已經(jīng)取得了幾何數(shù)量級的進展。深入思考壓抑住興奮回頭再仔細看看solution_2,你將發(fā)現(xiàn)一個大問題,那就是在solution_2里所有的元素都排序了!而事實上只需找出最大的1萬個即可,我們不是做了很多無用功嗎?應該怎么樣來消除這些無用功?如果你一時沒有頭緒,那就讓我慢慢引導你。首先,發(fā)掘一個事實:如果

6、這個大數(shù)組本身已經(jīng)按從大到小有序,那么數(shù)組的前1萬個元素就是結果;然后,可以假設這個大數(shù)組已經(jīng)從大到小有序,并將前1萬個元素放到結果數(shù)組;再次,事實上這結果數(shù)組里放的未必是最大的一萬個,因此需要將前1萬個數(shù)字后續(xù)的元素跟結果數(shù)組的最小的元素比較,如果所有后續(xù)的元素都比結果數(shù)組的最小元素還小,那結果數(shù)組就是想要的結果,如果某一后續(xù)的元素比結果數(shù)組的最小元素大,那就用它替換結果數(shù)組里最小的數(shù)字;最后,遍歷完大數(shù)組,得到的結果數(shù)組就是想要的結果了。template< class T >void solution_3( T BigArr, T ResArr /取最前面的一萬個memcpy(

7、 ResArr, BigArr, sizeof(T * RES_ARR_SIZE ;/標記是否發(fā)生過交換bool bExchanged = true;/遍歷后續(xù)的元素for( int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; +i int idx;/如果上一輪發(fā)生過交換if( bExchanged /找出ResArr中最小的元素int j;for( idx = 0, j = 1; j < RES_ARR_SIZE; +j if( ResArridx > ResArrj idx = j;/這個后續(xù)元素比ResArr中最小的元素大,則替換。if( B

8、igArri > ResArridx bExchanged = true;ResArridx = BigArri;elsebExchanged = false;上面的代碼使用了一個布爾變量bExchanged標記是否發(fā)生過交換,這是一個前文沒有談到的優(yōu)化手段用以標記元素交換的狀態(tài),可以大大減少查找ResArr中最小元素的次數(shù)。也對solution_3進行測試一下,結果用時2.0秒左右(不使用bExchanged則高達32分鐘,遠小于solution_2的用時。深思熟慮在進入下一步優(yōu)化之前,分析一下solution_3的成功之處。第一、solution_3的算法只遍歷大數(shù)組一次,即它是一個

9、O(n的算法,而solution_1是O(n*m的算法,solution_2是O(nlogn的算法,可見它在本質(zhì)上有著天然的優(yōu)越性;第二、在solution_3中引入了bExchanged這一標志變量,從測試數(shù)據(jù)可見引入bExchanged減少了約99.99%的時間,這是一個非常大的成功。上面這段話絕非僅僅說明了solution_3的優(yōu)點,更重要的是把solution_3的主要矛盾擺上了桌面為什么一個O(n的算法效率會跟O(n*m的算法差不多(不使用bExchanged?為什么使用了bExchanged能夠減少99.99%的時間?帶著這兩個問題再次審視solution_3的代碼,發(fā)現(xiàn)bExch

10、anged的引入實際上減少了如下代碼段的執(zhí)行次數(shù):for( idx = 0, j = 1; j < RES_ARR_SIZE; +j if( ResArridx > ResArrj idx = j;上面的代碼段即是查找ResArr中最小元素的算法,分析它可知這是一個O(n的算法,到此時就水落石出了!原來雖然solution_3是一個O(n的算法,但因為內(nèi)部使用的查找最小元素的算法也是O(n的算法,所以就退化為O(n*m的算法了。難怪不使用bExchanged使用的時間跟solution_1差不多;這也從反面證明了solution_3被上面的這一代碼段導致性能退化。使用了bExcha

11、nged之后因為減少了很多查找最小元素的代碼段執(zhí)行,所以能夠節(jié)省99.99%的時間!至此可知元兇就是查找最小元素的代碼段,但查找最小元素是必不可少的操作,在這個兩難的情況下該怎么去優(yōu)化呢?答案就是保持結果數(shù)組(即ResArr有序,那樣的話最小的元素總是最后一個,從而省去查找最小元素的時間,解決上面的問題。但這也引入了一個新的問題:保持數(shù)組有序的插入算法的時間復雜度是O(n的,雖然在這個問題里插入的數(shù)次比例較小,但因為基數(shù)太大(1億,這一開銷仍然會令本方案得不償失。難道就沒有辦法了嗎?記得小學解應用題時老師教導過我們?nèi)绻忸}沒有思路,那就多讀幾遍題目。再次審題,注意到題目并沒有要求找到的最大的1

12、萬個數(shù)要有序(注4,這意味著可以通過如下算法來解決:1將BigArr的前1萬個元素復制到ResArr并用QuickSort使ResArr有序,并定義變量MinElemIdx保存最小元素的索引,并定義變量ZoneBeginIdx保存可能發(fā)生交換的區(qū)域的最小索引;2遍歷BigArr其它的元素,如果某一元素比ResArr最小元素小,則將ResArr中MinElemIdx指向的元素替換,如果ZoneBeginIdx = MinElemIdx則擴展ZoneBeginIdx;3重新在ZoneBeginIdx至RES_ARR_SIZE元素段中尋找最小元素,并用MinElemIdx 保存其它索引;4重復2直至

13、遍歷完所有BigArr的元素。依上算法,寫代碼如下:template< class T, class I >void solution_4( T BigArr, T ResArr /取最前面的一萬個memcpy( ResArr, BigArr, sizeof(T * RES_ARR_SIZE ;/排序std:sort( ResArr, ResArr + RES_ARR_SIZE, std:greater_equal( ;/最小元素索引unsigned int MinElemIdx = RES_ARR_SIZE - 1;/可能產(chǎn)生交換的區(qū)域的最小索引unsigned int Zone

14、BeginIdx = MinElemIdx;/遍歷后續(xù)的元素for( unsigned int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; +i /這個后續(xù)元素比ResArr中最小的元素大,則替換。if( BigArri > ResArrMinElemIdx ResArrMinElemIdx = BigArri;if( MinElemIdx = ZoneBeginIdx -ZoneBeginIdx;/查找最小元素unsigned int idx = ZoneBeginIdx;unsigned int j = idx + 1;for( ; j < R

15、ES_ARR_SIZE; +j if( ResArridx > ResArrj idx = j;MinElemIdx = idx;經(jīng)過測試,同樣情況下solution_4用時約1.8秒,較solution_3效率略高,總算不負一番努力。這次優(yōu)化從solution_4產(chǎn)生的輸出來入手。把solution_4的輸出寫到文件,查看后發(fā)現(xiàn)數(shù)組基本無序了。這說明在程序運行一定時間后,頻繁的替換幾乎將原本有序的結果數(shù)組全部換血。結果數(shù)組被替換的元素越多,查找最小元素要遍歷的范圍就越大,當被替換的元素個數(shù)接近結果數(shù)組的大小時,solution_4就退化成solution_3。因為solution_4很

16、快退化也就直接導致它的效率沒有本質(zhì)上的提高。找出了原因,就應該找出一個解決的辦法。通過上面的分析,知道solution_3和solution_4最消耗時間的是查找最小元素這一操作,將它減少(或去除才有可能從本質(zhì)上提高效率。這樣思路又回到保持結果數(shù)組有序這一條老路上來。在上一節(jié)我們談到保持數(shù)組有序的插入算法將帶來大量的元素移動,頻繁的插入操作將使這一方法在效率上得不償失。有沒有辦法讓元素移動去掉呢?答案也是有的那就是使用鏈表。這時新的問題又來了,鏈表因為是非隨機存取數(shù)據(jù)結構,插入前尋找位置的算法又是O(n的。解決新的問題的答案是使用AVL 樹,但AVL樹雖然插入和查找都是O(logn,可是需要在

17、插入后進行調(diào)整保持平衡,這又是一個耗費大量時間的操作。分析到現(xiàn)在,發(fā)現(xiàn)我們像進了迷宮,左沖右突都找不到突破口。現(xiàn)在請靜下來想一想,如果思考結果沒有跳出上面這個怪圈,那我不幸地告訴你:你被我誤導了。這個故意的誤導是要告誡大家:進行算法優(yōu)化必須時刻保持自己頭腦清醒,否則時刻都有可能陷入這樣的迷宮當中。現(xiàn)在跳出這個怪圈重新思考,根據(jù)前文的分析,可知目標是減少(或去除查找最小元素的操作次數(shù)(或查找時間,途徑是讓ResArr保持有序,難點在于給ResArr排序太費時。反過來想一想,是否需要時刻保持ResArr有序?答案為否,因為當查找最小元素需要遍歷的范圍較小時,速度還是很快的,這樣就犯不著在每替換一個

18、元素的時候都排序一次,而僅需要在無序元素較多的時候適時地排序即可(即保持查找最小元素要遍歷的范圍較小。這個思想有用嗎?寫代碼來測試一下:template< class T, class I >void solution_5( T BigArr, T ResArr /同solution_4,略/這個后續(xù)元素比ResArr中最小的元素大,則替換。if( BigArri > ResArrMinElemIdx ResArrMinElemIdx = BigArri;if( MinElemIdx = ZoneBeginIdx -ZoneBeginIdx;/太多雜亂元素的時候排序if( Z

19、oneBeginIdx < 9400 std:sort( ResArr, ResArr + RES_ARR_SIZE, std:greater( ;ZoneBeginIdx = MinElemIdx = RES_ARR_SIZE - 1;continue;/同solution_4,略代碼中的9400是經(jīng)過試驗得出的最好數(shù)值,即在有600個元素無序的時候進行一次排序。測試的結果令人驚喜,用時僅400毫秒左右,約為solution_4的五分之一,這也證明了上述思想是正確的。殫思極慮 腳步永遠向前，在取得 solution_5 這樣的成果之后，仍然有必要分析和優(yōu)化它。對這一 看似已經(jīng)完美的算法

20、進行下一次優(yōu)化要從哪里著手？這時候要借助于性能剖分工具了， 常用 的有 Intel 的 VTune 以及 Microsoft Visual C+自帶的 profile 等。 使用 MS profile 對 solution_5 分析產(chǎn)生的報告如下（略去一些無關數(shù)據(jù)）： Func Func+Child Hit Time % Time % Count Function -37.718 1.0 3835.317 99.5 1 _main (algo.obj 111.900 2.9 3220.082 83.6 1 solution_5(int * . 0.000 0.0 3074.063 79.8 1

21、12 _STL:sort(int *,. 可以發(fā)現(xiàn) sort 函數(shù)的調(diào)用用去了將近 80%的時間，這表明 sort 函數(shù)是問題所在，優(yōu)化 應該從這里著手。但正如前文所說，STL 的 sort 已經(jīng)高度優(yōu)化速度很快了，再對他作優(yōu)化是 極難的；而且 sort 函數(shù)里又調(diào)用了其它 STL 內(nèi)部函數(shù)，如蛛絲般牽來繞去，讀得懂已經(jīng)不 是一般人可完成的了，優(yōu)化從何談起？ 我們不能左右天氣，但我們可以左右心情；我們不能修改 sort 函數(shù)，但我們可以控制 sort 的調(diào)用。再看看 solution_5 里對 sort 的調(diào)用有沒有什么蛛絲馬跡可尋： std:sort( ResArr, ResArr + RE

22、S_ARR_SIZE, std:greater( ; 這個調(diào)用是把結果數(shù)組 ResArr 重新排序一遍。 需要把整個 ResArr 完全重新排序嗎？答 案是需要的，但可以不使用這個方法。因為 ResArr 里的元素絕大部分是有序的（結合上文 可知前面 94%的元素都有序），待排序的只是 6%。只要把這 600 個數(shù)據(jù)重新排序然后將前 后兩個有序數(shù)組歸并為一個有序數(shù)組即可（歸并算法的時間復雜度為 O(n+m），將因為排 序的數(shù)據(jù)量較少而大大節(jié)約時間。寫代碼如下： template< class T, class I > void solution_6( T BigArr, T Res

23、Arr /同 solution_5，略 /太多雜亂元素的時候排序 if( ZoneBeginIdx < 9400 std:sort( ResArr + 9400, ResArr + RES_ARR_SIZE, std:greater( ; std:merge(ResArr, ResArr + 9400, ResArr + 9400, ResArr + RES_ARR_SIZE, BigArr, std:greater( ; memcpy( ResArr, BigArr, sizeof(T * RES_ARR_SIZE ; /同 solution_5，略 經(jīng)測試， solutio_6 的運行時間為 250 毫秒左右， solution_5 快了將近一半， 比 通過 profile 分析報告計算 sort 函數(shù)和 merge 函數(shù)的占用時間總計約為執(zhí)行時間的 19.6%，遠小于 solution_5 的占用時間。 結束語 一番努力之后， 終于將一個原來需要近一個小時才能解決的問題用 250 毫秒完成， 文章 到這里要完結，不過上述算法仍有可優(yōu)化的余地，這就要讀者朋友自己去挖掘了。我希望看 到這篇文章的人不僅僅是贊嘆算法的奇妙， 更希望能夠?qū)W會算法優(yōu)化的方法和技巧。 對于算 法優(yōu)化的方法，我總結如下（僅供參考及拋磚引玉之用）： 不斷地否定自己的方法全文 減少重