正则表达式性能慢

Question

正则表达式性能慢

11

下面的代码包含一个正则表达式，旨在提取C#字符串文字，但对于多个字符的输入字符串，正则表达式匹配的性能非常糟糕。

class Program
{
   private static void StringMatch(string s)
    {
        // regex: quote, zero-or-more-(zero-or-more-non-backslash-quote, optional-backslash-anychar), quote
        Match m = Regex.Match(s, "\"(([^\\\\\"]*)(\\\\.)?)*\"");
        if (m.Success)
            Trace.WriteLine(m.Value);
        else
            Trace.WriteLine("no match");
    }

    public static void Main()
    {
        // this first string is unterminated (so the match fails), but it returns instantly
        StringMatch("\"OK");

        // this string is terminated (the match succeeds)
        StringMatch("\"This is a longer terminated string - it matches and returns instantly\"");

        // this string is unterminated (so the match will fail), but it never returns
        StringMatch("\"This is another unterminated string and takes FOREVER to match");
    }
}

我可以将正则表达式重构为另一种形式，但有人能解释一下性能为什么这么糟糕吗？

- adelphus

http://msdn.microsoft.com/en-us/magazine/ff646973.aspx - SLaks

我认为这是错误的。[^\"] 不会在 \" 停止，它会在 \ 或 " 处停止。因此，它将在 \n 的 \ 处停止。这正确吗？ - xanatos

1

如果您没有使用反向引用，那么您可以修改您的正则表达式。例如：""(?:(?:[^\"]*)(?:\.)?)*""。当然，如果您正在使用反向引用，请忽略此提示。 - Matthew

6个回答

2

编辑

这是你需要的正则表达式："\"([^\\\\\"]|\\\\.)*\""

解释一下，当C#转义字符串后，你会得到这个正则表达式："([^\\"]|\\.)*"

意思是：

"                #start with a quote
(
    [^\\"]       #match a non backslash or quote
    |            #or
    \\.          #backslash something
)                
*                #And repeat
"                #end with a quote

如果您不嵌套您的星号，就不会出现指数级或无限循环，对我来说它会立即返回。

- Buh Buh

这是真的。在排除字符组中也会出现同样的问题。 - adelphus

好的，很酷，请编辑您的问题以解决此问题，然后让我们知道您是否仍然遇到这些问题？ - Buh Buh

我已经纠正了代码，但问题仍然存在。感谢您的提醒。 - adelphus

我确实喜欢你的版本的简洁性，很可能会使用它。不过，我必须向Tim给出正确的答案，因为问题是“为什么性能如此糟糕”，而不是“给我一个更好的正则表达式”。尽管如此，感谢你的帮助 - 非常感激。 - adelphus

1

尝试

Match m = Regex.Match(s, @"'.*?(?<=[^\\](\\\\)*)'".Replace("'", "\""));

这将“智能地”忽略偶数个\。这是因为"关闭字符串，\"不会，\\\"会（因为第一个反斜杠转义了第二个反斜杠），\\\\\"不会...

.*?是一种懒惰量词。您甚至可以使用标准的.*量词。我建议您使用^和$锚定您的正则表达式。

我使用替换，因为转义双引号让我头疼:-)

我要补充说，在我的电脑上，对于4k文本，无论是匹配还是不匹配，都是瞬间完成的。

作为替代方案：

Match m = Regex.Match(s, @"^'(?>([^'\\]|\\.)*)'$".Replace("'", "\""));

解释：

(?> ) disables backtracking

^ begin of the string

那么你就有一个交替结构（0次或多次，*）：

[^'\\] any non-quote and non backslash

\\. or a backslash followed by another character (that is escaped)

$ end of the string

这也非常非常快，而且很容易阅读。

- xanatos

有时候，过度使用独立子表达式构造 (?> ) 并不能限制在该子表达式内的回溯，我认为它只是相对于外部表达式进行了限制。 - user557597

1

我认为@Tim Pietzcker对于回溯算法给出了最好的解释。

通过各种基准测试（包括我的测试），以下是快速的方法：

方法1：展开循环。

" [^"\\]* (?: \\. [^"\\]* )* "

方法二，交替

" (?: \\. | [^"\\]+ )* "

方法1可以大幅度地优于方法2。

信息

我认为解释灾难性回溯是非常困难的。有时候，除非时间上非常明显，否则很难识别它。然后，在时间关键的应用程序中，有时候进行一些基准测试是有益的。

在这个引用主题上，我喜欢添加新的方法到一个基准模板perl（5.10引擎）脚本中，看看它的表现如何。每个引擎都有一点不同。如果您感兴趣，这里是一个样例。

使用一个经过大量引用和转义的字符串，迭代100,000次的正则表达式示例与时间比较。

(?x-ism:" ( (?: \\?. )*? ) ")
代码执行时间：14.7031秒（14.58用户 + 0.00系统 = 14.58 CPU）

(?x-ism:" (.*? (?<!\\) (?:\\{2})* ) ")
代码执行时间：12.8435秒（12.75用户 + 0.00系统 = 12.75 CPU）

(?x-ism:" ( (?: [^\\"] | \\. )* ) ")
代码执行时间：10.3123秒（10.27用户 + 0.00系统 = 10.27 CPU）

(?x-ism: " ( (?: [^"\\]+ | (?:\\.)+ )* ) " )
代码执行时间：8.39063秒（8.39用户 + 0.00系统 = 8.39 CPU）

