替换整个字符串比只替换它的第一个字符更快

Question

我尝试用 b 替换给定大字符串中的字符 a。我做了一个实验——首先我在整个字符串中替换它，然后我只在它的开头替换它。

import re
# pattern = re.compile('a')
pattern = re.compile('^a')
string = 'x' * 100000

pattern.sub('b', string)

我预计替换开头必须比替换整个字符串快得多，因为您只需检查 1 个位置而不是 100000 个位置。我做了一些测量：

python -m timeit --setup "import re; p=re.compile('a'); string='x'*100000" "p.sub('b', string)"
10000 loops, best of 3: 19.1 usec per loop

python -m timeit --setup "import re; p=re.compile('^a'); string='x'*100000" "p.sub('b', string)"
1000 loops, best of 3: 613 usec per loop

结果表明，相反，尝试替换整个字符串的速度要快大约 30 倍。你会期待这样的结果吗？你能解释一下吗？

Answer 1

Pythonre模块中提供的功能没有基于anchors进行优化。特别是，尝试在每个位置应用正则表达式的函数 - .search、.sub、.findall 等 - 即使正则表达式只能在开头匹配时也会这样做。即，即使没有指定 multi-line 模式，这样 ^ 也只能匹配字符串的开头，内部调用不是 re-routed。因此：

$ # .match only looks at the first position regardless
$ python -m timeit --setup "import re; p=re.compile('a'); string='x'*100000" "p.match(string)"
2000000 loops, best of 5: 155 nsec per loop
$ python -m timeit --setup "import re; p=re.compile('^a'); string='x'*100000" "p.match(string)"
2000000 loops, best of 5: 157 nsec per loop
$ # .search looks at every position, even if there is an anchor
$ python -m timeit --setup "import re; p=re.compile('a'); string='x'*100000" "p.search(string)"
10000 loops, best of 5: 22.4 usec per loop
$ # and the anchor only adds complexity to the matching process
$ python -m timeit --setup "import re; p=re.compile('^a'); string='x'*100000" "p.search(string)"
500 loops, best of 5: 746 usec per loop

虽然 re 没有针对锚点进行优化，但它确实针对模式开始时可能发生的其他几件事进行了优化。其中一项优化是针对模式 starting with a single constant character:

    if (prefix_len == 1) {
        /* pattern starts with a literal character */
        SRE_CHAR c = (SRE_CHAR) prefix[0];
#if SIZEOF_SRE_CHAR < 4
        if ((SRE_CODE) c != prefix[0])
            return 0; /* literal can't match: doesn't fit in char width */
#endif
        end = (SRE_CHAR *)state->end;
        state->must_advance = 0;
        while (ptr < end) {
            while (*ptr != c) {
                if (++ptr >= end)
                    return 0;
            }
            ...

此优化执行简单的字符比较以跳过不以所需字符开头的候选匹配项，而不是调用完整的匹配引擎。这种优化是未锚定正则表达式如此快的原因 - 代码中有 3 种独立的优化，一种针对单个常量字符，一种针对 multi-character 常量前缀，一种针对字符 class，但对于 ^ 锚点来说什么都没有。

我认为可以合理地针对此提交错误报告 - 没有实施如此明显的优化显然违反了预期。除此之外，虽然使用 .match 将 .search 替换为锚点很容易，但将 .sub 替换为锚点并不那么简单 - 你必须 .match，检查结果，然后自己在字符串上调用 .replace。

如果您需要锚定到字符串 的结尾而不是 开头，这会变得更加困难；我记得古老的 Perl 建议首先尝试反转字符串，但通常很难编写与您想要的反转相匹配的模式。

替换整个字符串比只替换它的第一个字符更快

Replacing whole string is faster than replacing only its first character

python

regex

time