为何divmod()比连续除法+取余的运行速度更慢？

我尝试优化自己的因式分解函数，最初版本在循环中先后执行整数除法n //= p和取余n % p操作。为优化性能，我将其替换为理应一步完成相同操作的divmod()函数，得到优化后的版本。随后使用timeit模块测试，测试范围为range(10**7)，结果显示优化版本性能反而下降50%：

• 原版本耗时：170.23512620001566
• 优化版本耗时：257.1009666999744

原函数代码 #

def factorize1(n: int, /) -> Factorization:
    """Return dictionary, where keys are all prime factors of natural n
    and values are their exponents.
    """

    if n < 2:
        return {}

    factorization: Factorization = {}
    
    # Divide by 2**r and 3**r
    for p in (2, 3):
        while n % p == 0:
            factorization[p] = factorization.get(p, 0) + 1
            n //= p
            
    attempt: int = 5
    delta: int = 2
    maxFactor: int = math.isqrt(n)
    while n > 1 and attempt <= maxFactor:
        oldN: int = n
        while n % attempt == 0:
            factorization[attempt] = factorization.get(attempt, 0) + 1
            n //= attempt
            
        if n < oldN:
            maxFactor = math.isqrt(n)
            
        attempt += delta
        delta = 6 - delta    # switch 2 <-> 4

    # Biggest prime factor
    if n > 1:
        factorization[n] = 1

    return factorization

优化后函数代码 #

def factorize2(n: int, /) -> Factorization:
    """Return dictionary, where keys are all prime factors of natural n
    and values are their exponents.
    """

    if n < 2:
        return {}

    factorization: Factorization = {}
    
    # Divide by 2**r and 3**r
    for p in (2, 3):
        q, r = divmod(n, p)
        while r == 0:
            factorization[p] = factorization.get(p, 0) + 1
            n = q
            q, r = divmod(n, p)
            
    attempt: int = 5
    delta: int = 2
    maxFactor: int = math.isqrt(n)
    while n > 1 and attempt <= maxFactor:
        oldN: int = n
        q, r = divmod(n, attempt)
        while r == 0:
            factorization[attempt] = factorization.get(attempt, 0) + 1
            n = q
            q, r = divmod(n, attempt)
        
        if n < oldN:
            maxFactor = math.isqrt(n)
            
        attempt += delta
        delta = 6 - delta    # switch 2 <-> 4

    # Biggest prime factor
    if n > 1:
        factorization[n] = 1

    return factorization

测试代码 #

import timeit

limit = 10**7
number = 1

print(timeit.timeit(f'for n in range({limit}): factorize1(n)', number = number, globals = globals()))
print(timeit.timeit(f'for n in range({limit}): factorize2(n)', number = number, globals = globals()))

性能下降的核心原因 #

1. 非因子场景的多余计算
   原版本中，while n % p == 0仅在余数为0时才执行除法操作。对于绝大多数无法被p整除的数，只需要一次取余判断就跳出循环。
   而优化版本中，无论当前数是否能被整除，每次循环前都先调用divmod()计算商和余数——这意味着非因子场景下，优化版本多做了一次不必要的除法计算，而取余操作的开销远小于完整的divmod()调用。

2. 局部变量的额外开销
   优化版本每次循环都需要创建并赋值q、r两个局部变量，频繁的变量绑定操作会累积额外性能损耗，相比原版本直接操作n的方式更耗时。

3. 解释器底层优化差异
   Python解释器对%、//=这类基础运算符有专门的字节码优化，执行效率极高；而divmod()是内置函数，调用时需要额外的栈帧创建、参数传递等开销。在遍历10^7次的高频场景下，这种微小的开销会被无限放大。

验证方法 #

可以测试单个质数的因式分解耗时，比如factorize1(10000003)和factorize2(10000003)，会发现优化版本耗时明显更高——因为它在每个attempt上都先执行了divmod()，而原版本仅做取余判断就跳过循环。

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