regex - 为什么这个正则表达式很慢？

Question

m/.+?(\d{4})<\/i>\)/s

当我在一些正常大小的 HTML 页面上运行上面的正则表达式时它很慢？为什么？我不会认为它应该运行缓慢。

编辑:这是演示问题的代码示例:

use WWW::Mechanize;
my $mech = new WWW::Mechanize;
$mech->get("http://www.elaws.gov.bw/desplaysubsidiary.php?m=SUBSIDIARY&v=I&vp=&id=904");
$page = $mech->content();
$page =~ m/.+?(\d{4})<\/i>\)/s;

正则表达式行需要永远。如果我删除 .+?没有延迟。

Answer 1

这个好像有点误会

假设我们有一个字符串

my $s = 'xxxxxxxxxx9999</i>)';

然后像这样的模式匹配

$s =~ m<.*?(\d{4})</i>\)>

将首先假设 .*?在字符串的开头占用无字符。然后它会检查是否(\d{4})</i>\)匹配那个点的字符串

它失败了，所以正则表达式引擎给出了一个字符 x至 .*?并再次尝试。这也失败了，因此 .*? 使用的字符串部分逐个字符扩展，直到它匹配十个字符 xxxxxxxxxx .此时模式的其余部分匹配成功，正则表达式测试被声明为成功

相反，如果我们有一个非惰性模式

$s =~ m<.*(\d{4})</i>\)>

首先假设 .*占用所有字符串

此时模式的其余部分不匹配，因此回溯再次开始，给出 .*字符串中除一个字符外的所有字符，然后重试

这和以前一样重复，但是逐个字符地缩短匹配，直到它退回到字符串 9999</i>) 的尾部九个字符时找到匹配为止。和 .*现在匹配 xxxxxxxxxx和以前一样

回溯是在发现匹配失败时返回到先前匹配的模式元素，改变该元素的匹配方式和再试一次。它不会向后通过对象字符串寻找东西

这里的问题是由.*?引起的必须在模式中考虑。如果我们只有 m<(\d{4})</i>\)>相反，那么根本就没有回溯。正则表达式引擎只搜索 \d{4}</i>\)要么找到它，要么找不到

只要它是您想要的模式的第一次出现，它就可以正常工作。不幸的是，找到子字符串的最后 出现的唯一方法是在其前面加上.*。 ，这会启动回溯并使过程必然变慢

The above regex is slow when I run it over some normal size HTML pages?

即便如此，根据您对“正常大小的 HTML 页面”的看法，我认为这不会超过几毫秒。正则表达式引擎是用 C 语言编写的，速度非常快。我猜你一定是在上面运行了一个计时器来注意到任何延迟？