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

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

2、00萬個數(shù)，然后再綜合起來。不過這不是本文要討論的主旨，所以本文把上題的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 )i

3、nt idx = 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萬，運行以上算法已經超過40分鐘（注3），遠遠超過我們的可接受范圍。稍作思考從上面的代碼可以看出跟SelectSort算法的核心代碼是一樣的。因為SelectSort是一個O(n2)的算法（solutio

4、n_1的時間復雜度為O(n*m)，因為solution_1沒有將整個大數(shù)組全部排序），而我們又知道排序算法可以優(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_equ

5、al() ); memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE ); 因為STL里的sort算法使用的是QuickSort，在這里直接拿來用了，是因為不想寫一個寫一個眾人皆知的QuickSort代碼來占篇幅（而且STL的sort高度優(yōu)化、速度快）。對solution_2進行測試，運行時間是32秒，約為solution_1的1.5%的時間，已經取得了幾何數(shù)量級的進展。深入思考壓抑住興奮回頭再仔細看看solution_2，你將發(fā)現(xiàn)一個大問題，那就是在solution_2里所有的元素都排序了！而事實上只需找出最大的1萬個即可，我們

6、不是做了很多無用功嗎？應該怎么樣來消除這些無用功？如果你一時沒有頭緒，那就讓我慢慢引導你。首先，發(fā)掘一個事實：如果這個大數(shù)組本身已經按從大到小有序，那么數(shù)組的前1萬個元素就是結果；然后，可以假設這個大數(shù)組已經從大到小有序，并將前1萬個元素放到結果數(shù)組；再次，事實上這結果數(shù)組里放的未必是最大的一萬個，因此需要將前1萬個數(shù)字后續(xù)的元素跟結果數(shù)組的最小的元素比較，如果所有后續(xù)的元素都比結果數(shù)組的最小元素還小，那結果數(shù)組就是想要的結果，如果某一后續(xù)的元素比結果數(shù)組的最小元素大，那就用它替換結果數(shù)組里最小的數(shù)字；最后，遍歷完大數(shù)組，得到的結果數(shù)組就是想要的結果了。template< class T

7、 >void solution_3( T BigArr, T ResArr )/取最前面的一萬個memcpy( 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 &l

8、t; RES_ARR_SIZE; +j )if( ResArridx > ResArrj )idx = j; /這個后續(xù)元素比ResArr中最小的元素大，則替換。if( BigArri > ResArridx )bExchanged = true; ResArridx = BigArri; elsebExchanged = false; 上面的代碼使用了一個布爾變量bExchanged標記是否發(fā)生過交換，這是一個前文沒有談到的優(yōu)化手段用以標記元素交換的狀態(tài)，可以大大減少查找ResArr中最小元素的次數(shù)。也對solution_3進行測試一下，結

9、果用時2.0秒左右（不使用bExchanged則高達32分鐘），遠小于solution_2的用時。深思熟慮在進入下一步優(yōu)化之前，分析一下solution_3的成功之處。第一、solution_3的算法只遍歷大數(shù)組一次，即它是一個O(n)的算法，而solution_1是O(n*m)的算法，solution_2是O(nlogn)的算法，可見它在本質上有著天然的優(yōu)越性；第二、在solution_3中引入了bExchanged這一標志變量，從測試數(shù)據可見引入bExchanged減少了約99.99%的時間，這是一個非常大的成功。上面這段話絕非僅僅說明了solution_3的優(yōu)點，更重要的是把soluti

10、on_3的主要矛盾擺上了桌面為什么一個O(n)的算法效率會跟O(n*m)的算法差不多（不使用bExchanged）？為什么使用了bExchanged能夠減少99.99%的時間？帶著這兩個問題再次審視solution_3的代碼，發(fā)現(xiàn)bExchanged的引入實際上減少了如下代碼段的執(zhí)行次數(shù)：for( idx = 0, j = 1; j < RES_ARR_SIZE; +j )if( ResArridx > ResArrj )idx = j; 上面的代碼段即是查找ResArr中最小元素的算法，分析它可知這是一個O(n)的算法，到此時就水落石出了！原來雖然solution_3是

11、一個O(n)的算法，但因為內部使用的查找最小元素的算法也是O(n)的算法，所以就退化為O(n*m)的算法了。難怪不使用bExchanged使用的時間跟solution_1差不多；這也從反面證明了solution_3被上面的這一代碼段導致性能退化。使用了bExchanged之后因為減少了很多查找最小元素的代碼段執(zhí)行，所以能夠節(jié)省99.99%的時間！至此可知元兇就是查找最小元素的代碼段，但查找最小元素是必不可少的操作，在這個兩難的情況下該怎么去優(yōu)化呢？答案就是保持結果數(shù)組（即ResArr）有序，那樣的話最小的元素總是最后一個，從而省去查找最小元素的時間，解決上面的問題。但這也引入了一個新的問題：保

12、持數(shù)組有序的插入算法的時間復雜度是O(n)的，雖然在這個問題里插入的數(shù)次比例較小，但因為基數(shù)太大（1億），這一開銷仍然會令本方案得不償失。難道就沒有辦法了嗎？記得小學解應用題時老師教導過我們如果解題沒有思路，那就多讀幾遍題目。再次審題，注意到題目并沒有要求找到的最大的1萬個數(shù)要有序（注4），這意味著可以通過如下算法來解決：1) 將BigArr的前1萬個元素復制到ResArr并用QuickSort使ResArr有序，并定義變量MinElemIdx保存最小元素的索引，并定義變量ZoneBeginIdx保存可能發(fā)生交換的區(qū)域的最小索引；2) 遍歷BigArr其它的元素，如果某一元素比ResArr最小

13、元素小，則將ResArr中MinElemIdx指向的元素替換，如果ZoneBeginIdx = MinElemIdx則擴展ZoneBeginIdx；3) 重新在ZoneBeginIdx至RES_ARR_SIZE元素段中尋找最小元素，并用MinElemIdx保存其它索引；4) 重復2)直至遍歷完所有BigArr的元素。依上算法，寫代碼如下：template< class T, class I >void solution_4( T BigArr, T ResArr )/取最前面的一萬個memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE )

14、; /排序std:sort( ResArr, ResArr + RES_ARR_SIZE, std:greater_equal() ); /最小元素索引unsigned int MinElemIdx = RES_ARR_SIZE - 1; /可能產生交換的區(qū)域的最小索引 unsigned int ZoneBeginIdx = 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;