我正在寻找基准，以比较python和静态类型化语言（例如C，Java或C ++）之间的正则表达式速度。我也想听听Cython对正则表达式的性能。
这可能比语言更依赖于个人实现。
仅举例来说，某些模式在某些实现中为O（N 2），而在其他实现中为〜O（N）。具体而言，大多数RE实现都是基于NFA（不确定性有限状态自动机）。长话短说，这意味着他们可以并且在某些情况下会以某些模式回溯。这大致给出了O（N 2）的复杂度。与相同模式匹配的确定性有限状态自动机（DFA）不会回溯-它始终具有线性复杂度。同时，DFA的编译阶段通常比NFA复杂（并且DFA并不具备NFA的全部功能）。
因此，使用许多不涉及任何回溯的简单模式，基于NFA的RE引擎可能比基于DFA的引擎运行起来容易。但是，当基于NFA的RE引擎试图匹配模式而不涉及回溯时，它可能会（并且将会）大大降低速度。在后一种情况下，基于DFA的引擎可能会快很多倍。
大多数RE库基本上都从以字符串表示的正则表达式开始。当您进行基于RE的搜索/匹配时，大多数会将其编译为NFA / DFA的数据结构。该编译步骤需要一些时间（虽然不是很多，但可能会变得很重要，尤其是当您使用许多不同的RE时）。一些RE引擎（例如Boost XPressive）可以静态地编译正则表达式-也就是说，RE与程序的源代码同时编译。这样可以从程序的执行时间中省去编译RE的时间，因此，如果您的代码在编译RE上花费了大量时间，则可以从中获得实质性的改进（但这至少与静态类型无关-至少据我所知，在Java或C或示例中无法获得相同的效果）。其他几种语言（例如
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句