前回 、『ラムダ式で再帰関数を書く - 超ウィザード級ハッカーのたのしみ 』でラムダ式について、学んでいたらPythonで遅延評価をする方法が理解できた。
実験に使うのは、たらい回し関数だ。
普通のたらい回し関数は以下の通り。
def tarai(x, y, z): return tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)) if x > y else y
遅延評価版は以下のようになる。
def lazy_tarai(x, y, z): def ltarai(fx, fy, fz): x = fx() y = fy() if x > y: return ltarai(lambda: ltarai(lambda: x-1, fy, fz), lambda: ltarai(lambda: y-1, fz, fx), lambda: ltarai(lambda: fz()-1, fx, fy)) else: return y return ltarai(lambda: x, lambda: y, lambda: z)
lambda: xという操作で、xを返す引数のない関数を作っている。これを評価するとxが返る。
>>> x = 10 >>> (lambda: x)() 10
この関数を評価するまではxは計算しなくてよくなる。つまり、遅延評価となる。
ちなみに、参考のページではxとyを複数回評価していたので、一回で済むようにした。
計算時間は以下の通りで、遅延評価にすると爆速になる。
$ python -m timeit -s 'import tarai' 'tarai.tarai(12, 6, 0)' 10 loops, best of 3: 18.6 sec per loop $ python -m timeit -s 'import tarai' 'tarai.lazy_tarai(12, 6, 0)' 10000 loops, best of 3: 140 usec per loop
ラムダ式にはこういう使い方もあるのか!!関数に名前をいちいち付けなくてよいだけのものではなかった。
参考
404 Blog Not Found:λ萌え - たらいを後回し
追記
def lazy_tarai2(x, y, z): def ltarai(fx, fy, fz): x = fx() y = fy() if x > y: return ltarai(lambda: ltarai(lambda: x-1, lambda: y, fz), lambda: ltarai(lambda: y-1, fz, lambda: x), lambda: ltarai(lambda: fz()-1, lambda: x, lambda: y)) else: return y return ltarai(lambda: x, lambda: y, lambda: z)
とすると少し早くなりました。
$ python -m timeit -s 'import tarai' 'tarai.lazy_tarai(100, 50, 0)' 100 loops, best of 3: 10 msec per loop $ python -m timeit -s 'import tarai' 'tarai.lazy_tarai2(100, 50, 0)' 100 loops, best of 3: 9.8 msec per loop