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

Question

我一直在玩 Euler 项目的 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)))

这运行s 具有以下输出：

lazySieve runtime:       4.931611961917952
betterLazySieve runtime: 3.7906006319681183

而且与问题不同，我不只是想要 any/all 的 returned 值。

all() 中的 return 是不是太慢了，以至于如果覆盖它在所有但大多数情况下的使用？ for-else 是否比短路的 all() 更快？

你怎么看？

编辑： 添加到

建议的平方根循环终止检查中

更新： ShadowRanger 的是正确的。

改变后

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

我可能错了，但我认为每次它在生成器表达式中计算 test % p != 0 时，它都是在一个新的堆栈帧中这样做的，所以调用函数有类似的开销。您可以在回溯中看到堆栈帧的证据，例如：

>>> all(n/n for n in [0])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <genexpr>
ZeroDivisionError: integer division or modulo by zero

Answer 2

这是一个关于令人费解的结果的有趣问题，不幸的是我没有一个明确的答案......也许是因为样本量，或者这个计算的细节？但是和你一样，我觉得很惊讶。

但是，可以使 lazysieve 比 betterlazysieve 更快：

def lazySieve (num_primes):
    if num_primes == 0: 
        return []
    primes = [2]
    test = 3
    while len(primes) < num_primes:
        if all(test % p for p in primes[1:] if p <= sqr_test):
            primes.append(test)
        test += 2
        sqr_test = test ** 0.5
    return primes

它的运行时间大约是你的版本的 65%，比我系统上的 betterlazysieve 快大约 15%。

在 jupyter notebook w python 3.4.4 中使用 %%timit 在旧的 macbook air 上：

%%timeit 
lazySieve(10001)
# 1 loop, best of 3: 8.19 s per loop

%%timeit
betterLazySieve(10001)
# 1 loop, best of 3: 10.2 s per loop

Answer 3

这是几个问题的组合：

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

你可以做些什么来最小化或消除差异：

运行用于测试的较大迭代（以最小化设置成本的影响）
明确地将 test 拉入生成器的本地范围，例如作为一个愚蠢的 hack all(test % p != 0 for test in (test,) for p in primes[1:])
通过使用 map 和 C 内置函数从进程中删除所有字节码执行，例如all(map(test.__mod__, primes[1:]))（这也恰好实现了#2，通过预先查找 test.__mod__ 一次，而不是每个循环一次）

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

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

Why is all() slower than using for-else & break?

python

performance

primes