python正則表達式速度

關於正則表達式（特別是python re），如果我們忽略表達式的寫法，是文本的長度是處理文檔所需時間的唯一因素？或者還有其他因素（如文本的結構）如何發揮重要作用？python正則表達式速度

2010-09-27 goh

文本的長度及其內容都很重要。

作爲一個例子正則表達式a+b將無法在包含百萬b秒，但更慢含百萬a個字符串的字符串匹配快速。這是因爲在第二種情況下需要更多的回溯。

import timeit 
x = "re.search('a+b', s)" 
print timeit.timeit(x, "import re;s='a'*10000", number=10) 
print timeit.timeit(x, "import re;s='b'*10000", number=10)

結果：

6.85791902323 
0.00795443275612

來源

2010-09-27 06:37:17

標題中存在''regexp'並且存在（'Mark Byers'）'=>'True'。 – OTZ 2010-09-27 06:39:47

是文本中冗長的單詞，例如「垃圾郵件垃圾郵件....」意義重大？我的正則表達式基本上尋找製表符，並用空格str = re.sub（「\ t」，「」，str）替換，但對於這段特定的文本，它似乎永遠不變。根據你的回答，就我而言，這應該不重要。 – goh 2010-09-27 06:48:58

@goh：對於那個特殊的正則表達式，它沒有任何區別。這個正則表達式非常簡單，所以沒有太多的回溯。 – 2010-09-27 06:53:00

一個重要的考慮因素也可以是文本是否真正的正則表達式匹配。拿（作爲一個人爲的例子）正則表達式(x+x+)+y從this regex tutorial。

當應用於xxxxxxxxxxy它匹配，採取正則表達式引擎7個步驟。當應用於xxxxxxxxxx時，它失敗（當然），但需要引擎2558步驟才能得出這個結論。

對於xxxxxxxxxxxxxxy與xxxxxxxxxxxxxx它已經7 VS 40958步驟，等等成倍...

這種情況特別容易與嵌套的重複或正則表達式同一文本可以通過兩個或多個不同的部分進行匹配正則表達式，迫使引擎在能夠聲明失敗之前嘗試所有排列組合。這被稱爲災難性的回溯。

來源

2010-09-27 06:45:50

python正則表達式速度

回答

相關問題