什麼原因導致這些方法調用的時間差異很大？

使用接受的答案（與文檔測試）從這裏Memoized裝飾：What can be done to speed up this memoization decorator?什麼原因導致這些方法調用的時間差異很大？

和下面的代碼（fib.py）：

class O(object): 

    def nfib(self,n): # non-memoized fib fn 

    if n in (0, 1): 
     return n 
    return self.nfib(n-1) + self.nfib(n-2) 

    @Memoized 
    def fib(self,n): # memoized fib fn 

    if n in (0, 1): 
     return n 
    return self.fib(n-1) + self.fib(n-2) 


if __name__ == '__main__': 
    import time 
    o = O() 

    stime = time.time() 
    print "starting non-memoized" 
    for i in range(10): 
    print o.nfib(32) 
    print "finished non-memoized - elapsed secs =", time.time() - stime 

    stime = time.time() 
    print "starting memoized" 
    for i in range(10): 
    print o.fib(32) 
    print "finished memoized - elapsed secs =", time.time() - stime 

    stime = time.time() 
    print "starting memoized with reset" 
    for i in range(10): 
    Memoized.reset() 
    print o.fib(32) 
    print "finished memoized with reset - elapsed secs =", time.time() - stime

我得到以下輸出：

C:\TEMP>python fib.py 
starting non-memoized 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
finished non-memoized - elapsed secs = 16.4189999104 
starting memoized 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
finished memoized - elapsed secs = 0.00100016593933 
starting memoized with reset 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
2178309 
finished memoized with reset - elapsed secs = 0.00299978256226 

C:\TEMP>

我希望第三個循環只要第一個循環，因爲它每次都通過循環重置它的緩存。將調試語句插入到fib方法中顯示它沒有被緩存，並且確實在第三個循環中計算結果，但它比第一個循環快得多。爲什麼？？？

我希望我忽略了一些令人尷尬明顯的事情，但是我的好奇心現在超過了我的自尊心。（b.t.w.我使用的是Windows 7專業版的64位Python 2.7，如果它很重要）

謝謝。

來源

2011-02-08 Gerrat

我在之前的評論中解釋過這一點：高速緩存產生O（n^2）函數O（n）。 – 2011-02-08 01:00:10

@Glenn：...是的，你做了（你不清楚）......我只是沒有「明白」。插入調試語句後，將每個（未記憶）的調用打印出來並以2 Gig文件結尾，並且每次看到所有的調用參數 - 我現在「明白了」！再次感謝裝飾者。 – Gerrat 2011-02-08 01:14:12

天真斐波那契函數的調用樹不是線性或三角形的，它是多維金字塔。通過記憶甚至一次，您修剪樹木的大量呼叫，將金字塔變成大多數線性結構。

來源

2011-02-08 00:58:39

第三個循環在計算每個最終結果後重置 - 但是，它仍然受益於遞歸調用的記憶。

來源

2011-02-08 00:58:04

time.time（）不應該用於時間碼，特別是在Windows上！使用timeit module。這是一箇舊的intoduction。一個大問題是電腦不斷地做數百件事情。如果在Outlook取電子郵件時某個部分碰巧運行，則Outlook在完成Outlook後可能會比其他功能稍長一些。重複這些任務，並採取最低限度往往會更好。這和其他許多事情都由timeit模塊自動處理。

關於窗口，這部分非常重要：

在Windows上，time.clock（）具有微秒粒度但了time.time（）的粒度的第二

1/60

來源

2011-02-08 00:58:21 chmullig

1/60秒的測試是非常準確的。 – Falmarri 2011-02-08 01:01:35

什麼原因導致這些方法調用的時間差異很大？

回答

相關問題