为什么正则表达式.*在一个地方较慢而在另一个地方较快

Question

最近我在java/groovy中使用了很多正则表达式.为了测试,我经常使用regex101.com.显然我也在看正则表达式的表现.

有一件事我注意到.*正确使用可以显着提高整体性能.首先,使用.*介于两者之间,或者更好地说不是正则表达式的结尾是性能杀戮.

例如,在此正则表达式中,所需的步骤数为27:

如果我先改变.*到\s*,这将减少到16显著所需的步骤:

但是,如果我第二个变化.*来\s*,它没有任何进一步降低步骤:

我有几个问题:

1. 为什么以上？我不想比较\s和.*.我知道不同之处.我想知道为什么\s和.*成本根据他们在完整正则表达式中的位置而有所不同.然后正则表达式的特征可能根据​​它们在整体正则表达式中的位置而成本不同(或者基于除位置之外的任何其他方面,如果有的话).
2. 此站点中给出的步骤计数器是否真的给出了有关正则表达式性能的任何指示？
3. 你有什么其他简单或类似(位置相关)的正则表达式性能观察？

Answer 1

以下是调试器的输出.

性能差异的主要原因是.*在字符串结束之前消耗所有内容(换行符除外).然后该模式将继续,强制正则表达式回溯(如第一张图片中所示).

其原因\s和.*在模式的结尾同样表现出色的是,贪婪模式与消费空白没有什么区别,如果没有什么别的匹配(除了WS).

如果您的测试字符串没有以空格结尾,那么性能会有所不同,就像您在第一个模式中看到的那样 - 正则表达式将被强制回溯.

编辑

如果你以空白之外的东西结束,你可以看到性能差异:

坏:

^myname.*mahesh.*hiworld

更好:

^myname.*mahesh\s*hiworld

更好的是:

^myname\s*mahesh\s*hiworld

Answer 2

正则表达式引擎使用*量词(也称为贪心量词)的方式是使用匹配的输入中的所有内容,然后:

1. 尝试正则表达式中的下一个术语.如果匹配,继续
2. "unconsume"一个字符(将指针移回一个),又称回溯并转到步骤1.

由于.匹配任何东西(差不多),遇到之后的第一个状态.*是将指针移动到输入的结尾,然后开始向后移动输入一个字符,一次尝试下一个字词,直到匹配为止.

使用时\s*,只消耗空白,因此指针最初会准确移动到您想要的位置 - 无需回溯以匹配下一个术语.

你应该尝试的是使用不情愿的量词.*?,它将一次消耗一个字符,直到下一个字词匹配,这应该具有相同的时间复杂度\s*,但稍微更高效,因为不需要检查当前字符.

\s*并且.*在表达式的末尾将执行类似的操作,因为两者将消耗匹配的末尾f输入处的所有内容,这使得指针对于两个表达式都是相同的位置.