8

我正在使用std::regex，在阅读中定义的各种常量时std::regex_constants，我​​遇到了std::optimize，阅读它，听起来它在我的应用程序中很有用（我只需要一个正则表达式的实例，在一开始就初始化，但它是在整个加载过程中多次使用）。

根据工作文件 n3126（第 1077 页）std::regex_constants::optimize，：

指定正则表达式引擎应该更多地关注正则表达式匹配的速度，而不是构建正则表达式对象的速度。否则，它对程序输出没有可检测的影响。

我很好奇将执行哪种类型的优化，但似乎没有太多关于它的文献（事实上，它似乎是未定义的），我发现的唯一一件事是在cppreference.com，表示std::regex_constants::optimize：

指示正则表达式引擎使匹配更快，但可能会降低构造速度。例如，这可能意味着将非确定性 FSA 转换为确定性 FSA。

但是，我没有正式的计算机科学背景，虽然我知道 FSA 是什么的基础知识，并且了解确定性 FSA（每个状态只有一个可能的下一个状态）和非 FSA 之间的基本区别。确定性 FSA（具有多个潜在的下一个状态）；我不明白这如何提高匹配时间。另外，我很想知道在各种 C++ 标准库实现中是否还有其他优化。

4

2 回答 2

3

在Jeffrey Friedl的Mastering Regular Expressions中有一些关于正则表达式引擎和性能权衡（远远超过 stackoverflow 答案）主题的有用信息。

值得注意的是，作为 N3126 的来源的 Boost.Regex 记录optimize为“目前对 Boost.Regex 没有影响”。

附言

实际上，它似乎是实现定义的

不，它未指定。实现定义意味着需要一个实现来定义行为的选择。实现不需要记录他们的正则表达式引擎是如何实现的或者optimize标志有什么（如果有的话）差异。

PS 2

在各种 STL 实现中

std::regex不是 STL 的一部分，C++ 标准库与 STL 不同。

于 2012-07-21T13:53:09.767 回答
2

请参阅http://swtch.com/~rsc/regexp/regexp1.html以获得关于基于 NFA 的正则表达式实现如何避免在某些情况下在 DFA 匹配器中发生的指数回溯的很好的解释。

于 2012-07-21T13:54:09.437 回答