Python环境下分组合并累加分数比线性累加更快的性能差异原因咨询

阿华AIGC实验室

2026-3-31

嘿，我最近在折腾Python里高精度分数累加的性能优化，遇到了一个让我困惑的现象——用**分组合并（归并式两两配对累加）**的方式计算分数和，居然比直接线性逐个累加要快将近40%！虽然理论上两种方式的总加法运算次数是一样的（都是n-1次分数加法，n是分数个数），但实际跑出来的性能差了不少。先给大家看看我的测试代码和结果，再聊聊我琢磨出的原因~

测试代码

from itertools import batched
from math import gcd

def arctan_derivative(x: int, y: int) -> tuple[int, int]:
    return y * y, x * x + y * y

def primitive_rationals_simple(denominator: int) -> list[tuple[int, int]]:
    assert isinstance(denominator, int) and denominator > 0
    result = []
    for numerator in range(denominator + 1):
        common = gcd(numerator, denominator)
        result.append((numerator // common, denominator // common))
    return result

def make_test_case(n: int) -> list[tuple[int, int]]:
    return [arctan_derivative(*frac) for frac in primitive_rationals_simple(n)]

# 线性累加方式
def test1(fracs: list[tuple[int, int]]) -> tuple[int, int]:
    num, den = 0, 1
    for tnum, tden in fracs:
        num, den = num * tden + tnum * den, den * tden
    return num, den

# 分组合并累加方式
def test2(fracs: list[tuple[int, int]]) -> tuple[int, int]:
    while (length := len(fracs)) > 1:
        carry = fracs.pop(-1) if length & 1 else None
        fracs = [(a * d + b * c, b * d) for (a, b), (c, d) in batched(fracs, 2)]
        if carry:
            fracs.append(carry)
    return fracs[0]

测试结果

data = make_test_case(360)
print(test1(data) == test2(data))  # 输出: True（结果一致）

%timeit test1(data)  # 271 μs ± 9.95 μs per loop
%timeit test2(data)  # 166 μs ± 948 ns per loop
print((271 - 166)/271)  # 输出: ~0.387，快了将近40%

为什么分组合并更快？

我一开始完全摸不着头脑，后来仔细琢磨Python解释器的工作机制，总结出这几个关键原因：

列表推导式 vs Python级for循环：底层实现的效率鸿沟
test1用的是纯Python层面的for循环，每次迭代都要在Python解释器里执行变量赋值、算术运算等操作，循环n次就有n次Python级别的迭代开销。而test2用了列表推导式，它的内部循环是用C实现的，批量处理所有分数对的加法，能大幅减少Python解释器的循环开销。比如n=360时，test1要跑360次Python循环，而test2只需要跑log₂(360)≈9次列表推导式，每次推导式的内部循环是C级别的，效率差不止一个量级。
内置函数batched的高效性
test2里的itertools.batched是Python 3.12+的内置函数，同样是C实现的，能高效地把列表分成两两一组，没有额外的Python级别的配对逻辑开销。如果自己用Python代码写分组逻辑，性能肯定会打折扣，但用batched直接把分组工作交给底层C代码，速度快很多。
内存访问的局部性优势
分组合并的方式每次处理的是列表中相邻的元素对，Python列表的内存布局是连续的指针数组，相邻元素的指针在内存里也是靠近的，CPU缓存的命中率更高。虽然这个影响比前两个小，但也是性能提升的一个辅助因素。
减少Python级别的变量更新次数
test1每次循环都要更新num和den两个变量，这是Python层面的赋值操作，次数多了累积的开销也不小。而test2的计算是批量在列表推导式里完成的，变量更新是在C层面批量处理，减少了Python级别的赋值次数。