为什么Python中模拟的原子分组比非捕获分支正则表达式性能更低？

问题描述 #

Python re 模块没有原生原子分组特性，但可以对其进行模拟。原本认为由于原子分组不会尝试组内所有可选分支，其性能会比简单的分支正则更快，但实际测试情况并非如此，测试代码如下：

import re
import timeit
import random

random.seed(42)

words = ["tricky", "liquid", "sleepy", "crowded", "half", "secretary", "roll", "educate", "medical", "closed",
         "unaccountable", "earthy", "permit", "pleasant", "confuse", "enter", "land", "encourage", "connection",
         "mindless", "spicy",
         "cracker", "twist"]

atomic_group = re.compile(
    r"(?=(unaccountable|l(?:and|iquid)|half|t(?:ricky|wist)|roll|p(?:ermit|leasant)|s(?:picy|ecretary|sleepy)|e(?:ducate|arthy|n(?:ter|courage))|m(?:indless|edical)|c(?:r(?:owded|racker)|on(?:fuse|nection)|losed)))\1")
non_atomic_group = re.compile(
    r"(?:unaccountable|l(?:and|iquid)|half|t(?:ricky|wist)|roll|p(?:ermit|leasant)|s(?:picy|ecretary|sleepy)|e(?:ducate|arthy|n(?:ter|courage))|m(?:indless|edical)|c(?:r(?:owded|racker)|on(?:fuse|nection)|losed))")

sentence = " ".join(random.choices(words, k=10000))

print(timeit.timeit("atomic_group.findall(sentence)",
                    setup="from __main__ import atomic_group, sentence",
                    number=10))

print(timeit.timeit("non_atomic_group.findall(sentence)",
                    setup="from __main__ import non_atomic_group, sentence",
                    number=10))

输出结果

0.036498754999999994
0.028361783

更大数据集下也观测到了相同的表现，有对应的性能对比图，图中的len(data)代表递增的句子（由60个单词组成的字符串）数量，复现代码可公开获取。

请问假设哪里存在错误？另外更通用的问题是，在Python中如何编写仅尝试分支中的一个匹配项、不会回溯尝试其他分支的正则表达式？

回答 #

假设错误的核心原因 #

• 测试场景未触发回溯：你选用的所有备选分支没有重叠前缀，每个输入位置最多只有一个分支能匹配，非原子分组在这种场景下本身就不会尝试其他分支，原子分组避免回溯的收益完全无法体现。
• 你使用的环视+反向引用模拟原子分组的方案本身有额外开销：正向环视(?=...)需要先扫描当前位置后的内容完成组内匹配，后续的\1还要再对同一内容做一次匹配，相当于同一段文本重复匹配两次，这部分纯额外开销在无回溯场景下直接导致模拟的原子分组性能比普通非捕获分组更差。

Python实现无回溯分支匹配的方案 #

1. 使用高版本Python原生支持的原子分组：Python 3.11及以上版本的标准库re模块已经原生支持原子分组语法(?>...)，无需额外模拟，原生实现的性能开销远低于环视模拟方案，可以直接实现匹配后不回溯组内分支的效果。
2. 从正则写法层面减少回溯可能：
   • 把长分支、高频匹配分支放在分支列表的最前面，提前命中匹配减少不必要的分支遍历
   • 合并分支的公共前缀，例如把abort|about|above改写为ab(?:ort|out|ove)，从根源上避免前缀重叠导致的回溯
3. 使用第三方正则库：如果需要兼容低版本Python，且有大量复杂正则的性能需求，可以使用第三方regex库，它原生支持原子分组、占有量词等高级正则特性，复杂场景下的性能表现优于标准库re。

内容的提问来源于stack exchange，提问作者Dani Mesejo