有個(gè)同學(xué)近來(lái)一直在做一個(gè)魔獸世界戰(zhàn)況分析（名字好像叫DeusCraft），說(shuō)是很火。只是用C#覺得不是很爽，想移植到C++上面來(lái)。但是那個(gè)東西在分析的時(shí)候用了好多正則表達(dá)式，于是只好找了些正則表達(dá)式引擎來(lái)測(cè)。

    測(cè)試的文件一共有27萬(wàn)多行，首先通過(guò)一個(gè)檢查時(shí)間的正則表達(dá)式。如果成功，則在接下來(lái)的20幾條正則表達(dá)式中驗(yàn)證字符串命中哪一條，然后開始做剩余的工作。原先在C#上花了12秒分析，后來(lái)?yè)Q了boost的正則表達(dá)式花費(fèi)40秒，然后從MSR上找了一個(gè)號(hào)稱比boost快4倍的正則表達(dá)式引擎，結(jié)果還是40秒（都是微軟的，咋差距這么大……）。于是同學(xué)用他自己做的正則表達(dá)式引擎花了23秒（此數(shù)據(jù)不太記得），我用我以前那個(gè)東西花費(fèi)108秒（-_-|||）。

    于是我們這幾天就在優(yōu)化正則表達(dá)式引擎，到了今天同學(xué)那個(gè)花費(fèi)13秒，我那個(gè)12秒。Visual Studio 2008 Team System上有一個(gè)Performance Wizard，用于在程序執(zhí)行的過(guò)程中統(tǒng)計(jì)各個(gè)函數(shù)所占用的時(shí)間，可以方便定位，看出效率瓶頸，非常好用。

    我之前的正則表達(dá)式為了保持很多語(yǔ)法上的一致性（譬如選擇操作符“|”需要遵守交換律等等），使用了一種花費(fèi)很大的辦法來(lái)對(duì)字符串進(jìn)行分析。這種分析方法找出所有符合正則表達(dá)式要求的所有匹配的路徑然后進(jìn)行篩選。篩選的過(guò)程中浪費(fèi)了很多new和delete的操作，而且做了很多計(jì)算，維護(hù)了一個(gè)非常復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。后來(lái)想到有些事情是可以讓人來(lái)操心的，于是在原來(lái)的接口上加了一個(gè)option，添加了一種叫做“貪婪式”的分析方法。現(xiàn)在就同時(shí)有兩種分析方法用了。第二種分析方法的優(yōu)點(diǎn)是快，缺點(diǎn)是喪失了一些語(yǔ)法上的優(yōu)美（不過(guò)這個(gè)對(duì)于大部分人來(lái)說(shuō)應(yīng)該是沒什么關(guān)系的了。要是正則表達(dá)式的執(zhí)行過(guò)程不復(fù)雜的話，《精通正則表達(dá)式》也就賣不出去了，反正別人的正則表達(dá)式大多都是貪婪的）。貪婪式的分析方法不同時(shí)掃描所有路徑，而是使用回溯的方法。不過(guò)這種方法最大的優(yōu)點(diǎn)在于數(shù)據(jù)結(jié)構(gòu)可以大幅度簡(jiǎn)化為三個(gè)堆棧（NFA狀態(tài)、已捕獲子串、捕獲狀態(tài)），從而大量減少包括申請(qǐng)和釋放等的指針操作。

    上文中的測(cè)試是在同學(xué)他自己進(jìn)行的。我在我自己的電腦上使用了一條表達(dá)式（而不是20幾條）來(lái)跑相同的文件，非貪婪式用了23秒，貪婪式用了3.5秒。

    雖然這個(gè)正則表達(dá)式引擎的接口跟現(xiàn)在C#或Java流行的那些差不多，只是這東西屬于Syngram的一部分，所以不是很想單獨(dú)分隔成一個(gè)dll發(fā)布。至于代碼就要等Vczh Free Script 3.0或者Vczh Lazy Script 1.0發(fā)布的時(shí)候再一起開放了，因?yàn)槭褂肧yngram做編譯器是很爽的。到時(shí)候再考慮如何將正則表達(dá)式和上下文無(wú)關(guān)文法兩個(gè)強(qiáng)大的字符串分析庫(kù)封裝成dll用吧。嘿嘿。