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

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

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

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

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

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