為什麼使用正則表達式會慢？

01-02

大家都說，在對性能敏感程序中盡量避免使用正則表達式。為什麼正則表達式會慢？
（面試官說並不是因為需要調用正則表達式模塊，因為PHP中正則表達式模塊是編譯進去的，也是以C的速度執行的。）

我倒覺得一般情況下不是因為複雜度，而是時間常數偏大，因為你自己寫的也不太會考慮成直接實現成有限狀態機，以後要修改就悲劇了……至於其他答案舉的例子，小心設計下正則表達式也是可以避免的。

主要還是因為正則匹配是通用演算法，所以會引入很多額外的判斷和分支，導致時間常數偏大。如果以後JIT技術進步了的話，也許就沒有這些性能問題了。

當然如果你壓根就缺乏正則表達式的語感（？），那寫出的非常詭異的表達式很可能是很慢的，但這種情況下我嚴重懷疑你自己手寫的會更糟糕，而且寫不對。

另外PHP里有啥性能敏感的程序……就算是PHP7，除了簡單的strpos之類能覆蓋的情況以外，我也嚴重懷疑能不能寫出比正確的正則表達式更快的程序，還是老老實實跟Python來個排排坐吃果果吧。

補充一下，來源：請問一下大家正則表達式的時間複雜度

NFA構造O(n)，匹配O(nm)

DFA構造O(2^n)，最小化O(kn"logn")（N"=O(2^n)），匹配O(m)

n=regex長度，m=串長，k=字母表大小，n"=原始的dfa大小

打開控制台，輸入如下代碼，然後看看你的CPU，你的電腦不卡算我輸：

"10101010110101001100101010101010101010101010101010000".match(/([01]+)+b/)

這長度還不到100呢

有人問這個正則為什麼會讓進程卡死，當然是因為進入了類似死循環的情況了

大致解釋一下，可以看到裡面有兩個加號，而且都是貪婪匹配，這會導致內層的加號首先嘗試把整個正則表達式匹配完，然後外層的加號再把這個模式重複，然而重複的時候又會發生一次內層加號的匹配，而兩個加號匹配完成後又發現後面並沒有一個b，於是回溯到外層括弧（因為外層是後匹配的，所以先回溯到它）減少其匹配數量，每次回溯都會有很多條分支可走（加號可以選擇匹配1到無窮多個，此例中即為匹配到字元串的結束），最後直到回溯到最開始的兩個字元，上例中即10，然後發現第三個符號依然不是b，然後才告結束。

每一次面臨選擇，都有從該位置直到結束那麼多種選擇，時間複雜度大概是n的階乘

評論有人提到在不同的語言下性能不一樣，原因是不同的語言內置的正則引擎不一樣，我了解的也不多，就不細說了。

演算法複雜度決定的。

正則有幾種基本的實現方式

第一種是回溯。也就是遇到字元就比較是不是符合當前的模式或可以套進下一個模式，符合就繼續「吃」掉字元，不符合有可能要回溯，將之前的字元吐出來，再餵給下一個模式去嘗試。比如一個最簡單的例子，模式ab|aa，輸入串"aa" 輸入的第一個a符合第一個模式"ab"中的a，但第二個a不符合模式中的b，這時要吐出a來，再去嘗試第二個模式aa。(a|aa)*遇到這種模式串下，因為每一個字元輸入可以匹配兩個方向，可能的分支按指數級別增長，遇到aaaaaaaaab這種時，導致指數級別的狀態回溯。

另一種是根據正則的模式串，實時構造一個決定性自動機，也就是創建一個很大的狀態遷移表，記錄了當遇到什麼字元時，從什麼狀態轉到什麼狀態。one-pass便利目標串，根據狀態遷移依次走到最後得到結果：接受還是不接受該串。但構造這個模式串的狀態會非常多，構造的時間複雜度也是O(m^2)，此後單次匹配的時間複雜度是O(n)。n是目標串的長度，m是模式串的長度。

還有一種叫lazy dfa，在進行過程中構造決定性自動機而不是一次過構造整個模式對應的自動機，並且在過程中對自動機進行緩存，這個會比較快點，但單次匹配的複雜度會比較高，印象中是小o(n*m)以上的。

ok。。因此在cgi程序裡面性能關鍵的查詢用regex，會很容易被dos攻擊。

有人說到NFA和DFA，實際上如果直接NFA匹配的話，複雜度O(nm)是可以接受的，畢竟正則長度數量級很小。

然而posix regex包含了很多亂七八糟的特性，可能不是一個NFA可以描述的，這導致了優化困難，樓上提到的/([01]+)+/顯然匹配演算法暴力回溯，時間變成指數級（正則攻擊）。

看正則寫的複雜度和邏輯吧，不要有太多回溯，速度還可以。

如果你能搞出來按需編譯的正則，那你大可以一勞永逸了。

不是慢

就是出現了死循環（回溯過多）

就像寫遞歸沒有處理好結束條件一樣

屬於邏輯上的錯誤

看正則的實現方式吧， NFA， DFA。用NFA的話會出現指數複雜度，但是即使自己手寫也不見得會實現成DFA，畢竟是體力活。所以我推薦用lexer搞，讓工具干dirty work，不過，真有這麼在乎性能嗎？