c++ - regex_match (“”为8秒，regex (“.{40000}”));?

更新2:实际上是regex(".{40000}");。仅此一项就需要花费很多时间。为什么？
regex_match("", regex(".{40000}"));在我的PC上耗时将近8秒钟。为什么？难道我做错了什么？我正在i7-6700的Windows 10上使用MinGW的gcc 4.9.3。

这是完整的测试程序:

#include <iostream>
#include <regex>
#include <ctime>
using namespace std;

int main() {
    clock_t t = clock();
    regex_match("", regex(".{40000}"));
    cout << double(clock() - t) / CLOCKS_PER_SEC << endl;
}

我如何编译和运行它:

C:\Users\ ... \coding>g++ -std=c++11 test.cpp

C:\Users\ ... \coding>a.exe
7.643

更新:看起来给定数字中的时间是二次方。将其加倍的时间大约是原来的四倍:

  10000   0.520 seconds (factor 1.000)
  20000   1.922 seconds (factor 3.696)
  40000   7.810 seconds (factor 4.063)
  80000  31.457 seconds (factor 4.028)
 160000 128.904 seconds (factor 4.098)
 320000 536.358 seconds (factor 4.161)

代码:

#include <regex>
#include <ctime>
using namespace std;

int main() {
    double prev = 0;
    for (int i=10000; ; i*=2) {
        clock_t t0 = clock();
        regex_match("", regex(".{" + to_string(i) + "}"));
        double t = double(clock() - t0) / CLOCKS_PER_SEC;
        printf("%7d %7.3f seconds (factor %.3f)\n", i, t, prev ? t / prev : 1);
        prev = t;
    }
}

仍然不知道为什么是。这是一个非常简单的正则表达式和空字符串(尽管短的非空字符串也是如此)。它应该立即失败。正则表达式引擎只是奇怪又糟糕吗？

最佳答案

因为它要快...

很有可能将此正则表达式转换为更易于运行的另一种表示形式(状态机或其他形式)。 C#甚至允许生成代表正则表达式的运行时代码。

在您的情况下，您可能会遇到该转换中一些带有O(n^2)复杂性的错误。