下面的 Python 代码非常慢:
import re
re.match( '([a]+)+c', 'a' * 30 + 'b' )
如果用更大的常数替换 30,情况会变得更糟。
我怀疑由于连续的解析歧义+
是罪魁祸首,但我在正则表达式解析和匹配方面不是很专家。这是Python正则表达式引擎的错误,还是任何合理的实现都会做同样的事情?
我不是 Perl 专家,但以下返回速度相当快
perl -e '$s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; print "ok\n" if $s =~ m/([a]+)+c/;'
并且增加“a”的数量不会显着改变执行速度。
我认为 Perl 足够聪明,可以将两者折叠起来+
s 合而为一,而 Python 则不然。现在让我们想象一下,如果没有优化的话,引擎会做什么。请记住,捕获通常很昂贵。另请注意,两者+
s 是贪婪的,因此引擎将尝试在一个回溯步骤中使用尽可能多的重复。每个要点代表一个回溯步骤:
- 引擎使用尽可能多的
[a]
尽可能,并消耗全部三十a
s。然后它就不能再继续了,所以它留下了第一个重复,captures 30 a
s。现在下一个重复开始了,它试图用另一个重复消耗更多([a]+)
但这当然行不通。然后是c
无法匹配b
.
- 回头!扔掉最后的
a
被内在的重复所消耗。之后我们再次离开内部重复,因此引擎将capture 29 a
s。然后另一个+
开始,再次尝试内部重复(消耗第 30 个a
)。然后我们再次离开内部重复,这也离开了捕获组,因此第一个捕获被丢弃并且引擎captures最后a
. c
无法匹配b
.
- 回头!扔掉另一个
a
里面。我们capture 28 a
s。捕获组的第二个(外部重复)消耗了最后 2 个a
s 是captured. c
无法匹配b
.
- 回头!现在我们可以在第二个重复中回溯并丢弃两个中的第二个
a
是。剩下的将是captured。然后我们第三次进入捕获组并且capture最后a
. c
无法匹配b
.
- 回头!降至27
a
s 在第一次重复中。
这是一个简单的可视化。每一行代表一个回溯步骤,每组括号显示内部重复的一次消耗。大括号代表那些newly为该回溯步骤捕获,而在此特定回溯步骤中不会重新访问普通括号。我省略了b
/c
因为它永远不会匹配:
{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaa}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaa}{aaaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aaa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa){a}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a)(a){a}{a}
和。所以。在。
请注意,最后引擎还将尝试子集的所有组合a
(回溯到前 29a
然后通过前 28a
s) 只是为了发现,c
也不匹配a
.
正则表达式引擎内部结构的解释基于分散的信息正则表达式.info http://www.regular-expressions.info/.
为了解决这个问题。只需删除其中之一即可+
s。任何一个r'a+c'
或者如果你do想要捕获的金额a
s use r'(a+)s'
.
最后回答一下你的问题。我不认为这是 Python 正则表达式引擎中的错误,而只是(如果有的话)缺乏优化逻辑。这个问题通常无法解决,因此引擎假设您必须自己处理灾难性的回溯并不是太不合理。如果 Perl 足够聪明,能够识别足够简单的情况,那就更好了。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)