输入字符串的微小差异如何导致 std::regex_search 性能的巨大差异

How can a small difference in input string cause a large difference in std::regex_search performance

提问人:Peter Jaspers 提问时间:10/25/2023 最后编辑:Peter Jaspers 更新时间:10/25/2023 访问量:45

问:

字符串的微小变化怎么可能引起这么大的变化 性能差异。我的正则表达式错了吗? 目的是提取两个标记“|>”之间的(可能是多行字符串)。 我使用 Visual Studio 和 Microsoft C++ 编译器编译了此代码。command

    bool testCommandMatching() {
        const std::string group(R"(
                gcc 
                src\hello.c 
               -o bin\hello 
            )");
        const std::regex cmdRe(R"(^\|>((?:.*\s*)*)\|>)");
        bool bothMatched = true;
        {
            std::cmatch match;
            const std::string command(R"(|>
                gcc 
                src\hello.c 
               -o bin\hello 
            |>)");
            auto start = std::chrono::system_clock::now();
            bool matched = std::regex_search(command.c_str(), match, cmdRe, std::regex_constants::match_continuous);
            auto end = std::chrono::system_clock::now();
            // elapsed is less than 10 ms
            auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
            bothMatched = bothMatched && group == (matched ? match[1] : std::string(""));
        }
        {
            std::cmatch match;
            const std::string command(R"(|>
                gcc 
                src\hello.c 
               -o bin\hello 
            |> bin\hello)");
            auto start = std::chrono::system_clock::now();
            bool matched = std::regex_search(command.c_str(), match, cmdRe, std::regex_constants::match_continuous);
            auto end = std::chrono::system_clock::now();
            // elapsed is more than 1000 ms. How is this possible?
            auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
            bothMatched = bothMatched && group == (matched ? match[1] : std::string(""));
        }
        return bothMatched;
    }

正则表达式 性能 多行

评论

1赞 The fourth bird 10/25/2023
如果要匹配到最后一次匹配^\|>(.*(?:\r?\n.*)*)\|>
2赞 Jérôme Richard 10/26/2023
PCRE 正则表达式的执行时间可能呈指数级增长,因此输入中的一个附加字符可以使性能提高一倍以上。类似的事情可能会导致这种情况。因此,您需要小心量词。在这种情况下,贪婪/懒惰的运算符有时会有所帮助,但最好的办法是重写正则表达式以避免这种模式。我认为应该是你的正则表达式有问题。或者,您可以使用生成确定性自动机的正则表达式库(例如 Google 的 Re2),以便保证解析在多项式时间内运行(实际上是线性 AFAIK)。.*.*.*(?:.*\s*)*
1赞 jhnc 10/26/2023
拉斯·考克斯(Russ Cox)的系列文章提供了详尽的解释
1赞 Casimir et Hippolyte 10/29/2023
@jhnc:如果你想要一些有效的东西,请使用带有所有格量词的展开模式:regex101.com/r/QbwiIY/1
1赞 Casimir et Hippolyte 10/29/2023
也可以将非捕获组更改为原子组:(?>.*\s*)*

答: 暂无答案