python - フィボナッチ計算時間差

Question

フィボナッチシーケンスの要素を計算するために次の2つのコードを書いています。私はfibとfib2でシンプルなwhileループを使用しています

def fib(n): 
    zero, one = 0, 1 
    k = 1 
    while k < n: 
     zero, one = one, zero + one 
     k = k + 1 
    return one, ls 

def fib2(n, memo=None): 
    if memo is None: 
     memo = {} 
    if n == 1 or n == 2: 
     return 1 
    if n in memo: 
     return memo[n] 
    else: 
     memo[n-1] = fib2(n-1, memo) 
     memo[n-2] = fib2(n-2, memo) 
     return memo[n-1] + memo[n-2] 


##import timeit 
## 
##print('Fibonacci 1:', timeit.timeit('fib(10000)', '''def fib(n): 
## zero, one = 0, 1 
## k = 1 
## while k < n: 
##  zero, one = one, zero + one 
##  k = k + 1 
## return one''', number=100)) 
## 
##print('Fibonacci 2:', timeit.timeit('fib2(10000)', '''import sys; sys.setrecursionlimit(10001); 
##def fib2(n, memo=None): 
## if memo is None: 
##  memo = {} 
## if n == 0 or n == 1: 
##  return 1 
## if n in memo: 
##  return memo[n] 
## else: 
##  memo[n-1] = fib2(n-1, memo) 
##  memo[n-2] = fib2(n-2, memo) 
##  return memo[n-1] + memo[n-2]''', number=100)) 

は同じの再帰的な実装です。しかし、fib2が非常に遅いことが判明しました。私はそれがなぜであるか知りたい。それはfib2がたくさんのフレームを作成するためですか？ fib2を正しく実装しましたか？

ありがとうございました。

Answer 1

時間あなたのオリジナルの反復解法に対してこの合理化再帰バージョン - 最初の約1％の再帰の上限10％まで：私は私のように再帰に引数としてmemoを渡していないよ

def fib2(n, memo={0: None, 1: 1, 2: 1}): 
    if n in memo: 
     return memo[n] 

    previous = fib2(n - 1) # implicitly computes fib2(n - 2) 

    result = memo[n] = previous + memo[n - 2] 

    return result 

デフォルトの引数が変更可能な構造体に設定されているときに、 "問題"を利用しています。

上記の解決策は、最初の呼び出しで私のマシン上の元の反復のものより約4.5倍遅くなります。その後、メモ化が引き継ぎます。

def fib3(n, memo=[None, 1, 1]): 
    if n < len(memo): 
     return memo[n] 

    previous = fib3(n - 1) # implicitly computes fib3(n - 2) 

    result = previous + memo[-2] 

    memo.append(result) 

    return result 

この1回は外〜3倍で遅く：我々は、すべてのキーがシーケンシャル整数であるので、リストに辞書から私たちの「メモリ」を変更することで、両方の空間で、これに&時間を少し向上させることができます最初の呼び出しのために、私のマシン上で反復的な解決策よりも、しかし、私たちはより良いスピードワイズ使用して再帰を行うことができます。

def fib4(n, res=0, nxt=1): 
    if n == 0: 
     return res 
    return fib4(n - 1, nxt, res + nxt) 

これは、反復解法よりもほんの〜2倍遅く、/しかし、何のメモ化を持ちません。テールコール最適化（すなわち、Pythonではない）の言語では、これはおそらく/反復となります。