在构建一个简单的 regex 时,我发现它在输入大小增加时具有非常奇怪的性能 配置文件。
这是另一个非常基本的正则表达式,具有类似的行为:
a+b
我用一个简单的基准对其进行了分析:
Regex regex = new Regex("a+b", RegexOptions.Compiled);
const int maxInputSize = 100;
const int n = 1000;
string input = "";
Stopwatch stopwatch = new Stopwatch();
for (int inputSize = 1; inputSize <= maxInputSize; ++inputSize)
{
input += 'a';
stopwatch.Restart();
for (int i = 0; i < n; ++i)
{
regex.Match(input);
}
stopwatch.Stop();
Console.WriteLine(stopwatch.Elapsed.Ticks);
}
它对字符串“a”、“aa”、“aaa”...运行正则表达式,并测量每个长度的字符串进行 n 次匹配所花费的时间。
我知道回溯问题(例如,如果正则表达式类似于(a+a+)+b
),但在这种情况下,即使考虑回溯我预计线性复杂度。
例如,如果我们想匹配 n 次 'a',这是我天真的期望的工作流程:
take first 'a'
take second 'a'
...
take last 'a'
ooops nothing more to take => backtracking
release one 'a' and try to match 'b', nothing => backtracking
...
release second 'a' and retry to match 'b', nothing => backtracking
release first 'a'
ooops we're back at the beginning => no match
所以它应该执行类似2n 的操作。
(该文档似乎证实了复杂度应该是线性的:http://msdn.microsoft.com/en-us/library/dsy130b4.aspx)
但我观察到的是二次复杂度:
所以我的问题是:
- 1) 我对线性复杂度的期望是否不合理?
- 2) 如果是,我在正则表达式匹配方面遗漏了什么?
- 3) 如果不是,我的基准是否有缺陷?为什么?
- 4) 如果我的期望和基准是正确的,那么问题可能是什么?
在此先感谢您的任何意见。
最佳答案
Regex.Match
函数搜索子字符串匹配:引擎尝试匹配从字符串的任何索引开始的表达式,给出 O(n²) 算法。您可以通过将正则表达式锚定到字符串的开头来实现线性性能:
Regex regex = new Regex("^a+b$", RegexOptions.Compiled);
关于c# - .Net 简单正则表达式二次复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19204168/