Pythonで遅延評価

前回 、『ラムダ式で再帰関数を書く - 超ウィザード級ハッカーのたのしみ 』でラムダ式について、学んでいたら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