Pythonのfunctools.lru_cache

竹内関数のメモ化が驚くほど簡単

竹内関数は、かの有名なLisper竹内郁雄さんが考案した関数で、与える数によって関数の再帰呼び出しの回数が増え、計算量が大きくなる関数で、よくベンチマーク測定などに使われます。
たらい回し関数と竹内関数の違いは、返す値が違い、それによって計算量に大きな違いがあることだそうです。それは、かのジョン・マッカーシーさんが、竹内関数では本来yを返すところを記憶違いでzにしてしまったということでそうなってしまったようです。
それはさておき、Pythonで普通に書くと以下のようになります。

def tarai(x, y, z):
    if x <= y:
        return y
    else:
        return tarai(tarai(x - 1, y, z),
                     tarai(y - 1, z, x),
                     tarai(z - 1, x, y))

たらい回し関数の場合は、

    if x <= y:
        return z

となります。
これを測定してみると以下のような結果になりました。

$ time python tarai.py
python tarai.py 1.28s user 0.00s system 99% cpu 1.285 total

しかし、Pythonのfunctools.lru_cacheを使うと以下のような結果になります。

$ time python tarai.py
python tarai.py 0.05s user 0.00s system 98% cpu 0.053 total

コードは以下のようになります。

from functools import lru_cache

@lru_cache(maxsize=128)
def tarai(x, y, z):
    if x <= y:
        return y
    else:
        return tarai(tarai(x - 1, y, z),
                     tarai(y - 1, z, x),
                     tarai(z - 1, x, y))

@lru_cache(maxsize=128)とデコレータをつけるだけです。
このデコレータは最近の呼び出し最大maxsize回まで保存するというもので、最新の呼び出しが次も呼び出される可能性が高い場合に最も効率がよくなるらしい。そしてLRUキャッシュは前回計算した値を再利用したい場合にのみに使うべき、と公式ドキュメントには書かれているので、今回はまさに持ってこいの機能であるように思います。
今回偶然見つけたのでラッキーでしたが、いろいろよく読んで、なんとなくでも頭の片隅に覚えておきたいものであります。私の頭の引き出しが、まさにその時開くか否かはまた別の話として……