Python 3でfunctools.lru_cacheを使って簡単にメモ化再帰

python

このエントリーをはてなブックマークに追加

Google Code Jamの公式解説 Dashboard - Round 1B 2014 - Google Code Jamを読んでいて、Python 3には簡単にメモ化再帰する機能が標準ライブラリに含まれていることを知りました。以下、簡単な解説です。

フィボナッチ数を求める再帰関数

お題として、n番目のフィボナッチ数 - Wikipedia]を求める再帰関数を考えます。

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

これは引数nが大きくなると急激に遅くなります。例えばprint(fibo(35))の実行時間は、手元で以下のようになりました。

9227465
./fibonacci.py  7.61s user 0.06s system 99% cpu 7.698 total

メモ化再帰とは

ある引数に対する計算結果を保存しておき、後で同じ引数が与えられた時、計算結果を再利用するテクニックのことです。

デコレータlru_cacheによるメモ化再帰

Python 3の場合、標準ライブラリfuctoolsに含まれるデコレータ、lru_cacheを使うことで、自動的にメモ化再帰が実現できます！　

デコレータの使い方は以下です。

@functools.lru_cache(maxsize=None)
def fibo(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

maxsizeには、直近の何回分を記憶しておくかを指定します。Noneの場合は、制限なく記憶するようです。(10.2. functools — 高階関数と呼び出し可能オブジェクトの操作 — Python 3.4.2 ドキュメント)

print(fibo(35))の実行時間は、手元で以下のようになりました。劇的に早くなっていることがわかります。

9227465
./fibonacci.py  0.05s user 0.12s system 56% cpu 0.297 total

Python 2で使うには？

残念ながらこの機能はPython 2にはバックポートされていないようです。代替手段が memoization library for python 2.7 - Stack Overflow で紹介されています。