メモ化とline_profilerによる計測

アルゴリズムの勉強などをあまりしていなかったので，メモ化という言葉は就活なんかでの技術試験で知るのが初めてだった．
メモ化自体はそこまで難しいことではなく，何度も同じ計算をしないで，一度計算したものをうまく保存することで計算結果を再利用するというものである．

例として，フィボナッチ数列がよく使われる．
フィボナッチ数列は，fib(n) = fib(n-1) + fib(n-2)で定義されるため，fib(k)が何度も呼び出されることになる．
ここで，メモ化を用いることで，一度計算したfib(k)を保存し，再利用する．

これを，時間計測ツールであるline_profilerを用いて，計測した．

# 通常のフィボナッチ数列
def normal_fib(n):
    if n == 0 or n == 1 :
        return n
    else:
        return normal_fib(n-1) + normal_fib(n-2)

# メモするフィボナッチ数列
memo = [0 for x in range(100)]
def memo_fib(n):
    if n < 2 :
        return n
    elif memo[n] != 0:
        return memo[n]
    else:
        memo[n] = memo_fib(n-1) + memo_fib(n-2)
        return memo[n]

@profile
def main():
    print(memo_fib(20))
    print(normal_fib(20))

if __name__ == '__main__':
    print("Memoization!!!")
    main()
    print(memo)

fib(20)で比較した出力結果は以下のよう．

Memoization!!!
6765
6765
[0, 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Wrote profile results to memo.py.lprof
Timer unit: 1e-06 s

Total time: 0.015669 s
File: memo.py
Function: main at line 19

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    19                                           @profile
    20                                           def main():
    21         1         51.0     51.0      0.3      print(memo_fib(20))
    22         1      15618.0  15618.0     99.7      print(normal_fib(20))