gpt4 book ai didi

python - 比较不匹配的正则表达式的速度

转载 作者:太空狗 更新时间:2023-10-29 19:37:48 25 4
gpt4 key购买 nike

下面的 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 足够聪明,可以将两个 + 合二为一,而 Python 却没有。现在让我们想象一下如果不优化引擎会做什么。请记住,捕获通常很昂贵。另请注意,两个 + 都是贪心的,因此引擎将尝试在一个回溯步骤中使用尽可能多的重复。每个要点代表一个回溯步骤:

  • 引擎使用尽可能多的[a],并消耗所有三十个a。然后它不能再继续了,所以它离开了第一个重复并捕获 30 个a。现在下一次重复开始了,它试图用另一个 ([a]+) 消耗更多,但这当然行不通。然后 c 无法匹配 b
  • 回溯!丢弃内部重复消耗的最后一个a。在此之后,我们再次保留内部重复,因此引擎将捕获 29 个a。然后另一个 + 开始,再次尝试内部重复(消耗第 30 个 a)。然后我们再次离开内部重复,这也离开了捕获组,所以第一个捕获被丢弃,引擎捕获最后一个ac 无法匹配 b
  • 回溯!扔掉里面的另一个a。我们捕获 28 个a。捕获组的第二个(外部重复)消耗最后 2 个a,它们是捕获的c 无法匹配 b
  • 回溯!现在我们可以在第二个其他重复中回溯并丢弃两个 a 中的第二个。剩下的那个将被捕获。然后第三次进入捕获组,捕获最后一个ac 无法匹配 b
  • 回溯!在第一次重复中减少到 27 个 a

这是一个简单的可视化。每条线代表一个回溯步骤,每组括号代表一次内部重复的消耗。大括号表示那些为该回溯步骤捕获的那些,而在该特定回溯步骤中不会重新访问普通括号。我省略了 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 的子集的所有组合(仅通过前 29 个 a 回溯,然后通过前 28 个 as) 只是为了发现,c 也不匹配 a

正则表达式引擎内部的解释是基于散布在 regular-expressions.info 周围的信息.

解决这个问题。只需删除其中一个 +r'a+c' 或者如果您确实 想要捕获a 的数量,请使用r'(a+)s '.

最后,回答你的问题。我不会认为这是 Python 的正则表达式引擎中的错误,而只是(如果有的话)缺乏优化逻辑。这个问题通常无法解决,因此引擎假设您必须自己处理灾难性的回溯并不太合理。如果 Perl 足够聪明,可以识别足够简单的情况,那就更好了。

关于python - 比较不匹配的正则表达式的速度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13179030/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com