これらのメソッドコールのタイミングに大きな違いが生じる原因は何ですか？

Question

ここからメモ化デコレータのために（doctestを持つ）受け入れ答えを使用する：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> 

私は3番目のループが最初のループの長さになると予想していました。なぜなら、ループを通過するたびにキャッシュがリセットされるからです。 fibメソッドにデバッグステートメントを挿入すると、キャッシュされていないことが示され、実際には3番目のループで結果が計算されますが、最初のループよりもはるかに高速です。なぜ？？？

私は恥ずかしがっていることを見落としてしまったと思っていますが、私の好奇心は現在私の誇りを上回っています。 （私は、Windows 7のプロマシンで64ビットのPython 2.7を使用しています）。

ありがとう。

Answer 1

素朴なフィボナッチ関数の呼び出しツリーは線形または三角形ではなく、多次元ピラミッドです。あなたが一度でもメモを書くことによって、の広大なの量の呼び出しをツリーから取り除き、ピラミッドをほぼ線形の構造に変えます。

Answer 2

最後の各結果を計算した後で3番目のループがリセットされますが、再帰呼び出しのメモ処理には依然としてメリットがあります。

Answer 3

time.time（）はタイムコード、特にウィンドウに使用しないでください！ timeit moduleを使用してください。ここに古いintoductionがあります。 1つの大きな問題は、コンピュータが常に何百ものことをしていることです。 Outlookが電子メールをフェッチしている間に1つの部分が実行されると、Outlookが終了した後に他の機能よりもわずかに時間がかかることがあります。タスクを繰り返し、最小限に抑える方が良い傾向があります。これと他の多くのものは、timeitモジュールによって自動的に処理されます。窓について

が、この部分はかなり関連している：Windowsでは

場合、time.clock（）はマイクロ秒の精度を持っていますが、 time.time（）の粒度は、第二

の1 /第60回です