在 C/Java 中处理正则表达式的速度比在 Python 中快多少？
How much faster are regular expressions processed in C/Java than in Python?
我正在寻找比较 python 和静态类型语言（如 C、Java 或 C++）之间的正则表达式速度的基准。我还想听听有关正则表达式的 Cython 性能的信息。
这可能更多地取决于个人实现而不是语言。
举个例子，有些模式在某些实现中是 O(N2)，但在其他实现中是 ~O(N)。具体来说，大多数 RE 实现都基于 NFA（非确定性有限状态自动机）。长话短说，这意味着他们可以并且会在某些情况下使用某些模式回溯。这给出了大致 O(N2) 复杂度。匹配相同模式的确定性有限状态自动机 (DFA) 从不回溯——它始终具有线性复杂性。同时，DFA 的编译阶段通常比 NFA 更复杂（并且 DFA 不具备 NFA 的所有功能）。
因此，对于许多不涉及任何回溯的简单模式，基于 NFA 的 RE 引擎很容易 运行 比基于 DFA 的引擎更快。但是，当基于 NFA 的 RE 引擎试图匹配一个模式而不是涉及回溯时，它可能（并且将会）大幅减速。在后一种情况下，基于 DFA 的引擎可能会快很多倍。
大多数 RE 库基本上都是从表示为字符串的正则表达式开始的。当你做一个基于 search/match 的 RE 时，大多数人会把它编译成他们的 NFA/DFA 的数据结构。该编译步骤需要一些时间（不是很多，但可能会变得很重要，尤其是当您使用许多不同的 RE 时）。少数 RE 引擎（例如 Boost XPressive）可以静态编译正则表达式——也就是说，RE 与程序的源代码同时编译。这可以从程序的执行时间中消除编译 RE 的时间，因此如果您的代码花费大量时间编译 RE，它可以从中获得实质性改进（但这独立于静态类型——至少据我所知，你无法在 Java 或 C 或示例中获得相同的结果）。一些其他语言（例如，D）提供了足够的功能，您几乎可以肯定地用它们做同样的事情，但我不知道您现在可以计划使用它们的实际实现。
我正在寻找比较 python 和静态类型语言（如 C、Java 或 C++）之间的正则表达式速度的基准。我还想听听有关正则表达式的 Cython 性能的信息。
这可能更多地取决于个人实现而不是语言。
举个例子，有些模式在某些实现中是 O(N2)，但在其他实现中是 ~O(N)。具体来说，大多数 RE 实现都基于 NFA（非确定性有限状态自动机）。长话短说，这意味着他们可以并且会在某些情况下使用某些模式回溯。这给出了大致 O(N2) 复杂度。匹配相同模式的确定性有限状态自动机 (DFA) 从不回溯——它始终具有线性复杂性。同时，DFA 的编译阶段通常比 NFA 更复杂（并且 DFA 不具备 NFA 的所有功能）。
因此，对于许多不涉及任何回溯的简单模式，基于 NFA 的 RE 引擎很容易 运行 比基于 DFA 的引擎更快。但是，当基于 NFA 的 RE 引擎试图匹配一个模式而不是涉及回溯时，它可能（并且将会）大幅减速。在后一种情况下，基于 DFA 的引擎可能会快很多倍。
大多数 RE 库基本上都是从表示为字符串的正则表达式开始的。当你做一个基于 search/match 的 RE 时，大多数人会把它编译成他们的 NFA/DFA 的数据结构。该编译步骤需要一些时间（不是很多，但可能会变得很重要，尤其是当您使用许多不同的 RE 时）。少数 RE 引擎（例如 Boost XPressive）可以静态编译正则表达式——也就是说，RE 与程序的源代码同时编译。这可以从程序的执行时间中消除编译 RE 的时间，因此如果您的代码花费大量时间编译 RE，它可以从中获得实质性改进（但这独立于静态类型——至少据我所知，你无法在 Java 或 C 或示例中获得相同的结果）。一些其他语言（例如，D）提供了足够的功能，您几乎可以肯定地用它们做同样的事情，但我不知道您现在可以计划使用它们的实际实现。