最近,我在java/groovy中使用了很多正则表达式。为了进行测试,我通常使用regex101.com。显然,我也在研究正则表达式的性能。
我注意到的一件事是,正确使用.*
可以显著提高整体性能。首先,在正则表达式的中间使用.*
,或者更好地说不是在正则表达式的末尾,这会降低性能。
例如,在this正则表达式中,所需的步骤数为27:
If I change first .*
to \s*
,它将大大减少所需的步骤至16步:
然而,if I change second .*
to \s*
,它不会进一步减少步骤:
我有几个问题:
\s
和.*
__。我知道其中的区别。我想知道为什么基于\s
和.*
在完整正则表达式中的位置,它们的成本会有所不同。然后是正则表达式的特征,根据它们在整个正则表达式中的位置(或者基于位置以外的任何其他方面,如果有的话),这些特征的成本可能会有所不同。这个站点中给出的步骤计数器是否真的给出了任何关于正则表达式performance?发布于 2015-11-06 22:08:06
正则表达式引擎使用*
量词(又称贪婪量词)的方式是使用输入中匹配的所有内容,然后:
由于.
几乎匹配任何内容,因此遇到.*
后的第一个状态是将指针移动到输入的末尾,然后开始返回输入,每次移动一个字符,尝试下一项,直到匹配为止。
使用\s*
时,只使用空格,因此指针最初会精确地移动到您想要的位置-不需要回溯以匹配下一项。
您应该尝试使用不情愿的量词.*?
,它将一次消耗一个字符,直到下一项匹配,它应该具有与\s*
相同的时间复杂度,但效率略高,因为不需要检查当前字符。
表达式末尾的\s*
和.*
将执行类似的操作,因为两者都将消耗匹配的末尾f输入的所有内容,这使得两个表达式的指针位置相同。
发布于 2015-11-06 22:01:32
以下是调试器的输出。
性能差异的主要原因是.*
将使用字符串末尾的所有内容(换行符除外)。然后,该模式将继续,强制正则表达式回溯(如第一个图像所示)。
\s
和.*
在模式的末尾表现同样好的原因是,如果没有其他东西可匹配(除了WS),贪婪模式与消耗空格没有区别。
如果您的测试字符串没有以空格结尾,那么性能将会有所不同,就像您在第一个模式中看到的那样--正则表达式将被迫回溯。
编辑
如果您以空格以外的其他内容结尾,则可以看到性能差异:
不好:
^myname.*mahesh.*hiworld
更好的:
^myname.*mahesh\s*hiworld
更好的是:
^myname\s*mahesh\s*hiworld
https://stackoverflow.com/questions/33568236
复制相似问题