为什么在正则表达式中,贪婪量词比懒惰量词更高效?

6

http://www.rexegg.com/regex-quantifiers.html#tempered_greed

enter image description here


贪婪量词(默认)- 通过尽可能地吞噬允许的字符,然后逐个减少匹配的字符数量,以便为模式的其余部分腾出空间。

例如,正则表达式.*world应用于字符串hello world将首先尝试吞噬整个字符串并将其放入.*中。但是它不能,因为world无法匹配,所以.*开始逐个放弃字符,直到它放弃了原始字符串中的world - 在这种情况下,整个正则表达式可以匹配。

懒惰量词 - 工作方式类似,只不过相反。它们希望尽可能少地匹配字符,并且执行相同的操作,逐个添加更多字符,直到模式的其余部分有机会匹配。


但是根据我读过的这篇文章,这些看似相同的贪婪懒惰量词的进程是不同的 - 只有懒惰量词需要“回溯”。但是当吐出先前吞下的元素时,贪婪量词也需要“回溯”,为什么会出现这种情况?这似乎很直观。

2个回答

11
贪婪量词和懒惰量词在正确应用时的代价相同。然而,懒惰量词因为通常被用来弥补模式不精确而被认为是缓慢的。
考虑一个简单的例子:<.*?><.*>
当这两个表达式应用于相同的输入时,
<abcdefghijklmnopqrstuvwxyz0123456789>

它们完全匹配相同的文本。区别仅在于它们如何进行匹配:"懒惰"表达式会尝试逐渐增加更长的字符串,经过40个步骤后到达匹配位置(演示1)。另一方面,贪婪表达式一直走到末尾,然后向后跟踪回到匹配位置,只经过5个步骤就到达了匹配位置(演示2)。

请注意,如果在>后添加更多字符,则情况可能会反转:

<abcdefghijklmnopqrstuvwxyz0123456789>abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789

现在,贪婪表达式变成了“慢表达式”,需要 149 步才能匹配成功 (演示 3),而懒惰表达式仍然像之前一样只需要 40 步就能匹配成功 (演示 4)。


但是贪婪量词不也会遇到类似的情况吗?通过在正则表达式中“反刍”先前匹配的元素,它也在执行回溯,对吧? - AlanSTACK

3

有时贪婪是不好的。

示例[asdfsikbfqew0787072143k*(*&^(**&]

工作台

Regex1:   \[[^\]]*\]
Options:  < none >
Completed iterations:   200  /  200     ( x 1000 )
Matches found per iteration:   1
Elapsed Time:    0.48 s,   476.21 ms,   476211 µs


Regex2:   \[.*?\]
Options:  < none >
Completed iterations:   200  /  200     ( x 1000 )
Matches found per iteration:   1
Elapsed Time:    0.32 s,   322.73 ms,   322730 µs

切勿使用dot结合greedy,除非你需要匹配行末的剩余部分。

有人曾告诉我,(?=.*d)是从下一个字符开始检查的前瞻,这是绝对错误的。
这会立即将指针设置到字符串的末尾,并向后回溯(backtracking)。 注意,它会跳过所有内容。
它比看干漆还慢。

我曾经经常使用greedy,但现在只有在必要时才使用,而且我不建议任何人使用它。


1
你用什么来计时? - Michael
1
@Michael - 这里这里这里 - user557597
我认为这并不是对OP的回答,因为您没有将惰性和贪婪量词应用于相同的模式。尽管如此,这仍然很有趣。 - logi-kal

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接