爲什麼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) 

它沒有memoization實現，所以有一個指數數量的調用。

使用max(iterable)的實現比具有循環的實現慢兩倍以上。

奇怪的是， max vs loop的直接比較沒有證明效果 （編輯：沒關係，請參閱@TimPeters答案）。另外，如果我使用max(a, b)而不是max(iterable)，則性能不匹配會消失。

Answer 1

這對於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，開銷只是堆積階乘做。

函數事件的列表理解版本幾乎遭受同樣的問題。它要快一點，因爲列表解析比生成器表達式更快。

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

確切地說，在這種情況下，沒有爲每個呼叫創建功能，所以您沒有看到堆積如山。你只是在這裏提供參數。

Answer 2

發佈此爲「答案」，因爲有用的格式是不可能的評論：

$ 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慢，而後者反過來比使用慢。由於你的代碼比只有最大，所以時序差異並不是極端 - 但由於它的作用不僅僅是最大值，而且最大值的速度仍然非常重要。