python 正则表达式速度

Question

关于正则表达式(特别是python re)，如果我们忽略表达式的书写方式，文本的长度是否是处理文档所需时间的唯一因素？或者是否还有其他因素(如文本的结构)也起着重要作用？

Answer 1

还有一个重要的考虑因素是文本是否真的与正则表达式相匹配。以(作为人为的例子)来自 this regex tutorial 的正则表达式 (x+x+)+y .

当应用于 xxxxxxxxxxy 时，它匹配，正则表达式引擎执行 7 个步骤。当应用于 xxxxxxxxxx 时，它失败了(当然)，但是引擎需要 2558 步才能得出这个结论。

对于 xxxxxxxxxxxxxxy 与 xxxxxxxxxxxxxx 它已经是 7 对 40958 步，依此类推...

这种情况在嵌套重复或正则表达式中尤其容易发生，其中相同的文本可以由正则表达式的两个或多个不同部分匹配，迫使引擎在能够声明失败之前尝试所有排列。这就是所谓的灾难性回溯。