メモ化再帰とデコレータ

何故か知らないが土曜の夜に妙なキーワードがトレンド入りしていた。

　

　

プログラミングコンペが行われていた時間らしく同スキルを求めるような出題であったようである。詳しくは知らない。

　

せっかくの機会なので簡単に復習しておく。

Pythonには鉄板のメモ化ライブラリが存在する。

functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.12.2 ドキュメント

　

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

for i in range(40):
    print(fib(i))

　

キャッシュサイズに制限を加えたければlru_cacheを使うと良い。

上記は簡単なプログラムであるが@cacheのデコレータの部分をコメントアウトするとどういう挙動になるかどうか試して頂きたい。

　

フィボナッチ数列は再帰呼び出しで典型的な課題であるが，数学的な定義でプログラミングすると上記のようになる。メモ化されていないとそれ以前の数列の値を再帰的に計算しなおすことになるがこれが不変であることからキャッシュに保存しておくことで劇的に速くなる。

　

メモ化情報を揮発性のRAMで残すのが上記の手法であるが，不揮発性のストレージなどに残す場合もあり，こういった場合はメモ化の永続化と言われる。一般的にはKVSのデータベースが使われることが多い。

ゲームAI界隈だと同じ局面が何度も見られた場合に以前の計算結果を流用するという意味で，定跡データベースというものがこれに当たるが，こちらは対戦前に計算しておいて溜めておくという計算リソースの前借という表現が適当であろう。

　

キャッシュが何をしているかと言えば，（ほぼ）同等コードが下記のようになる。

　

def cache2(f):
    table = {}
    def f2(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return f2

@cache2
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

for i in range(40):
    print(fib(i))

　

ついでにデコレータも復習しておこう。

デコレータも上記のように自分で作ることが出来るが意味は下記のようになる。見通しが悪くならず後置してよければデコレータを使わずに同じ意味だ。

def cache2(f):
    table = {}
    def f2(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return f2

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

fib = cache2(fib)

for i in range(40):
    print(fib(i))

　

どちらかと言うとBlogにコードを貼る復習になった感じである。