前回『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
遅延評価の方が高速なようだ。