たらい回し関数をメモ化で高速化

前回『Pythonで遅延評価 - 超ウィザード級ハッカーのたのしみ』に引き続きたらい回し関数で遊んでみる。

今回は、メモ化(memoization)で高速化を試みる。

メモ化で高速化したたらい回し関数は以下のとおり。

memo = {}
def memo_tarai(x, y, z):
    global memo
    try:
        return memo[(x, y, z)]
    except KeyError:
        if x > y:
            ret = memo_tarai(memo_tarai(x-1, y, z), memo_tarai(y-1, z, x), memo_tarai(z-1, x, y))
        else:
            ret = y
        memo[(x, y, z)] = ret
        return ret

Pythonには辞書機能があるのでメモ化は簡単ですね。

実行時間は以下のとおりで、メモ化をすると遅延評価と比較してもさらに爆速になりました。

$ python -m timeit 'import tarai; tarai.l
azy_tarai(100, 50, 0)'
100 loops, best of 3: 10 msec per loop
$ python -m timeit 'import tarai; tarai.m
emo_tarai(100, 50, 0)'
1000000 loops, best of 3: 1.11 usec per loop

メモ化の威力おそるべし。

追記

メモ化の実行時間はメモされた値を直に返す時間になっているかも。

$ time python -c 'import tarai;tarai.memo_tarai(100, 50, 0)'

real    0m0.093s
user    0m0.076s
sys     0m0.016s
$ time python -c 'import tarai;tarai.lazy_tar
ai(100, 50, 0)'

real    0m0.050s
user    0m0.032s
sys     0m0.016s

遅延評価の方が高速なようだ。