PythonでやるTAK関数の高速化
ほげ!John(())です。
Lispの怖い人、@fu7mu4さんからご飯を頂いたのでその消化を行っていきたいと思います。(めっちゃほったらかしてた)
ご飯内容
そういうことです。ありがてぇ。。
とりあえずPythonで実装してみた
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))
そのままですが。
そして最後に
print(tak(12, 6, 0))
を付け加えたこのプログラムの実行時間。
$ time python3 tak.py
12real 0m4.960s
user 0m4.776s
sys 0m0.032s
となりました。
高速化
$ time python3 fast_tak.py
fast_tak.py:5: SyntaxWarning: name 'tak_dict' is used prior to global declaration
global tak_dict
12real 0m0.499s
user 0m0.112s
sys 0m0.028s
怒られてるけど、解決策わかんないです。
コードはこんな感じ。
def tak(x, y, z):
try:
tak_dict
except NameError:
global tak_dict
tak_dict = {}if str(x) + "," + str(y) + "," + str(z) in tak_dict:
return tak_dict[str(x) + "," + str(y) + "," + str(z)]
elif x <= y:
return y
else:
first = tak(x - 1, y, z)
tak_dict[str(x - 1) + "," + str(y) + "," + str(z)] = first
second = tak(y - 1, z, x)
tak_dict[str(y - 1) + "," + str(z) + "," + str(x)] = second
third= tak(z - 1, x, y)
tak_dict[str(z - 1) + "," + str(x) + "," + str(y)] =third
tak_dict[str(first) + "," + str(second) + "," + str(third)] = tak(first, second, third)
return tak_dict[str(first) + "," + str(second) + "," + str(third)]print(tak(12, 6, 0))
辞書使ってすでに計算してるのを省略した。
汚いのは知ってるけど、Pythonわかんない僕にはこれしか思いつかなかったんだ。。
でもこれで4.5秒位早くなった!わっしょい!
最後に
かまってくれる方、ありがとうございます。
ゆっくりながらも頑張っていくので構い続けて下さいな!