正则表达式速度：Python在VS2013下比C++11快六倍？

Question

Python的C正则表达式实现比我漏掉了什么，快了6倍吗？

Python版本：

import re
r=re.compile(r'(HELLO).+?(\d+)', re.I)
s=r"prefixdfadfadf adf adf adf adf he asdf dHello Regex 123"

%timeit r.search(s)

1000000 loops, best of 3: 1.3 µs per loop (769,000 per sec)

C++11版本：

#include<regex>
int main(int argc, char * argv[])
{
    std::string s = "prefixdfadfadf adf adf adf adf he asdf dHello Regex 123";
    std::regex my(R"((HELLO).+?(\d+))", regex_constants::icase);

    bench_utils::run(std::chrono::seconds(10),
        [&]{
        std::smatch match;
        bool found = std::regex_search(s, match, my);
    });       
    return 0;
}

Results in about ~125,000 searches/second

编辑： 这是bench_utils的代码:

namespace bench_utils
{
    template<typename T>    
    inline std::string formatNum(const T& value)
    {
            static std::locale loc("");
            std::stringstream ss;
            ss.imbue(loc);
            ss << value;
            return ss.str();
        }

    inline void run(const std::chrono::milliseconds &duration,
        const std::function<void() >& fn)
    {
        using namespace std::chrono;
        typedef steady_clock the_clock;
        size_t counter = 0;
        seconds printInterval(1);
        auto startTime = the_clock::now();
        auto lastPrintTime = startTime;
        while (true)
        {
            fn();
            counter++;
            auto now = the_clock::now();
            if (now - startTime >= duration)
                break;
            auto p = now - lastPrintTime;
            if (now - lastPrintTime >= printInterval)
            {
                std::cout << formatNum<size_t>(counter) << " ops per second" << std::endl;
                counter = 0;
                lastPrintTime = the_clock::now();
            }
        }
    }

}

- GabiMe

---

好的，我会尽力进行翻译。以下是需要翻译的内容：相关问题：https://dev59.com/-2Yq5IYBdhLWcg3wxjY7答案：在某些情况下，C++11正则表达式确实比Python的re模块慢。这可能是由于C++11正则表达式使用了确定性有限状态自动机（DFA）算法，而Python的re模块使用了回溯算法。回溯算法的一个缺点是它可能会导致指数级别的时间复杂度，这意味着它对于某些模式和输入可能会非常慢。然而，它也具有一些优点，例如能够支持更复杂的模式和更灵活的匹配选项。另一方面，DFA算法虽然通常比回溯算法快，但在某些情况下可能会导致更糟糕的性能。例如，在处理包含多个可选分支或重复元素的复杂模式时，DFA算法可能会生成大量的状态转换，从而导致更长的预处理时间和更大的内存消耗。因此，对于某些特定的模式和输入，Python的re模块可能比C++11正则表达式更快。但是，在许多情况下，C++11正则表达式应该比Python的re模块更快。 - devnull

我们怎么知道 bench_utils 是做什么的？它不是标准的 C++，我也没有看到包含该文件。 - Ali

你尝试过为C++使用不同的正则表达式库吗？ - Niklas B.

@GabiMe 现在我看到你的代码了，这里有两件事情我肯定不会在那个无限循环中做：（1）将要研究的函数作为重量级 std::function 传递进去，以及（2）在每次迭代中调用 the_clock::now();。我不知道它有多重要，但我可能不会在每次迭代中创建新的 std::smatch match;。无论如何，我会尽力确保 Python 代码和 C++ 代码尽可能地实现相同的功能。 - Ali

你尝试过其他正则表达式功能吗？比如不捕获、断言等等。 - quantum

Answer 1

首先要注意的是，在Python中，正则表达式（无论是使用“re”模块还是“regex”模块）都以“C语言的速度”进行，也就是说，实际的重型代码是用C语言编写的，因此至少对于较长的字符串，性能将取决于C正则表达式的实现。

有时候Python非常聪明，Python可以轻松执行数千万次操作，并且每秒可以创建数百万个对象-这比C慢一千倍，但如果我们谈论的是需要微秒级别的操作，Python的开销可能并不重要，它只会在每个函数调用中增加0.1微秒。

因此，在这种情况下，Python的相对缓慢并不重要。它在绝对意义上足够快，重要的是正则表达式函数执行的速度有多快。

我重新编写了C++示例，使其不受任何批评（希望如此，如有任何问题，请随时指出），实际上，它甚至不需要创建匹配对象，因为搜索仅返回布尔值（真/假）。

#include <regex>
#include <iostream>

int main(int argc, char * argv[])
{
    std::string s = "prefixdfadfadf adf adf adf adf he asdf dHello Regex 123";
    std::regex my(R"((HELLO).+?(\d+))", std::regex_constants::icase);

    int matches = 0;
    for (int i = 0; i < 1000000; ++i)
        matches += std::regex_search(s, my);


    std::cout << matches  << std::endl;
    return 0;
}

我写了一个相似的Python程序（尽管Python创建并返回了一个匹配对象），我的结果与你的完全一样。

C++: 6.661秒
Python: 1.039秒

我认为这里的基本结论是，Python的正则表达式实现比c++标准库强大得多。

它也比Go快

前段时间，只是为了好玩，我比较了Python和Go的正则表达式性能。结果Python至少快了两倍。

结论是，Python的正则表达式实现非常好，您绝对不应该查找Python以获取改进后的正则表达式性能。正则表达式所做的工作基本上耗时足够长，以至于Python的开销实际上根本无关紧要，并且Python有一个很棒的实现（新的regex模块通常比re还要快）。

- Blake Walsh

Answer 2

使用timeit进行基准测试是错误的，因为它只给出了3次中的最佳结果，并没有进行统计学差异测试。

这是你的代码问题，而不是语言本身的问题。

以下是需要优化的几个方面：

1. 将函数作为std::function传递会使C++代码变慢； 2. 在每次迭代中调用时钟函数； 3. 在每次迭代中创建新对象，例如std::smatch match； 4. run函数； 5. 没有预编译正则表达式。

我还想知道你正在运行哪些优化。

run()函数做的太多了。请修复它。 :)

- Good Person

---

1. 这是一个无效的论点。Python 在每个操作上都有更多的开销，所以 如果 它是一个重要的论点，那么它将成为 C++ 的一个 负面 论点。即使有这 微小的 开销，C++ 应该比 Python 更快，因为它避免了许多 Python 版本存在的其他开销。同样，3. 也是无效的，因为 Python 每次调用 search 都会创建一个新的匹配对象，而 C++ 应该在这方面更快。实际重要的点是 2 和 5，特别是 5 我认为。

- Bakuriu