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正则表达式速度

回答

相关问题