2

我有接下来的 2 块代码：

def replace_re(text):
    start = time.time()
    new_text = re.compile(r'(\n|\s{4})').sub('', text)
    finish = time.time()
    return finish - start

def replace_builtin(text):
    start = time.time()
    new_text = text.replace('\n', '').replace('    ', '')
    finish = time.time()
    return finish - start

比我用文本参数调用这两个函数（一个网页的大约 500kb 源代码）。我认为replace_re()会快得多，但结果是下一个：

  1. replace_builtin()~ 0.008 秒
  2. replace_re()~ 0.035 秒（慢了近 4.5 倍！！！）

这是为什么？

4

4 回答 4

7

因为正则表达式比固定字符串替换复杂 4.5 倍以上。

于 2012-06-29T08:35:35.857 回答
5

因为re必须生成一个 FSM。然后用它来处理字符串。而替换可以使用更接近 lib/OS 级别的底层字符串处理函数。

于 2012-06-29T08:39:32.953 回答
3

考虑每个空格字符在源字符串中发生的情况——正则表达式引擎必须探索接下来的三个字符以查看它们是否也是空格。因此，每个空格本质上还涉及查看下一个字符。大多数 RE 引擎写得并不那么……直截了当地说……但它本质上意味着引擎必须返回到启动状态，并可能丢弃它在之前构建的匹配状态上建立的数据。

然而，在字符串中搜索固定模式（四个空格）实际上可以在亚线性时间内完成。我不知道 Pythonreplace()是否以这种方式实现，但希望他们能够很好地使用这些工具。

于 2012-06-29T08:43:16.087 回答
3

经验法则

固定字符串匹配应该总是比正则表达式匹配更快。你可以用谷歌搜索各种基准，或者做你所做的并执行你自己的，但通常你可以假设这将是正确的，除非（可能）在一些不寻常的边缘情况下。

为什么正则表达式更慢

为什么这是真的与固定字符串匹配没有回溯、编译步骤、范围、字符类或许多其他减慢正则表达式引擎速度的特性有关。当然有优化正则表达式匹配的方法，但我认为在常见情况下它不太可能击败对字符串的索引。

使用源

如果您想要更好的解释，您可以随时查看相关模块的源代码，了解它们是如何工作的。这肯定会为您提供更多信息，说明为什么任何特定实现会如此执行。

于 2012-06-29T08:47:03.217 回答