KMP 算法并非優(yōu)化
算法書和數(shù)據(jù)結(jié)構(gòu)書對(duì)KMP算法多有介紹，稱只需對(duì)字符串掃描一遍不需回溯云云.然而,它恐怕只應(yīng)該作為一種思想存在;用于實(shí)際的字符串查找并不理想.要費(fèi)勁心血實(shí)現(xiàn)和優(yōu)化它,才能在特定的字符串上略微超過(也可能略微遜過)std::search.
KMP算法的基本思想,是利用需要匹配字符串的自身信息來避免回溯.(這里討論的算法是以C/C++為編程語(yǔ)言,因此下標(biāo)索引以0開始)
例如:字符串PAT=”abcabcde”,里面第二段的abc和PAT開頭的字符是匹配的.
假如我們有個(gè)要查找的字符串TEXT=”abcabD...”,在比較到TEXT的'D'處(TEXT[5])也即到了PAT的第二個(gè)'c'(PAT[5])時(shí)比較失敗,一般的字符串查找又得從TEXT[1](即'b')開始查找PAT.而KMP算法知道PAT的第二段abc匹配自身的開頭字符串，它會(huì)對(duì)PAT存儲(chǔ)如下next表:0 0 0 1 2 3 0 0數(shù)字代表匹配失敗后應(yīng)該從PAT的第多少個(gè)位置開始比較.我們這里在PAT[5]處失敗,而前面的PAT[0...4]都比較成功,因此先看看PAT[5]的上一個(gè)成功位置的next信息:next[4]=2,這代表應(yīng)該從PAT[2]處重新開始比較(即說明有2個(gè)字符不需要比了),就不需要跳到TEXT[1]處重新啟動(dòng)查找,這時(shí)的PAT[0...1]為”ab”,TEXT的'D'的前面兩個(gè)也是”ab”,只需要開始比較TEXT[5]和PAT[2],KMP說的無回溯意義正是如此:不需要回溯TEXT的比較位置.如果PAT[2]又失敗了,next[1]=0.那么TEXT[5]與PAT[0]開始比較,不成功的話TEXT遞增到TEXT[6],一直遞增到成功為止,成功的話當(dāng)然PAT也開始遞增.
偽碼如下:
template<class I>
I find(I beg,I end)
{
int patPos=0;
while (beg!=end)
{
if (*beg==PatChar[patPos])
{//匹配時(shí)遞增文本和模式的指針.
++beg;
if (++patPos!=sizePat)
continue;
//如果模式指針遞增了模式的長(zhǎng)度那么多次,說明比較成功,返回指針
return beg-=failFunc.size();
}
else if (patPos)//根據(jù)next表信息調(diào)整模式串要比較的位置
patPos=nextTable(--patPos);
else
++beg;
}
return end;
}
我用微軟的wingdi.h頭文件測(cè)試,方法是讀入后自加到1M以上,在里面找”IN HDC, IN UINT””PolyPolyline”這樣的串若干次.
實(shí)測(cè)性能非常低,既比不過std::string::find,也比不過std::search.
于是我進(jìn)行了第一次優(yōu)化.像很多書本的作者正確指出的那樣,一般的程序員對(duì)該優(yōu)化的地方常常估計(jì)錯(cuò)誤:
請(qǐng)看前面說的PAT[5]失敗的地方,它跳轉(zhuǎn)到PAT[2]開始比較,然而PAT[2]比較必定失敗,為什么?因?yàn)?span mce_style="font-family: 'Times New Roman';">PAT[5]==PAT[2]='c',PAT[5]失敗當(dāng)然PAT[2]也會(huì)失敗,我的優(yōu)化移除此類情況,也即next表:0 0 0 1 2 3 0 0優(yōu)化后變?yōu)?span mce_style="font-family: 'Times New Roman';">:0 0 0 0 0 3 0 0 .
興沖沖的重新編譯運(yùn)行換來的卻是些微的提升.顯然這不是影響性能的地方.
分析良久后也沒找到應(yīng)該改進(jìn)的地方,因?yàn)?span mce_style="font-family: 'Times New Roman';">std::search的代碼比較平凡.最后抱著試試看的心理,把代碼替換了:
template<class I>
I find(I beg,I end)
{ …
beg=std::find(beg,end, PatChar[0]);
int patPos=0;
else if (patPos)
patPos=nextTable(--patPos);
else
{
beg=std::find(beg,end, PatChar[0]);
patPos=0;
}
}
return end;
}
帶來了巨大的速度提升,使得KMP查找的速度大大提升,在gcc上比string.find快,在vs 2008比std::search快了(恩,換句話說就是比gcc的std::search慢,比vs 2008的string.find慢...)
恩,總算發(fā)現(xiàn)性能低下的真正原因了:在一大塊文本中找少量匹配的文本,最好是先濾掉不匹配的.對(duì)于不匹配的情況,std::find需要的指令更少;因此先用它來跳過不匹配的字符后在進(jìn)入KMP比較算法的核心會(huì)帶來可觀的速度提升.
那么接下來還有什么高級(jí)手段使得KMP算法大大改進(jìn)嗎?我嘗試了很久.然而很遺憾,沒有什么再值得慶祝的優(yōu)化了:它們?cè)黾恿?span mce_style="font-family: 'Times New Roman';">10倍的煩惱,換來一點(diǎn)點(diǎn)的性能提升.比方說:對(duì)于PAT=”abcabcde”,它的前置串”abcab”的next值都為0,意味著可以先提前用簡(jiǎn)單的代碼去比較”abcab”，一旦比較失敗又繼續(xù)從失敗處開始找而不需要去查看next表.因此我的實(shí)際代碼是用findFront_代替了std::find來干這事.這讓KMP算法提升了一點(diǎn)點(diǎn)性能,付出了n天思考和除錯(cuò)的時(shí)間.
最終的成型算法是這樣的結(jié)果:比gcc自帶的string::find要快,偶爾(通過對(duì)比較文本串的大小和比較次數(shù)調(diào)整)快于gcc的std::search;比vs 2008的std::search快,被vs 2008的string::find秒殺....
結(jié)論:
1.簡(jiǎn)單的代碼編譯器容易優(yōu)化.也適合現(xiàn)代處理器的預(yù)測(cè)執(zhí)行技術(shù)和cache.
2.日常用的要查找的字符串不會(huì)有多少適合KMP查找:”abcabcabcabc”的next表是什么值?優(yōu)化后應(yīng)該全為0!我對(duì)著wingdi.h看了幾遍才找到了像”WINGDIAPI BOOL WINAPI”,”PATPAINT”這些歪瓜劣棗,它們的next表優(yōu)化后也只有一兩個(gè)地方有值.KMP算法應(yīng)該適用在文本中大量字符串重復(fù)且要找的子串也自身重復(fù)的情況.
3.去實(shí)現(xiàn)KMP查找不如用std::search.
代碼下載
花絮:
gcc的string::find很低效;因?yàn)樗鼈兙褪怯?span mce_style="font-family: 'Times New Roman';">char_trait的eq一個(gè)個(gè)去找,vs2008的是用memchr先找到一個(gè)再去比較整個(gè)串.也許unix世界習(xí)慣了用正則庫(kù)根本不怎么用標(biāo)準(zhǔn)庫(kù)自帶的.
不過gcc的string::find低效是相對(duì)自己的其它庫(kù)函數(shù)而言.它編譯的測(cè)試代碼普遍比vs2008的快上一倍以上.
vs2008的std::search比較低效;就是平凡地一個(gè)字符一個(gè)字符對(duì)比;而gcc的std::search先用std::find找到第一個(gè)相等的字符后再去比較整個(gè)串.(看這里和string::find情況反過來了)
vs2008的std::find很平凡,只是對(duì)char的情況特化成memchr;gcc的find對(duì)隨機(jī)迭代器做了優(yōu)化,循環(huán)展開成4個(gè)4個(gè)地比較.
測(cè)試環(huán)境:xp sp3
Cpu:amd 5000超頻到2.7G
內(nèi)存:ddr2 2G.