從一道筆試題談算法優(yōu)化_百度文庫(kù)概要

1、從一道筆試題談算法優(yōu)化（上作者:賴(lài)勇浩（http:/blog.csd n.n et/la nphaday引子每年十一月各大IT公司都不約而同、爭(zhēng)后恐后地到各大高校進(jìn)行全國(guó)巡回招 聘。與此同時(shí)，網(wǎng)上也開(kāi)始出現(xiàn)大量筆試面試題；網(wǎng)上流傳的題目往往都很精巧，既 能讓考查基礎(chǔ)知識(shí)，又在平淡中隱含了廣闊的天地供優(yōu)秀學(xué)生馳騁。這兩天在網(wǎng)上淘到一道筆試題目（注1，雖然真假未知，但的確是道好題，題目如 下:從10億個(gè)浮點(diǎn)數(shù)中找出最大的1萬(wàn)個(gè)。這是一道似易實(shí)難的題目，一般同學(xué)最容易中的陷阱就是沒(méi)有重視這個(gè)億”字。因?yàn)橛?0億個(gè)單精度浮點(diǎn)數(shù)元素的數(shù)組在 32位平臺(tái)上已經(jīng)達(dá)到3.7GB之巨， 在常見(jiàn)計(jì)算機(jī)平臺(tái)（如Wi

2、n32上聲明一個(gè)這樣的數(shù)組將導(dǎo)致堆棧溢出。正確的解決 方法是分治法，比如每次處理100萬(wàn)個(gè)數(shù)，然后再綜合起來(lái)。不過(guò)這不是本文要討論 的主旨，所以本文把上題的10億改為1億，把浮點(diǎn)數(shù)改為整數(shù)，這樣可以直接地完成 這個(gè)問(wèn)題,有利于清晰地討論相關(guān)算法的 優(yōu)化（注2。不假思索拿到這道題，馬上就會(huì)想到的方法是建立一個(gè)數(shù)組把1億個(gè)數(shù)裝起來(lái)，然后用for循環(huán)遍歷 這個(gè)數(shù)組,找出最大的1萬(wàn)個(gè)數(shù)來(lái)。原因很簡(jiǎn)單，因?yàn)槿绻页鲎畲蟮?那個(gè)數(shù),就是這樣 解決的;而找最大的1萬(wàn)個(gè)數(shù),只是重復(fù)1萬(wàn)遍而已。templatev class T >void solution_1（ T BigArr, T ResArrf

