聲明：本文最初發(fā)表于《電腦編程技巧與維護(hù)》2006年第5期，版本所有，如蒙轉(zhuǎn)載，敬請(qǐng)連此聲明一起轉(zhuǎn)載，否則追究侵權(quán)責(zé)任。
從一道筆試題談算法優(yōu)化（上）
作者：賴勇浩（http://blog.csdn.net/lanphaday）
引子
每年十一月各大IT公司都不約而同、爭(zhēng)后恐后地到各大高校進(jìn)行全國(guó)巡回招聘。與此同時(shí)，網(wǎng)上也開始出現(xiàn)大量筆試面試題；網(wǎng)上流傳的題目往往都很精巧，既能讓考查基礎(chǔ)知識(shí)，又在平淡中隱含了廣闊的天地供優(yōu)秀學(xué)生馳騁。
這兩天在網(wǎng)上淘到一道筆試題目（注1），雖然真假未知，但的確是道好題，題目如下：
從10億個(gè)浮點(diǎn)數(shù)中找出最大的1萬個(gè)。
這是一道似易實(shí)難的題目，一般同學(xué)最容易中的陷阱就是沒有重視這個(gè)“億”字。因?yàn)橛?0億個(gè)單精度浮點(diǎn)數(shù)元素的數(shù)組在32位平臺(tái)上已經(jīng)達(dá)到3.7GB之巨，在常見計(jì)算機(jī)平臺(tái)（如Win32）上聲明一個(gè)這樣的數(shù)組將導(dǎo)致堆棧溢出。正確的解決方法是分治法，比如每次處理100萬個(gè)數(shù)，然后再綜合起來。不過這不是本文要討論的主旨，所以本文把上題的10億改為1億，把浮點(diǎn)數(shù)改為整數(shù)，這樣可以直接地完成這個(gè)問題，有利于清晰地討論相關(guān)算法的優(yōu)化（注2）。
不假思索
拿到這道題，馬上就會(huì)想到的方法是建立一個(gè)數(shù)組把1億個(gè)數(shù)裝起來，然后用for循環(huán)遍歷這個(gè)數(shù)組，找出最大的1萬個(gè)數(shù)來。原因很簡(jiǎn)單，因?yàn)槿绻页鲎畲蟮哪莻€(gè)數(shù)，就是這樣解決的；而找最大的1萬個(gè)數(shù)，只是重復(fù)1萬遍而已。
template< class T >
void solution_1( T BigArr[], T ResArr[] )
{
for( int i = 0; i < RES_ARR_SIZE; ++i )
{
int idx = i;
for( int j = i+1; j < BIG_ARR_SIZE; ++j )
{
if( BigArr[j] > BigArr[idx] )
idx = j;
}
ResArr[i] = BigArr[idx];
std::swap( BigArr[idx], BigArr[i] );
}
}
設(shè)BIG_ARR_SIZE ＝ 1億，RES_ARR_SIZE = 1萬，運(yùn)行以上算法已經(jīng)超過40分鐘（注3），遠(yuǎn)遠(yuǎn)超過我們的可接受范圍。
稍作思考
從上面的代碼可以看出跟SelectSort算法的核心代碼是一樣的。因?yàn)镾electSort是一個(gè)O(n^2)的算法（solution_1的時(shí)間復(fù)雜度為O(n*m)，因?yàn)閟olution_1沒有將整個(gè)大數(shù)組全部排序），而我們又知道排序算法可以優(yōu)化到O(nlogn)，那們是否可以從這方面入手使用更快的排序算法如MergeSor、QuickSort呢？但這些算法都不具備從大至小選擇最大的N個(gè)數(shù)的功能，因此只有將1億個(gè)數(shù)按從大到小用QuickSort排序，然后提取最前面的1萬個(gè)。
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) * RES_ARR_SIZE );
}
因?yàn)镾TL里的sort算法使用的是QuickSort，在這里直接拿來用了，是因?yàn)椴幌雽懸粋€(gè)寫一個(gè)眾人皆知的QuickSort代碼來占篇幅（而且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)展。
深入思考
壓抑住興奮回頭再仔細(xì)看看solution_2，你將發(fā)現(xiàn)一個(gè)大問題，那就是在solution_2里所有的元素都排序了！而事實(shí)上只需找出最大的1萬個(gè)即可，我們不是做了很多無用功嗎？應(yīng)該怎么樣來消除這些無用功？
如果你一時(shí)沒有頭緒，那就讓我慢慢引導(dǎo)你。首先，發(fā)掘一個(gè)事實(shí)：如果這個(gè)大數(shù)組本身已經(jīng)按從大到小有序，那么數(shù)組的前1萬個(gè)元素就是結(jié)果；然后，可以假設(shè)這個(gè)大數(shù)組已經(jīng)從大到小有序，并將前1萬個(gè)元素放到結(jié)果數(shù)組；再次，事實(shí)上這結(jié)果數(shù)組里放的未必是最大的一萬個(gè)，因此需要將前1萬個(gè)數(shù)字后續(xù)的元素跟結(jié)果數(shù)組的最小的元素比較，如果所有后續(xù)的元素都比結(jié)果數(shù)組的最小元素還小，那結(jié)果數(shù)組就是想要的結(jié)果，如果某一后續(xù)的元素比結(jié)果數(shù)組的最小元素大，那就用它替換結(jié)果數(shù)組里最小的數(shù)字；最后，遍歷完大數(shù)組，得到的結(jié)果數(shù)組就是想要的結(jié)果了。
template< class T >
void solution_3( T BigArr[], T ResArr[] )
{
//取最前面的一萬個(gè)
memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );
//標(biāo)記是否發(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( ResArr[idx] > ResArr[j] )
idx = j;
}
}
//這個(gè)后續(xù)元素比ResArr中最小的元素大，則替換。
if( BigArr[i] > ResArr[idx] )
{
bExchanged = true;
ResArr[idx] = BigArr[i];
}
else
bExchanged = false;
}
}
上面的代碼使用了一個(gè)布爾變量bExchanged標(biāo)記是否發(fā)生過交換，這是一個(gè)前文沒有談到的優(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í)。
深思熟慮
在進(jìn)入下一步優(yōu)化之前，分析一下solution_3的成功之處。第一、solution_3的算法只遍歷大數(shù)組一次，即它是一個(gè)O(n)的算法，而solution_1是O(n*m)的算法，solution_2是O(nlogn)的算法，可見它在本質(zhì)上有著天然的優(yōu)越性；第二、在solution_3中引入了bExchanged這一標(biāo)志變量，從測(cè)試數(shù)據(jù)可見引入bExchanged減少了約99.99%的時(shí)間，這是一個(gè)非常大的成功。
上面這段話絕非僅僅說明了solution_3的優(yōu)點(diǎn)，更重要的是把solution_3的主要矛盾擺上了桌面——為什么一個(gè)O(n)的算法效率會(huì)跟O(n*m)的算法差不多（不使用bExchanged）？為什么使用了bExchanged能夠減少99.99%的時(shí)間？帶著這兩個(gè)問題再次審視solution_3的代碼，發(fā)現(xiàn)bExchanged的引入實(shí)際上減少了如下代碼段的執(zhí)行次數(shù)：
for( idx = 0, j = 1; j < RES_ARR_SIZE; ++j )
{
if( ResArr[idx] > ResArr[j] )
idx = j;
}
上面的代碼段即是查找ResArr中最小元素的算法，分析它可知這是一個(gè)O(n)的算法，到此時(shí)就水落石出了！原來雖然solution_3是一個(gè)O(n)的算法，但因?yàn)閮?nèi)部使用的查找最小元素的算法也是O(n)的算法，所以就退化為O(n*m)的算法了。難怪不使用bExchanged使用的時(shí)間跟solution_1差不多；這也從反面證明了solution_3被上面的這一代碼段導(dǎo)致性能退化。使用了bExchanged之后因?yàn)闇p少了很多查找最小元素的代碼段執(zhí)行，所以能夠節(jié)省99.99%的時(shí)間！
至此可知元兇就是查找最小元素的代碼段，但查找最小元素是必不可少的操作，在這個(gè)兩難的情況下該怎么去優(yōu)化呢？答案就是保持結(jié)果數(shù)組（即ResArr）有序，那樣的話最小的元素總是最后一個(gè)，從而省去查找最小元素的時(shí)間，解決上面的問題。但這也引入了一個(gè)新的問題：保持?jǐn)?shù)組有序的插入算法的時(shí)間復(fù)雜度是O(n)的，雖然在這個(gè)問題里插入的數(shù)次比例較小，但因?yàn)榛鶖?shù)太大（1億），這一開銷仍然會(huì)令本方案得不償失。
難道就沒有辦法了嗎？記得小學(xué)解應(yīng)用題時(shí)老師教導(dǎo)過我們?nèi)绻忸}沒有思路，那就多讀幾遍題目。再次審題，注意到題目并沒有要求找到的最大的1萬個(gè)數(shù)要有序（注4），這意味著可以通過如下算法來解決：
1) 將BigArr的前1萬個(gè)元素復(fù)制到ResArr并用QuickSort使ResArr有序，并定義變量MinElemIdx保存最小元素的索引，并定義變量ZoneBeginIdx保存可能發(fā)生交換的區(qū)域的最小索引；
2) 遍歷BigArr其它的元素，如果某一元素比ResArr最小元素小，則將ResArr中MinElemIdx指向的元素替換，如果ZoneBeginIdx == MinElemIdx則擴(kuò)展ZoneBeginIdx；
3) 重新在ZoneBeginIdx至RES_ARR_SIZE元素段中尋找最小元素，并用MinElemIdx保存其它索引；
4) 重復(fù)2)直至遍歷完所有BigArr的元素。
依上算法，寫代碼如下：
template< class T, class I >
void solution_4( T BigArr[], T ResArr[] )
{
//取最前面的一萬個(gè)
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 ZoneBeginIdx = MinElemIdx;
//遍歷后續(xù)的元素
for( unsigned int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i )
{
//這個(gè)后續(xù)元素比ResArr中最小的元素大，則替換。
if( BigArr[i] > ResArr[MinElemIdx] )
{
ResArr[MinElemIdx] = BigArr[i];
if( MinElemIdx == ZoneBeginIdx )
--ZoneBeginIdx;
//查找最小元素
unsigned int idx = ZoneBeginIdx;
unsigned int j = idx + 1;
for( ; j < RES_ARR_SIZE; ++j )
{
if( ResArr[idx] > ResArr[j] )
idx = j;
}
MinElemIdx = idx;
}
}
}
經(jīng)過測(cè)試，同樣情況下solution_4用時(shí)約1.8秒，較solution_3效率略高，總算不負(fù)一番努力。
待續(xù)……