替换整个字符串比仅替换第一个字符更快

Question

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

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

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

$ # .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没有针对锚点进行优化，但它确实针对模式开始时可能发生的其他一些事情进行了优化。其中一项优化是针对以单个常量字符开头的模式：

    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 种单独的优化，一种针对单个常量字符，一种针对多字符常量前缀，一种针对字符类，但没有针对^锚。

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

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