メモ化について

#この記事を書く動機
フィボナッチ数列の高速化で何がありますかと言われて答えられなかったから
調べたものを共有してほしいと思い書きました。

#メモ化とは

メモ化（英: Memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。(Wikipedia)

###フィボナッチ数列の原文

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

nが大きくなるほど再起関数呼び出しが深くなり計算時間増加
でもよく考えると

f(4)=f(3)+f(2)
f(3)=f(2)+f(1)
f(2)=f(1)+f(0)

何回___f(2)___計算するん。。。

キャッシュしちゃおう！！

一回計算して出た結果は配列に保存しておいて、関数から値を計算するのではなく配列から呼び出そう！！！

すると以下のコード

例えばN=50

N=50

memo=[-1 for i in range(N+1)]

def fib(n,memo):

    if n==0:
        memo[n]=0
        return memo[n]
    elif n==1:
        memo[n]=1
        return memo[n]
    else:
        if memo[n]!=-1:
            return memo[n]
        else:
            memo[n]=fib(n-1,memo)+fib(n-2,memo)
            return memo[n]

配列memo[n]は再起関数を呼ぶごとにインデックスが変わっていくためnに応じて値がキャッシュされる

#計算速度比較
###N=40の場合
メモ化無し
t=37.91sec

メモ化有り
一瞬

###N=400の場合
メモ化無し
オーバーフロー

メモ化有り
t=0.001sec

#結論
アルゴリズムおそるべし