我有一个用户输入的搜索字符串。通常,搜索字符串使用空格分开,然后执行 OR 搜索(如果项目匹配任何搜索字符串元素,则该项目匹配)。我想提供一些“高级”查询功能,例如使用引号将包含空格的文字短语括起来的能力。
虽然我已经敲定了一个不错的正则表达式来为我拆分字符串,但它的执行时间出奇地长(在我的机器上 > 2 秒)。我把它拆开来找出打嗝的地方,更有趣的是,它似乎发生在最后一个 Match
匹配之后(大概是在输入的末尾)。直到字符串末尾的所有匹配都在比我捕获的时间更短的时间内匹配,但是最后一个匹配(如果是这样的话 - 没有任何返回)几乎占用了 2 秒的全部时间。
我希望有人能对我如何加快这个正则表达式的速度有所了解。我知道我正在使用带有无界量词的后视,但就像我说的那样,在匹配最后一场比赛之前,这似乎不会导致任何性能问题。
代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
namespace RegexSandboxCSharp {
class Program {
static void Main( string[] args ) {
string l_input1 = "# one \"two three\" four five:\"six seven\" eight \"nine ten\"";
string l_pattern =
@"(?<=^([^""]*([""][^""]*[""])?)*)\s+";
Regex l_regex = new Regex( l_pattern );
MatchCollection l_matches = l_regex.Matches( l_input1 );
System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator();
DateTime l_listStart = DateTime.Now;
List<string> l_elements = new List<string>();
int l_previousIndex = 0;
int l_previousLength = 0;
// The final MoveNext(), which returns false, takes 2 seconds.
while ( l_matchEnumerator.MoveNext() ) {
Match l_match = (Match) l_matchEnumerator.Current;
int l_start = l_previousIndex + l_previousLength;
int l_length = l_match.Index - l_start;
l_elements.Add( l_input1.Substring( l_start, l_length ) );
l_previousIndex = l_match.Index;
l_previousLength = l_match.Length;
}
Console.WriteLine( "List Composition Time: " + ( DateTime.Now - l_listStart ).TotalMilliseconds.ToString() );
string[] l_terms = l_elements.ToArray();
Console.WriteLine( String.Join( "\n", l_terms ) );
Console.ReadKey( true );
}
}
}
输出
(这正是我得到的。)
one
"two three"
four
five:"six seven"
eight
"nine ten"
最佳答案
尝试将正则表达式更改为以下内容:
(?<=^((?>[^"]*)(["][^"]*["])?)*)\s+
此处唯一的变化是将 [^"]*
放入 atomic group 中,以防止发生 catastrophic backtracking。
注意:上面的正则表达式显然没有使用我不熟悉的C#正则表达式字符串语法,但我认为应该是以下内容:
@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)\s+";
为什么会发生灾难性的回溯:
找到所有有效匹配项后,尝试的下一个匹配项是最后引用部分内的空间。后视将失败,因为空格前有奇数个引号。
此时,lookbehind 中的正则表达式将开始回溯。 anchor 意味着它总是从字符串的开头开始,但它仍然可以通过从它匹配的末尾删除元素来回溯。让我们看看 lookbehind 中的正则表达式:
^([^"]*(["][^"]*["])?)*
由于引用的部分是可选的,因此可以将它们作为正则表达式回溯删除。对于不在引号部分内的每个非引号字符 block ,在回溯之前,每个字符都将作为正则表达式开头的 [^"]*
的一部分进行匹配。作为回溯从该部分开始,最后一个字符将从 [^"]*
匹配的内容中删除,并将由外部重复拾取。此时它变得非常类似于上面灾难性回溯链接中的示例。
关于c# - 正则表达式花费了惊人的长时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12499764/