为什么这个正则表达式会变慢？

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>\)并找到它或不找到它

只要它是您想要的第一次出现的模式,这样就可以正常工作.不幸的是,找到子串的最后一次出现的唯一方法是在它之前.*,这将启动回溯并使进程必然更慢

当我在一些正常大小的HTML页面上运行时,上面的正则表达式很慢？

即便如此,根据您对"正常大小的HTML页面"的看法,我看不出这需要超过几毫秒.正则表达式引擎用C编码,写得非常快.我想你必须在它上面运行一个计时器才能发现任何延迟？