Pythonでもわりとたらい回せそう？

さて、PythonのMemoize*1版は誰かよろしこ、ということですのでためしに書いてみました。まずMemoizeしない版を、以下のようにいじっときます。

#!/usr/bin/python
import sys

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

x, y, z = 10, 5, 0
if len(sys.argv) == 4:
    x, y, z = map(int, sys.argv[1:])
print ('tak(%d, %d, %d) = %d' % (x, y, z, tak(x, y, z)))

で、本命であるこれのMemoize版が次のコードです。

#!/usr/bin/python
import sys

taks = {}

def tak (x, y, z):
    global taks
    if x <= y:
        return y
    else:
        if not taks.has_key((x,y,z)):
            taks[(x,y,z)] = tak(tak(x - 1, y, z),
                                tak(y - 1, z, x),
                                tak(z - 1, x, y))
        return taks[(x,y,z)]

x, y, z = 10, 5, 0
if len(sys.argv) == 4:
    x, y, z = map(int, sys.argv[1:])
print ('tak(%d, %d, %d) = %d' % (x, y, z, tak(x, y, z)))

で、この二つのベンチをとってみました。PowerBook G4 (867 MHz, 640 MB RAM)の環境でOS標準のPython使ってます。

tak.py
tak(12, 6, 0) = 12
       21.95 real        19.22 user         0.31 sys

tak_memoize.py
tak(12, 6, 0) = 12
        0.18 real         0.05 user         0.08 sys

なんか相当はやくなったー！さすがにHaskellにはおよばなさそう。しかし、Memoize版Pythonもかなりがんばってます。比較のために、うちの環境でほかの言語のたらい回しをベンチしてみました。PerlとRubyのコードは、たらいを回すならHaskellからお借りしました。

tak_memoize.pl
tak(100, 50, 0) = 100
        0.54 real         0.44 user         0.04 sys

tak_memoize.rb
tak(100, 50, 0) = 100
        0.91 real         0.79 user         0.04 sys

tak_memoize.py
tak(100, 50, 0) = 100
        0.39 real         0.27 user         0.08 sys

なかなかやるぜ、Python。

あと、これの元ネタである、C言語による最新アルゴリズム事典が手元にあったのでp185を参照してみたんですが、