フィボナッチコードからの再帰とキャッシングを理解できない

Question

私は再帰とキャッシングを理解しようとしていますが、まだまだ私は興味深い進歩を遂げています。私はこのコードを理解するのに少し問題があります：

# Fibonacci recursive with result storage 

class FibonacciStorage: 
    _storage = { 0:1, 1:1 } 
    @staticmethod 
    def _fib(number): 
     try: # is this already calculated 
      return FibonacciStorage._storage[number] #searches dict, and if value exists then return it 
     except KeyError: 
      result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) #this is the actual Fibonacci Formula 
      FibonacciStorage._storage[number] = result #adds result to dictionary 
      #print FibonacciStorage._storage #this shows the storage list growing with each iteration. 
      return result 
    @staticmethod 
    def fib(number): #first function, it has two asserts to basically make sure number is whole/positive and if its okay passes it to _fib(where the real work is done) 
     # only do the assert statements once 
     assert(isinstance(number,int)),"Needs a whole number" 
     assert(number>0),"Needs a positive whole number" 
     return FibonacciStorage._fib(number) 

# use a more readable name 
getFib = FibonacciStorage.fib 

print getFib(50) 

私はこのコードをネットで見つけて、実際に何をしているのかを理解するために各行にコメントしようとしました。私はこれがどのように再帰であるのか分かりませんが、正しい結果が得られるまでコードをループしますが、その呼び出し自体は見えません。

私はそれがこの行だと思っていましたが、私のprint FibonacciStorage._storage行はストレージキャッシュの成長と成長を示していますが、その下の行はリターン関数なので混乱します。 return resultがどういうふうに再帰を再び引き起こしているのか分かりません。

また、ストレージ辞書がこのプログラムを非常に速くしているかどうかもわかりません。ファイブシーケンスの単純な再帰は（データを保存しても）長い時間がかかりますが、この場合はprint getFib(200)の瞬間があります。キャッシングはどのように高速化していますか？

だからまとめるために、二つの質問は：

1）どのように再帰は実際にトリガされていますか？私のprintステートメントが各ループでアクセスされている場合？

2）キャッシングは他のフィブスシーケンスよりもどのように高速化されますか？クラス構造や@staticmethodが違いを生み出していますか？例えば、これは瞬間的で、http://en.literateprograms.org/Fibonacci_numbers_(Pythonのものは少し遅れているようです。

3）おそらくintrestから出て、ちょうどintrestから出ているfibnocciタイプのalgoスケール（分割して並行して実行できますか？

洞察力があれば助かります。

Answer 1

（1）再帰呼び出しは、この行にある：

result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) 
//     here^      and here^

そうだね、これは、定義によって、再帰的である「実際のフィボナッチ式」、です。

（2）キャッシングが高速化しています。違いを生むのは永続オブジェクト_storageです。これはの驚異の重複作業量を節約しています。考えてみましょう：

        fib(4) 
          /  \ 
          fib(3) +  fib(2) 
         / \  / \ 
        fib(2) + fib(1) fib(1) + fib(0) 
        / \ 
       fib(1) + fib(0) 

これは単なるfib(4)で、すでに冗長性を見ることができます。 fib(3)とfib(4)の整数値を単にキャッシュするだけで、fib(5)に必要な計算回数を7から1に減らすことができます。

Answer 2

フィボナッチの実装では、すでに計算された値を保存し、必要なときに効率的に検索するために、再計算する代わりにmemoizationという手法を使用します。値は一度だけ計算する必要があるため、パフォーマンスに大きなメリットがあります。再帰がこのラインでトリガされ

1. ：ご質問について

   あなたは_fib手順はキャッシュが大幅に計算速度を向上さ

2. 自身を呼び出している見ることができるよう、FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2)、これを参照してくださいexampleを参照してください。この場合、静的メソッドを使用することは特に有用ではなく、インプリメンテーションをより工夫します。
3. memonizedではない再帰的なバージョンは、並列アルゴリズムで分割され、fibonacciの呼び出しは別のスレッドで実行されます。しかし、オーバーヘッドはかなり大きく、アルゴリズムの複雑さはまったく改善されません。フィボナッチを計算するためのより速い方法については、メモしたバージョンに固執するか、read。

Answer 3

それはPythonのdictsが不足しているキーのために呼び出されます__missing__方法を持っていることを知って良いことだ：

class FibonacciStorage(dict): 
    def __missing__(self, n): 
     self[n] = self[n - 1] + self[n - 2] 
     return self[n] 

使用法：

fib = FibonacciStorage({0: 1, 1: 1}) 
print(fib[50]) #20365011074