regex - 为什么正则表达式。*在一个地方变慢而在另一个地方变快

Question

最近，我在Java / groovy中使用了许多正则表达式。为了进行测试，我通常使用regex101.com。显然，我也在查看正则表达式的性能。

我注意到一件事，正确使用.*可以显着提高整体性能。主要是在两者之间使用.*，或者最好不要在正则表达式的末尾使用.*杀死性能。

例如，在this正则表达式中，所需的步骤数为27：



If I change first \s* to .*，它将把所需的步骤大大减少到16：



但是，if I change second \s* to \s不会进一步减少步骤：



我有几个问题：


为什么会以上？我不想比较.*和\s。我知道区别。我想知道为什么.*和 的成本基于它们在完整正则表达式中的位置而不同。然后，正则表达式的特性可能因其在整个正则表达式中的位置（或基于位置以外的任何其他方面（如果有））而有所不同。
该网站上提供的步骤计数是否真的能说明正则表达式的性能？
您还有哪些其他简单或类似（与位置相关的）正则表达式性能观察？

Answer 1

正则表达式引擎使用*量词（又名贪婪量词）的方式是消耗匹配输入中的所有内容，然后：


在正则表达式中尝试下一个术语。如果匹配，请继续
“消耗”一个字符（将指针移回一个字符），又名回溯并转到步骤1。


由于.几乎匹配任何内容，因此遇到.*后的第一个状态是将指针移动到输入的末尾，然后一次尝试下一个术语开始一次遍历输入的整个字符，直到匹配为止。

使用\s*，仅占用空白，因此指针最初会精确地移动到您希望的位置-无需回溯即可匹配下一项。

您应该尝试使用的是不情愿的量词.*?，它会一次消耗一个字符，直到下一项匹配为止，该词的时间复杂度应与\s*相同，但是效率更高，因为不检查当前值必须输入char。

表达式末尾的\s*和.*的执行方式类似，因为两者都将消耗匹配输入f的末尾所有内容，从而使两个表达式的指针位置相同。