慢性能正常表现
下面的代码包含一个用于提取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"); } }
我可以将正则表达式重构为另一种forms,但任何人都可以解释为什么表现如此糟糕?
你遇到了灾难性的回溯:
让我们简化一下正则表达式(没有转义的引号,也没有第二个可选组,因为在评论中,它与测试的字符串无关):
"(([^\\"]*))*"
([^\\"]*)
匹配除引号或反斜杠之外的任何字符串。这再次包含在可重复任意次数的可选组中。
现在对于字符串"ABC
,正则表达式引擎需要尝试以下排列:
-
"
,ABC
-
"
,ABC
, -
"
,AB
,C
-
"
,AB
,C
, -
"
,AB
,
,C
-
"
,AB
,
,C
, -
"
,
,AB
,C
-
"
,
,AB
,C
, -
"
,
,AB
,
,C
, -
"
,
,AB
,
,C
-
"
,A
,BC
-
"
,A
,BC
, -
"
,A
,
,BC
-
"
,
,A
,BC
- 等等
-
"
,A
,B
,C
-
"
,A
,B
,C
, -
"
,A
,B
,
,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);
编辑
你去: "\"([^\\\\\"]|\\\\.)*\""
要解释一下,在C#转义字符串之后你得到了这个正则表达式: "([^\\"]|\\.)*"
含义:
" #start with a quote ( [^\\"] #match a non backslash or quote | #or \\. #backslash something ) * #And repeat " #end with a quote
通过不嵌套你的*你没有得到指数或无限循环,它会立即返回给我。
我认为@Tim Pietzcker给出了关于回溯的最佳解释。
通过各种基准(我自己包括),这些是快速的方法:
方法1,展开
" [^"\\]* (?: \\. [^"\\]* )* "
方法2,改变
" (?: \\. | [^"\\]+ )* "
方法1,可以大幅超越2。
信息
我认为很难解释灾难性的回溯。 即使认识到它有时也很难,除非时间非常明显。 然后,在时间关键的应用程序中,做一些基准测试有时是有益的。
在这个引用主题上,我喜欢为基准模板化perl(5.10引擎)脚本添加新方法,以了解它的工作原理。 每个引擎都有点不同。 如果你关心,这是一个样本。
使用重度引用和转义字符串的正则表达式样本与时间的关系
每次迭代100,000次。
(?x-ism:" ( (?: \\?. )*? ) ")
代码采用:14.7031 wallclock secs(14.58 usr + 0.00 sys = 14.58 CPU)
(?x-ism:" (.*? (?
代码采用:12.8435 wallclock secs(12.75 usr + 0.00 sys = 12.75 CPU)
(?x-ism:" ( (?: [^\\"] | \\. )* ) ")
代码采用:10.3123 wallclock secs(10.27 usr + 0.00 sys = 10.27 CPU)
(?x-ism: " ( (?: [^"\\]+ | (?:\\.)+ )* ) " )
代码采用:8.39063 wallclock secs(8.39 usr + 0.00 sys = 8.39 CPU)
(?x-ism: " ( (?: [^"\\]+ | \\. )* ) " )
代码采用:8.7498 wallclock secs(8.75 usr + 0.00 sys = 8.75 CPU)
(?x-ism: " ( (?: \\. | [^"\\]+ )* ) " )
代码采用:8.5623 wallclock secs(8.44 usr + 0.00 sys = 8.44 CPU)
(?x-ism: " ( [^"\\]* (?: \\. [^"\\]* )* ) " )
代码采取:7.79661 wallclock secs(7.80 usr + 0.00 sys = 7.80 CPU)
(?x-ism: (?> " ( (?: [^"\\] | \\. )* " ) ) )
代码采用:10.5156 wallclock secs(10.52 usr + 0.00 sys = 10.52 CPU)
尝试
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
这也非常快,而且很容易阅读。
这是我会用的:
"[^\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""\\]*)*""");
编辑:顺便说一句,我不是说你必须使用这个正则表达式,因为它更快; 其他解决方案几乎肯定足够快。 但是如果你确实需要最大的性能(同时仍然使用正则表达式),这可能是实现它的方法。 正是如此之快的原因是正则表达式始终向前发展:没有后向引用,没有外观,最重要的是,没有回溯。
- 如何在C中初始化多维Char数组?
- 我怎么能捕获键盘输入并将其写入文件?
- 如何在ASP.NET中显示消息框?
- 从Accelerometer.ReadingChanged调用NavigationService.Navigate会抛出NotSupportedException
- 不安全的C#技巧提高速度
- 无法从’System.Data.Objects.ObjectParameter’转换为’System.Data.Entity.Core.Objects.ObjectParameter’
- 在窗体视图中的转发器中的代码隐藏中设置下拉列表中的选定值
- 使用LINQ合并2个数组
- Web API中的MVC-6与MVC-5 BearerAuthentication