python - 为什么 all() 比使用 for-else 和 break 慢？

Question

我一直在玩problem 7在欧拉项目中，我注意到我的两种主要查找方法非常相似，但运行速度却截然不同。

#!/usr/bin/env python3

import timeit

def lazySieve (num_primes):
    if num_primes == 0: return []
    primes = [2]
    test = 3
    while len(primes) < num_primes:
        sqrt_test = sqrt(test)
        if all(test % p != 0 for p in primes[1:]):  # I figured this would be faster
            primes.append(test)
        test += 2
    return primes

def betterLazySieve (num_primes):
    if num_primes == 0: return []
    primes = [2]
    test = 3
    while len(primes) < num_primes:
        for p in primes[1:]: # and this would be slower
            if test % p == 0: break
        else:
            primes.append(test)
        test += 2
    return primes

if __name__ == "__main__":

    ls_time  = timeit.repeat("lazySieve(10001)",
                             setup="from __main__ import lazySieve",
                             repeat=10,
                             number=1)
    bls_time = timeit.repeat("betterLazySieve(10001)",
                             setup="from __main__ import betterLazySieve",
                             repeat=10,
                             number=1)

    print("lazySieve runtime:       {}".format(min(ls_time)))
    print("betterLazySieve runtime: {}".format(min(bls_time)))

运行时输出如下:

lazySieve runtime:       4.931611961917952
betterLazySieve runtime: 3.7906006319681183

与 this 不同问题，我不只是想要任何/全部的返回值。

all() 的返回是否如此缓慢，以至于 if overrides 它在除大多数情况外的所有情况下都可以使用？ for-else 中断是否比短路的 all() 更快？

你觉得怎么样？

编辑:添加到 Reblochon Masque 建议的平方根循环终止检查中

更新: ShadowRanger 的 answer是正确的。

更改后

all(test % p != 0 for p in primes[1:])

到

all(map(test.__mod__, primes[1:]))

我记录了以下运行时间的减少:

lazySieve runtime:       3.5917471940629184
betterLazySieve runtime: 3.7998314710566774

编辑:删除了 Reblochon 的加速以使问题保持​​清晰。对不起，伙计。

Answer 1

这是几个问题的组合:

1. 调用内置函数以及加载和执行生成器代码对象的设置成本较低，因此对于要测试的少量素数，设置成本会淹没每次测试的成本
2. 生成器表达式建立一个内部作用域；未迭代的变量需要经过正常 LEGB lookup成本，因此 all 生成器表达式中的每次迭代都需要查找 test 以确保它没有更改，并且它通过 dict 查找(其中局部变量查找是固定大小数组中的廉价查找)
3. 生成器有少量开销，特别是在跳入和跳出 Python 字节代码时(all 是在 CPython 中的 C 层实现的)

可以采取的措施来最小化或消除差异:

1. 运行更大的迭代来进行测试(以尽量减少设置成本的影响)
2. 显式地将 test 拉入生成器的本地范围，例如作为一个愚蠢的黑客 all(test % p != 0 for test in (test,) for p in primes[1:])
3. 通过将 map 与 C 内置函数一起使用，从进程中删除所有字节码执行，例如all(map(test.__mod__, primes[1:])) (这也恰好实现了#2，通过预先查找 test.__mod__ 一次，而不是每个循环一次)

有了足够大的输入，#3 有时可以胜过您的原始代码，至少在 Python 3.5 上(我在 ipython 中进行了微基准测试)，具体取决于许多因素。它并不总是获胜，因为字节码解释器对 BINARY_MODULO 进行了一些优化，以获取适合 CPU 寄存器的值，从而显式直接跳到 int.__mod__ 代码绕过，但它通常表现得非常相似。