解釋這個高階函數行爲

有人可以解釋爲什麼版本1和2以相同的速度執行嗎？我預計版本2,3和4需要大約相同的時間。解釋這個高階函數行爲

def fib(n): 
    return n if n in [0, 1] else fib(n-2)+fib(n-1) 

def memoize(fn): 
    stored_results = {} 

    def memoized(*args): 
     try: 
      return stored_results[args] 
     except KeyError: 
      #nothing cached 
      result = stored_results[args] = fn(*args) 
      return result 

    return memoized 

#version 1 (unmemoized) 
print timeit.timeit('fib(35)', 'from __main__ import fib', number=1) 
print fib, '\n' 

#version 2 
memo_fib = memoize(fib) 
print timeit.timeit('memo_fib(35)', 'from __main__ import memo_fib', number=1) 
print memo_fib, '\n' 

#version 3 (wrapped) 
fib = memoize(fib) 
print timeit.timeit('fib(35)', 'from __main__ import fib', number=1) 
print fib, '\n' 

#version 4 (w/ decoration line) 
@memoize 
def fib(n): 
    return n if n in [0, 1] else fib(n-2)+fib(n-1) 

print timeit.timeit('fib(35)', 'from __main__ import fib', number=1)

結果：

version 1: 4.95815300941 
<function fib at 0x102c2b320> 

version 2: 4.94982290268 
<function memoized at 0x102c2b410> 

version 3: 0.000107049942017 
<function memoized at 0x102c2b488> 

version 4: 0.000118970870972

來源

2013-04-30 alexhb

使用'timeit'模塊爲您的代碼計時。 – 2013-04-30 23:50:36

你memoize功能實際上並沒有取代fib與memo_fib，它只是返回一個新功能。

該新功能仍遞歸調用原始未記憶的fib。

所以，基本上，你只是記憶的最高水平。

在fib，以fib遞歸調用時只使用模塊的全局名稱。（函數與其他任何類型的值基本沒有區別，函數名稱與其他類型的名稱沒有區別，所以如果您在模塊全局級別定義函數，那就是它的作用，例如，如果您反編譯字節碼與dis.dis(fib)，你會看到名字fib一個LOAD_GLOBAL）

所以，簡單的解決辦法是：

fib = memoize(fib)

或者只是使用memoize作爲裝飾，使這個更難得到錯誤的。

換句話說，你的例子3和4

或者，甚至更簡單，使用內置lru_cache裝飾。一個函數體內定義fib：如果你想成爲真正偷偷摸摸（注意它的文檔中的第二個例子。）

。它將最終引用fib作爲定義範圍內的封閉單元，而不是全局（LOAD_DEREF而不是LOAD_GLOBAL在反彙編中）。然後，您可以進入該範圍並替換其其fib，這意味着您的遞歸函數現在被「祕密地」記憶（實際的全局fib未被記憶，但遞歸調用的函數是）和「安全」（沒有人除了通過fib本身以外，其他人對閉合單元有參考）。

來源

2013-04-30 23:54:24 abarnert

在版本2中，您使用不同的名稱存儲了memoized版本，因此您可以調用fib的次數與第一次版本中的次數相同。您的調用堆棧看起來是這樣的：

memo_fib(35) 
    fib(35) 
     fib(34) 
      fib(33) 
     fib(33)

等

所以你實際上並沒有收到在此情況下，記憶化任何好處。

來源

2013-04-30 23:56:23

解釋這個高階函數行爲

回答

相關問題