.Net简单正则表达式的二次复杂度

Question

在构建一个简单的正则表达式时，我发现随着输入大小的增加，它的性能表现非常奇怪。

这是另一个非常基本的正则表达式，具有类似的行为：

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）如果我的期望和基准测试正确，可能会有哪些问题？

非常感谢您提供的任何帮助。

- Pragmateek

---

你可能需要增加样本大小，如果时间以秒为单位而不是100个滴答，则您的时间提供程序可能不如您期望的那样准确。 - Darren Kopp

@DarrenKopp：好的评论，但在这种情况下，样本大小与实验一致：它只需要十分之一毫秒，即使使用更大的样本大小，我也会得到相同的行为。谢谢。 - Pragmateek

实际上，在您指出的这个链接中，有很多建议，也有如何优化正则表达式和避免回溯等方面的建议。我认为在某些情况下需要更复杂的语法。 https://learn.microsoft.com/en-us/dotnet/standard/base-types/backtracking-in-regular-expressions?redirectedfrom=MSDN - David Constantine

Answer 1

< p > Regex.Match 函数搜索子串匹配：引擎尝试从字符串的任何索引开始匹配表达式，这会产生一个O(n²)算法。您可以通过将正则表达式锚定到字符串的开头来实现线性性能：

Regex regex = new Regex("^a+b$", RegexOptions.Compiled);

- Joni

---

当然 >_<！使用这种方法，我的时间复杂度是线性的，显然，我的复杂度是二次的：滑动窗口在字符串上的应用是缺少的维度。感谢您的快速回答 :) - Pragmateek