John(筋肉)の備忘録的な何か

備忘録的な何かであり、進捗そのものでもあるよ!!怖い人は見ないで!

PythonでやるTAK関数の高速化

ほげ!John(())です。

Lispの怖い人、@fu7mu4さんからご飯を頂いたのでその消化を行っていきたいと思います。(めっちゃほったらかしてた)

 

ご飯内容

gist.github.com

 

そういうことです。ありがてぇ。。

 

とりあえず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
12

real 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
12

real 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秒位早くなった!わっしょい!

 

最後に

かまってくれる方、ありがとうございます。

ゆっくりながらも頑張っていくので構い続けて下さいな!