为什么 max(iterable) 的执行速度比等效循环慢得多？

Question

我注意到一个小的重构对性能造成了奇怪的影响，该重构将循环替换为对递归函数内的内置 max 的调用。

这是我能制作的最简单的复制品：

import time

def f1(n):
    if n <= 1:
        return 1
    best = 0
    for k in (1, 2):
        current = f1(n-k)*n
        if current > best:
            best = current
    return best

def f2(n):
    if n <= 1:
        return 1
    return max(f2(n-k)*n for k in (1, 2))


t = time.perf_counter()
result1 = f1(30)
print('loop:', time.perf_counter() - t) # 0.45 sec

t = time.perf_counter()
result2 = f2(30)
print('max:', time.perf_counter() - t) # 1.02 sec

assert result1 == result2

f1 和 f2 都使用标准递归计算阶乘，但添加了不必要的最大化（这样我就可以在递归中使用 max，同时仍然保持递归简单）：

# pseudocode
factorial(0) = 1
factorial(1) = 1
factorial(n) = max(factorial(n-1)*n, factorial(n-2)*n)

它是在没有记忆的情况下实现的，因此调用次数呈指数级增长。

使用 max(iterable) 的实现比使用循环的实现慢两倍以上。

~~奇怪的是，max 与循环的直接比较并没有证明效果~~（编辑：没关系，请参阅@TimPeters 的回答）。另外，如果我使用 max(a, b) 而不是 max(iterable)，性能不匹配就会消失。

Answer 1

将此作为 "an answer" 发布，因为在评论中无法使用有用的格式：

$ python -m timeit "max(1, 2)"  # straight
10000000 loops, best of 3: 0.148 usec per loop

$ python -m timeit "max([i for i in (1, 2)])" # list comp
1000000 loops, best of 3: 0.328 usec per loop

$ python -m timeit "max(i for i in (1, 2))" # genexp
1000000 loops, best of 3: 0.402 usec per loop

这表明递归是一个转移注意力的问题。正如这些结果所示，一般来说，genexp 比 listcomp 慢，而 listcomp 又比两者都不用慢。由于您的代码所做的不仅仅是 just a max，因此时间差异并不那么极端 - 但由于它所做的 little 不仅仅是 max ，最大部分的速度仍然非常重要。

Answer 2

由于您为其提供的生成器表达式，这对 max 函数来说确实不公平。

对于 f2 的每次调用都需要为 n 创建一个新的闭包，需要创建一个新函数（这就是生成器表达式和列表表达式的方式，因为 Python 3 我相信，已实现；请参阅 'The Details' of PEP 289)，它包装了代表 gen-exp 的代码对象。然后这个迭代调用其他函数的函数再次被调用。

相关字节码的一小段：

14 LOAD_CLOSURE             0 (n)
16 BUILD_TUPLE              1
18 LOAD_CONST               2 (<code object <genexpr> at 0x7f1b667e1f60, file "", line 16>)
20 LOAD_CONST               3 ('f2.<locals>.<genexpr>')
22 MAKE_FUNCTION            8
24 LOAD_CONST               5 ((1, 2))
26 GET_ITER
28 CALL_FUNCTION            1

当然，您在 f1 的情况下看不到任何此类指令，因为它只是在调用。

当您随后调用 max 函数 f2 时，显着次，就像您在递归计算的阶乘时所做的那样30，开销就堆积。

功能事物的列表理解版本几乎存在同样的问题。它快一点，因为列表理解比生成器表达式快。

If I use max(a, b) instead of max(iterable) the performance mismatch disappears.

确切地说，在这种情况下，没有为每次调用创建函数，因此您不会看到开销堆积。您只是在此处提供参数。

为什么 max(iterable) 的执行速度比等效循环慢得多？

Why does max(iterable) perform much slower than an equivalent loop?

python

performance

python-3.x

python-internals