3、or( int i = 0; i < RES_ARR_SIZE; +iin tidx = i;for( int j = i+1; j < BIG_ARR_SIZE; +jif( BigArrj >BigArridxidx = j;ResArri = BigArridx;std:swap( BigArridx, BigArri;設(shè)BIG_ARR_SIZE =1億，RES_ARR_SIZE = 1萬(wàn)，運(yùn)行以上算法已經(jīng)超過(guò) 40分 鐘(注 3 ,遠(yuǎn)遠(yuǎn)超過(guò)我們的可接受范圍。稍作思考從上面的代碼可以看出跟SelectSort算法的核心代碼是一樣的。因?yàn)镾electSort是一個(gè)0(n2

4、的算法(solution_1的時(shí)間復(fù)雜度為0(n*m,因?yàn)閟olution_1沒(méi)有將整個(gè) 大數(shù)組全部排序，而我們又知道排序算法可以?xún)?yōu)化到 0(nlogn,那們是否可以從這方 面入手使用更快的排序算法如MergeSor、QuickSort呢?但這些算法都不具備從大 至小選擇最大的N個(gè)數(shù)的功能，因此只有將1億個(gè)數(shù)按從大到小用QuickSort排序， 然后提取最前面的1萬(wàn)個(gè)。templatev class T, class I >void solution_2( T BigArr, T ResArrstd:sort( BigArr, BigArr + BIG_ARR_SIZE, std:gre

5、ater_equal(;memcpy( ResArr, BigArr, sizeof(T * RES_ARR_SIZE ;因?yàn)镾TL里的sort算法使用的是Quicksort ,在這里直接拿來(lái)用了 ,是因?yàn)椴幌?寫(xiě)一個(gè)寫(xiě)一個(gè)眾人皆知的QuickSort代碼來(lái)占篇幅(而且STL的sort高度優(yōu)化、速 度快。對(duì)solution_2進(jìn)行測(cè)試，運(yùn)行時(shí)間是32秒，約為solution_1的1.5%的時(shí)間，已經(jīng)取 得了幾何數(shù)量級(jí)的進(jìn)展。深入思考?jí)阂肿∨d奮回頭再仔細(xì)看看solution_2,你將發(fā)現(xiàn)一個(gè)大問(wèn)題,那就是在 solution_2里所有的元素都排序了 ！而事實(shí)上只需找出最大的1萬(wàn)個(gè)即可,我們不是

6、做了很多無(wú)用功嗎？應(yīng)該怎么樣來(lái)消除這些無(wú)用功？如果你一時(shí)沒(méi)有頭緒，那就讓我慢慢引導(dǎo)你。首先,發(fā)掘一個(gè)事實(shí):如果這個(gè)大數(shù)組本身已經(jīng)按從大到小有序，那么數(shù)組的前1萬(wàn)個(gè)元素就是結(jié)果；然后,可以假設(shè)這個(gè)大 數(shù)組已經(jīng)從 大到小有序，并將前1萬(wàn)個(gè)元素放到結(jié)果數(shù)組；再次,事實(shí)上這結(jié)果數(shù)組 里放的未必是最大 的一萬(wàn)個(gè)，因此需要將前1萬(wàn)個(gè)數(shù)字后續(xù)的元素跟結(jié)果數(shù)組的最 小的元素比較，如果所有后 續(xù)的元素都比結(jié)果數(shù)組的最小元素還小，那結(jié)果數(shù)組就 是想要的結(jié)果，如果某一后續(xù)的元素比結(jié)果數(shù)組的最小元素大，那就用它替換結(jié)果數(shù) 組里最小的數(shù)字；最后,遍歷完大數(shù)組，得到的結(jié)果數(shù)組就是想要的結(jié)果了。templatev clas

7、s T >void solution_3( T BigArr, T ResArr/取最前面的一萬(wàn)個(gè)memcpy( ResArr, BigArr, sizeof(T * RES_ARR_SIZE ;/標(biāo)記是否發(fā)生過(guò)交換boolbExcha nged = true;/遍歷后續(xù)的元素for( int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; +iin tidx;/如果上一輪發(fā)生過(guò)交換if( bExcha nged/找出ResArr中最小的元素int j;for( idx = 0, j = 1; j < RES_ARR_SIZE; +jif( ResAr

8、ridx >ResArrjidx = j;/這個(gè)后續(xù)元素比ResArr中最小的元素大，則替換。if( BigArri >ResArridxbExcha nged = true;ResArridx = BigArri;elsebExcha nged = false;上面的代碼使用了一個(gè)布爾變量 bExchanged標(biāo)記是否發(fā)生過(guò)交換，這是一個(gè)前 文沒(méi)有談到 的優(yōu)化手段一一用以標(biāo)記元素交換的狀態(tài)，可以大大減少查找ResArr 中最小元素的次數(shù)。也對(duì)solution_3進(jìn)行測(cè)試一下,結(jié)果用時(shí)2.0秒左右(不使用bExchanged則高達(dá)32分鐘,遠(yuǎn)小于solution_2的用時(shí)。深思熟慮

9、在進(jìn)入下一步優(yōu)化之前，分析一下solution_3的成功之處。第一、solution_3的 算法只遍歷 大數(shù)組一次,即它是一個(gè)0(n的算法,而solution是O(n*m的算法,solution_2是0(nlogn的算法,可見(jiàn)它在本質(zhì)上有著天然的優(yōu)越性；第二、在 solution_3中引入了 bExchanged這一標(biāo)志變量，從測(cè)試數(shù)據(jù)可見(jiàn)引入bExchanged減 少了約99.99%的時(shí)間，這是一個(gè)非常大 的成功。上面這段話(huà)絕非僅僅說(shuō)明了 solution_3的優(yōu)點(diǎn)，更重要的是把solution_3的主要 矛盾擺上了桌面為什么一個(gè)O(n的算法效率會(huì)跟O(n*m的算法差不多(不使用bExcha

10、nged ?為什么使用了 bExchanged能夠減少99.99%的時(shí)間？帶著這兩個(gè)問(wèn) 題再次審視solution_3的代碼，發(fā)現(xiàn)bExchanged的引入實(shí)際上減少了如下代碼段的 執(zhí)行次數(shù)：for( idx = 0, j = 1; j < RES_ARR_SIZE; +jif( ResArridx >ResArrjidx = j;上面的代碼段即是查找ResArr中最小元素的算法，分析它可知這是一個(gè)O(n的 算法，到此時(shí)就水落石出了 ！原來(lái)雖然solution_3是一個(gè)O(n的算法，但因?yàn)閮?nèi)部使用 的查找最小元素的算法也是O(n的算法，所以就退化為O(n*m的算法了。難怪不使 用b

11、Exchanged使用 的時(shí)間跟solution_1差不多;這也從反面證明了 solution_3被上 面的這一代碼段導(dǎo)致性能退化。使用了 bExcha nged之后因?yàn)闇p少了很多查找最小 元素的代碼段執(zhí)行，所以能夠節(jié)省99.99%的時(shí)間！至此可知元兇就是查找最小元素的代碼段，但查找最小元素是必不可少的操作， 在這個(gè)兩難的情況下該怎么去優(yōu)化呢？答案就是保持結(jié)果數(shù)組(即ResArr有序，那樣 的話(huà)最小的元 素總是最后一個(gè)，從而省去查找最小元素的時(shí)間，解決上面的問(wèn)題。但這也引入了一個(gè)新的 問(wèn)題:保持?jǐn)?shù)組有序的插入算法的時(shí)間復(fù)雜度是O(n的,雖然在這個(gè)問(wèn)題里插入的數(shù)次比 例較小,但因?yàn)榛鶖?shù)太大(1億

12、，這一開(kāi)銷(xiāo)仍然會(huì)令本方 案得不償失。難道就沒(méi)有辦法了嗎？記得小學(xué)解應(yīng)用題時(shí)老師教導(dǎo)過(guò)我們?nèi)绻忸}沒(méi)有思路，那就多讀幾 遍題目。再次審題，注意到題目并沒(méi)有要求找到的最大的1萬(wàn)個(gè)數(shù)要有序(注4，這意味著可以通過(guò)如下算法來(lái)解決：1將BigArr的前1萬(wàn)個(gè)元素復(fù)制到 ResArr并用Quicksort使ResArr有序，并定 義變量MinElemldx保存最小元素的索引，并定義變量ZoneBeginldx保存可能發(fā)生 交換的區(qū)域的最小索引；2遍歷BigArr其它的元素,如果某一元素比 ResArr最小元素小,則將ResArr中 MinElemldx指向的元素替換，如果ZoneBeginldx = Mi

13、nElemldx則擴(kuò)展 Zon eBeg inldx ;3重新在ZoneBeginldx至RES_ARR_SIZE元素段中尋找最小元素，并用 MinElemldx保存其它索引;4重復(fù)2直至遍歷完所有BigArr的元素。依上算法，寫(xiě)代碼如下：templatev class T, class I >void solution_4( T BigArr, T ResArr / 取最前面的一萬(wàn)個(gè) memcpy( ResArr, BigArr, sizeof(T * RES_ARR_SlZE ; / 排 序 std:sort( ResArr, ResArr + RES_ARR_SIZE, std:g

14、reater_equal( ; 最小元素索引 un sig ned in tMi nElemldx = RES_ARR_SlZE - 1; /可能產(chǎn)生交換的區(qū)域的最小索引 unsigned intZoneBeginldx = MinElemldx; / 遍歷后續(xù)的元素 for( unsigned int i = RES_ARR_SlZE; i < BIG_ARR_SIZE; +i / 這個(gè)后續(xù)元素比 ResArr 中最小的元素 大，則替換。if( BigArri >ResArrMinElemldx ResArrMinElemldx = BigArri;if( Mi nElemldx = Zon eBegi nldx -Z on