爲什麼尾遞歸優化比Python中的正常遞歸更快？

Question

雖然我明白尾遞歸優化是非Pythonic，但我想出了一個快速入侵的問題，在我準備發佈後立即刪除。

在1000堆棧限制下，深度遞歸算法在Python中不可用。但有時候，通過解決方案的初步想法是非常好的。由於函數是Python中的第一類，所以我使用返回一個有效的函數和下一個值來玩。然後在循環中調用該過程，直到完成單個調用。我相信這不是新的。

我發現有趣的是，我期望來回傳遞函數的額外開銷，使其比正常遞歸慢。在我的粗略測試中，我發現它需要30-50％的正常遞歸時間。 （隨着允許LONG遞歸額外的獎勵）

這裏是代碼我運行：

from contextlib import contextmanager 
import time 

# Timing code from StackOverflow most likely. 
@contextmanager 
def time_block(label): 
    start = time.clock() 
    try: 
     yield 
    finally: 
     end = time.clock() 
     print ('{} : {}'.format(label, end - start)) 


# Purely Recursive Function 
def find_zero(num): 
    if num == 0: 
     return num 
    return find_zero(num - 1) 


# Function that returns tuple of [method], [call value] 
def find_zero_tail(num): 
    if num == 0: 
     return None, num 
    return find_zero_tail, num - 1 


# Iterative recurser 
def tail_optimize(method, val): 
    while method: 
     method, val = method(val) 
    return val 


with time_block('Pure recursion: 998'): 
    find_zero(998) 

with time_block('Tail Optimize Hack: 998'): 
    tail_optimize(find_zero_tail, 998) 

with time_block('Tail Optimize Hack: 1000000'): 
    tail_optimize(find_zero_tail, 10000000) 

# One Run Result: 
# Pure recursion: 998 : 0.000372791020758 
# Tail Optimize Hack: 998 : 0.000163852100569 
# Tail Optimize Hack: 1000000 : 1.51006975627 

爲什麼是第二快的風格？

我的猜測是在棧上創建條目的開銷，但我不知道如何找出答案。

編輯：

與調用次數玩，我做了一個循環，在不同的NUM值都試一下。當我多次循環和調用時，遞歸更接近平價。

所以，我的時機，這是find_zero下一個新的名字前面加上這樣的：

def unrelated_recursion(num): 
    if num == 0: 
     return num 
    return unrelated_recursion(num - 1) 

unrelated_recursion(998) 

現在的尾部優化通話的完整遞歸的85％的時間。

所以我的理論是，15％的懲罰是大堆棧的開銷，而不是單堆棧。

之所以我看到如此巨大的執行時間差異，只運行一次就是堆棧內存和結構分配的代價。一旦分配，使用它們的成本就大大降低了。

因爲我的算法很簡單，內存結構分配是執行時間的很大一部分。

當我將堆棧啓動調用切換到unrelated_recursion(499)時，我在find_zero(998)執行時間之間獲得了完全啓動和未啓動的堆棧之間的大約一半。這與理論有關。

Answer 1

爲註釋希望remineded我，我是不是真的回答這個問題，所以這裏是我的感悟：

在您的優化，你分配，開箱和重新分配的元組，所以我想沒有他們：

# Function that returns tuple of [method], [call value] 
def find_zero_tail(num): 
    if num == 0: 
     return None 
    return num - 1 


# Iterative recurser 
def tail_optimize(method, val): 
    while val: 
     val = method(val) 
    return val 

1000次嘗試，每個開始值= 998：

• 這個版本採取0.16s
• 你的「優化」版本花了0.22s
• 「未優化」版本花了0。29S

（請注意，對於我來說，你的優化版本更快的未優化的一個...但我們不這樣做完全一樣的測試。）

但我不認爲這是有用的，以獲得這些統計數據：成本更多的是在Python方面（方法調用，元組分配，...），您的代碼在做真正的事情。在實際的應用程序中，您最終不會測量1000個元組的成本，而是實際實施的成本。

但是根本就沒有做到這一點：這只是難以閱讀的幾乎沒有，你寫的讀者，不是機器：

# Function that returns tuple of [method], [call value] 
def find_zero_tail(num): 
    if num == 0: 
     return None, num 
    return find_zero_tail, num - 1 


# Iterative recurser 
def tail_optimize(method, val): 
    while method: 
     method, val = method(val) 
    return val 

我不會嘗試實施它更可讀的版本，因爲我可能會結束：

def find_zero(val): 
    return 0 

但是我覺得在現實情況下，有一些不錯的方法來處理遞歸限制（包括內存大小或深度側）：

爲了幫助有關內存（不是深度），從functools的lru_cache一般可以有很大的幫助：

>>> from functools import lru_cache 
>>> @lru_cache() 
... def fib(x): 
...  return fib(x - 1) + fib(x - 2) if x > 2 else 1 
... 
>>> fib(100) 
354224848179261915075 

而對於堆棧大小，您可以使用list或deque，根據您的情況和使用情況，而不是使用語言堆棧。根據具體實施（當你實際上存儲在堆棧重新使用這些簡單的分計算），這就是所謂的dynamic programming：

>>> def fib(x): 
...  stack = [1, 1] 
...  while len(stack) < x: 
...   stack.append(stack[-1] + stack[-2]) 
...  return stack[-1] 
... 
>>> fib(100) 
354224848179261915075 

但是，這裏來使用自己的結構很好的一部分而不是調用堆棧，你並不總是需要保持整個堆疊繼續計算：

>>> def fib(x): 
...  stack = (1, 1) 
...  for _ in range(x - 2): 
...   stack = stack[1], stack[0] + stack[1] 
...  return stack[1] 
... 
>>> fib(100) 
354224848179261915075 

但隨着一個很好的接觸的「努力實現它之前知道的問題」（不可讀得出結論，硬調試，很難直觀地證明，這是錯誤的代碼，但它很有趣）：

>>> def fib(n): 
...  return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) 
... 
>>> 
>>> fib(99) 
354224848179261915075 

如果你問我，最好的實施是更具可讀性之一（斐波那契例如，可能是一個與LRU緩存，但通過改變... if ... else ...有一個更可讀的if語句，另一個例如deque可能更可讀，而對於其他例子，動態編程可能會更好......

「您正在爲人類閱讀代碼而不是爲機器寫信」。