RegEx绩效问题

Question

我们遇到以下正则表达式的问题:

(.*?)\|\*\|([0-9]+)\*\|\*(.*?)

它应该匹配以下内容: |*25 *|

我们使用的是.Net Framework 4 RegEx Class,代码如下:

string expression = "(.*?)" + 
       Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
       "([0-9]+)" + 
       Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END) + 
       "(.*?)";
Regex r = new Regex(expression);
r.Matches(contentText)

使用40.000个字符的文本需要太长时间(如60秒).

但是180.000的文字速度是非常可接受的(3秒或更短)

文本之间的唯一区别是第一个文本(慢速的文本)它全部包含在一行中,没有换行符.这可能是个问题吗？那影响了性能？

谢谢

Answer 1

@David Gorsline的解决方案(来自评论)是正确的:

string expression =
    Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
    "([0-9]+)" + 
    Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END);

具体来说,它就是(.*?)在开始时让你进入.它的作用是接管正则表达式引擎本身应该做的事情 - 扫描正则表达式可以匹配的下一个地方 - 并且做得多,效率低得多.在每个位置,(.*?)有效地执行前瞻以确定正则表达式的下一部分是否可以匹配,并且仅当该失败时它继续并且消耗下一个字符.

但即使你使用了更高效的东西[^|]*,你仍然会放慢速度.但是,请保留该部分,并且正则表达式引擎可以替代扫描正则表达式的第一个常量部分,可能使用Boyer-Moore或Knuth-Morris-Pratt等算法.所以不用担心有什么身边要匹配的位; 只需告诉正则表达式引擎您正在寻找的东西并让它走出困境.

另一方面,尾随 (.*?)几乎没有影响,因为它从来没有真正做过任何事情.该?转的.*不情愿,所以怎样才能让它继续和消费的下一个字符？只有在强制它的正则表达式中有一些跟随它的东西时才会这样做.例如,在此之后foo.*?bar消耗从下一个"foo"到下一个"bar"的所有内容,但是foo.*?一旦消耗"foo"就停止.它从来没有很有意义的不情愿的量词作为一个正则表达式的最后一件事.