正则表达式在C/Java中的处理速度比Python快多少？

Question

我正在寻找比较Python和静态类型语言（如C、Java或C++）之间正则表达式速度的基准测试。我还想了解Cython在正则表达式方面的性能。

- Jeff Mandell

---

CPython的正则表达式引擎是用C语言编写的。 - abarnert

另外，您为什么会期望静态类型与正则表达式引擎有任何关系呢？正则表达式只是对字节流或字符流进行操作。 - abarnert

而且，Cython 的性能与 CPython 中的纯 Python 代码大致相同，因为它只是从 _re 模块中调用相同的 C 编写函数。 - abarnert

@abarnert 謝謝你告訴我，我錯誤地假設了。 - Jeff Mandell

这通常是将C与C与C进行比较，并且更多地涉及库的问题，因为任何语言中大多数快速正则表达式函数都是使用C / C ++等语言本地实现以提高速度。正则表达式特别适合本地实现，因为紧密而性能关键的循环逻辑被很好地隐藏起来。 - user4842163

Answer 1

这更可能取决于个别实现而不是语言本身。

例如，某些模式在某些实现中是O(N ²)，但在其他实现中是 ~O(N)。具体来说，大多数正则表达式实现都基于非确定有限状态自动机（NFA）。简而言之，这意味着它们可以并且会在某些情况下回溯某些模式。这导致了大约O(N ²)的复杂度。匹配相同模式的确定性有限状态自动机（DFA）永远不会回溯 - 它总是具有线性复杂度。同时，与NFA相比，DFA的编译阶段通常更复杂（并且DFAs没有所有NFA的功能）。

因此，对于许多不涉及回溯的简单模式，基于NFA的正则表达式引擎可能比基于DFA的引擎运行得更快。但是，当基于NFA的正则表达式引擎试图匹配涉及回溯的模式时，它可能会（并且会）显着减慢速度。在后一种情况下，基于DFA的引擎可能轻松地快几倍。

大多数正则表达式库基本上从表示为字符串的正则表达式开始。当您进行基于正则表达式的搜索/匹配时，大多数将其编译为NFA / DFA的数据结构。该编译步骤需要一些时间（不是很多，但如果您使用许多不同的RE，则可能变得显着）。一些RE引擎（例如Boost XPressive）可以静态地编译正则表达式 - 也就是说，RE与程序源代码同时编译。这可以消除从程序执行时间中编译RE的时间，因此，如果您的代码在编译RE上花费了大量时间，则可以从中获得实质性的改进（但这与静态类型无关 - 至少据我所知，您不能在Java或C中获得相同的结果，例如）。一些其他语言（例如D）提供足够的功能，您几乎肯定可以使用它们做到相同的事情，但我不知道它们是否有可用于计划使用的实际实现。

- Jerry Coffin

---

有些模式使用第一种实现方式是O(2^N)，但使用第二种则会失败。 :) - abarnert

@abarnert：但（至少如果我没有记错的话），那些模式在技术上并不是正则表达式。 - Jerry Coffin

当然，但我愿意打赌，OP（像大多数此时不在研究生阶段的人一样...）在说“正则表达式”时实际上是指“Perl风格的正则表达式”。如果我没记错，即使Google的RE2实现也不能被定义为正则语言。 - abarnert

@JerryCoffin：虽然您的回答很有见地，但我正在寻找Python和C之间针对相同Perl风格正则表达式的基准墙时比较。我有一个Python正则表达式，它很慢。我想看看是否值得学习所需的C语言来转换我的程序子集以获得性能提升。 - Jeff Mandell

@JeffM：也许你可以发布相关的正则表达式，但我立刻猜到，在C语言中仅使用正则表达式不会有太大的区别。如果你想要明显的差异，你需要做一些不同的事情（例如，使用基于确定有限状态自动机的正则表达式引擎或者根本不使用实际的正则表达式进行搜索）。 - Jerry Coffin