(?x-ism: " ( (?: [^"\\]+ | \\. )* ) " )
代码执行时间：8.7498秒（8.75用户 + 0.00系统 = 8.75 CPU）

(?x-ism: " ( (?: \\. | [^"\\]+ )* ) " )
代码执行时间：8.5623秒（8.44用户 + 0.00系统 = 8.44 CPU）

(?x-ism: " ( [^"\\]* (?: \\. [^"\\]* )* ) " )
代码执行时间：7.79661秒（7.80用户 + 0.00系统 = 7.80 CPU）

(?x-ism: (?> " ( (?: [^"\\] | \\. )* " ) ) )
代码执行时间：10.5156秒（10.52用户 + 0.00系统 = 10.52 CPU）

- user557597

1

这是我会使用的代码：

"[^\n"\\]*(?:\\.[^\n"\\]*)*"

@sln 的无展开循环方法是最快的，但我会通过排除换行符来进一步完善它，因为在老式字符串文字中不允许使用。 \\. 部分没问题，但 [^"\\] 需要改为 [^\n"\\]。此外，如果我们谈论的是提取字符串文字，就不能用 \A 和 \Z 锚定正则表达式。

我使用 RegexBuddy 来比较你的正则表达式、Tim 的没有锚点的正则表达式和这个正则表达式的性能。我将光标放在每个样本字符串的开头引号前，并使用“Debug Here”功能，这些是结果：

original regex        :  "(([^\\"\n]*)(\\.)?)*"

"OK                   :  failed in 101 steps

"This is a longer...  :  matched in 12 steps

"This is another...   :  gave up after 1,000,000 steps



Tim's regex           :   "(?:\\.|[^\\"\n])*"

"OK                   :  failed in 17 steps

"This is a longer...  :  matched in 211 steps

"This is another...   :  failed in 253 steps


unrolled loop         :  "[^\\"\n]*(?:\\.[^\\"\n]*)*"

"OK                   :  failed in 5 steps

"This is a longer...  :  matched in 5 steps

"This is another...   :  failed in 5 steps

将其作为逐字字符串插入您的代码中，您将得到以下内容：

Match m = Regex.Match(s, @"""[^\n""\\]*(?:\\.[^\n""\\]*)*""");

编辑：顺便说一下，我并不是说你必须使用这个正则表达式，因为其他解决方案几乎肯定已经足够快了。但是如果您确实需要最大的性能（同时仍然使用正则表达式），那么这可能是实现它的方法。让它如此快的原因是正则表达式总是向前移动：没有反向引用、没有向前查找，最重要的是没有回溯。

- Alan Moore

0

回溯问题是由于所有内容都位于嵌套的量化器组内部且是可选的，这个块被文字包围所致。由于永远无法到达最终的文字，引擎会无限尝试每个内部序列。

唯一的解决方法是在该块内放置一个文字停止点。这是停止回溯的点。

除此之外，您可以将文字放在两个变量术语内，并使用巧妙的聚类来获得最佳结果：

"  [^\\"]*  (?:  \\.    [^\\"]*  )*  "
     ^^^         ^^^      ^^^
     var       literal    var

- sln

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Pietzcker · Accepted Answer

你遇到了灾难性回溯：

让我们简化一下正则表达式（不包括转义引号和第二个可选组，因为如你所述，对于测试的字符串来说无关紧要）：

"(([^\\"]*))*"

([^\\"]*)匹配除引号或反斜杠之外的任何字符串。这个表达式又被包含在一个可选的组中，可以重复任意次数。

现在对于字符串"ABC，正则表达式引擎需要尝试以下排列组合：

", ABC
", ABC, <empty string>
", AB, C
", AB, C, <empty string>
", AB, <empty string>, C
", AB, <empty string>, C, <empty string>
", <empty string>, AB, C
", <empty string>, AB, C, <empty string>
", <empty string>, AB, <empty string>, C, <empty string>
", <empty string>, AB, <empty string>, C
", A, BC
", A, BC, <empty string>
", A, <empty string>, BC
", <empty string>, A, BC
等等。
", A, B, C
", A, B, C, <empty string>
", A, B, <empty string>, C
等等等等。

每个排列组合都会因为没有后续的"而失败。

此外，你只测试了子字符串，而没有强制正则表达式匹配整个字符串。通常应使用原样字符串表示正则表达式以减少需要转义的反斜杠数量。如下所示：

foundMatch = Regex.IsMatch(subjectString, 
    @"\A     # Start of the string
    ""       # Match a quote
    (?:      # Either match...
     \\.     # an escaped character
    |        # or
     [^\\""] # any character except backslash or quote
    )*       # any number of times
    ""       # Match a quote
    \Z       # End of the string", 
    RegexOptions.IgnorePatternWhitespace);