pythonの関数をメモ化する

プログラムを書いていると再帰呼び出しする関数や整数値を引数にとる関数など、同じ値を渡して何度も実行される関数があります。
そのような場合、メモリーが十分あるのであれば毎回毎回処理を実行するより結果を保存しておく方が効率的です。

それを、メモ化(Memoization)と言うそうです。
メモ化 – Wikipedia

自分で実装するのも難しくないですが、pythonでメモ化を行うには、
@functools.lru_cache
と言う便利なデコレーターが用意されています。

ちなみに、lruは、Least Recently Usedの略です。
キャッシュアルゴリズム – Wikipedia

フィボナッチ数列で実際に使ってみましょう。
また、実際に効率化できている(関数中の処理の実行回数が減っている)ことを確認するために、
その関数が何回呼び出されたのかを記録し、表示します。
また、実行時間も測りましょう。

まず、メモ化をしない例。(jupyter notebookで動作させることを前提としたコードです。)

%%time
fib_count = 0  # 関数が呼び出された回数記録用


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


print("F(100)=", fib(30))
print("実行回数:", fib_count)

# 以下出力
F(100)= 832040
実行回数: 2692537
CPU times: user 449 ms, sys: 3.35 ms, total: 453 ms
Wall time: 456 ms

fibが何度も繰り返し実行され、非常に無駄の多い実装になっていることがわかります。

続いて、lru_cacheでメモ化した例です。

%%time
from functools import lru_cache
fib_memo_count = 0  # 関数が呼び出された回数記録用


@lru_cache(maxsize=None)
def fib_memo(n):
    global fib_memo_count
    fib_memo_count = fib_memo_count + 1
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_memo(n-1) + fib_memo(n-2)


print("F(100)=", fib_memo(30))
print("実行回数:", fib_memo_count)

# 以下出力
F(100)= 832040
実行回数: 31
CPU times: user 229 µs, sys: 120 µs, total: 349 µs
Wall time: 311 µs

こんどのfib_memoは31回しか実行されませんでした。
n=0,...,30 でそれぞれ1回ずつですね。
処理時間も桁違いに早くなっています。