为什么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)比使用循环的实现慢两倍多.

奇怪的是,maxvs循环的直接比较没有证明效果(编辑:没关系,请参阅@TimPeters答案).另外,如果我使用max(a, b)而不是max(iterable)性能不匹配消失.

Answer 1

将此作为"答案"发布,因为评论中无法使用有用的格式:

$ 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慢,后者反过来比使用两者都慢.由于您的代码所做的不仅仅是最大值,因此时序差异并不是那么极端 - 但由于它只是做了一点上限,因此最大部分的速度非常重要.

Answer 2

max由于您输入的生成器表达式，这对于该函数来说确实不公平。

f2对于需要为 创建新闭包的每次调用n，都需要创建一个新函数（我相信这就是生成器表达式和自 Python 3 以来的列表表达式的实现方式；请参阅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时，正如您在递归计算 的阶乘时所做的那样，开销就会不断增加。f230

函数的列表理解版本几乎也遇到同样的问题。它更快一点，因为列表推导式比生成器表达式更快。

如果我使用max(a, b)而不是max(iterable)性能不匹配就会消失。

确切地说，在这种情况下，不会为每个调用创建任何函数，因此您不会看到开销堆积起来。您只是在这里提供论据。