Lispはじめた。
Scala => Haskell => Lisp と逆行して勉強して行ってる感じ。
『はじめての人のためのLisp』を買ってきた。
対話形式の本で、ささっと文法を押さえるには不向きだが、読んでて面白い。
情報科学以外の広い知識が滲み出ている。
ファインマン物理を彷彿とさせる。
・・で、竹内函数が出てきたのでScalaで書いてみた。
def tak(x: Int, y: Int, z: Int): Int = {
if (x <= y)
y
else
tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
} 実行時間を計ってみる。↓こんなコードで。
new scala.testing.Benchmark {
def run() = tak(17, 9, 3)
}.runBenchmark(10)
結果は10回計測して3000, 3062, 3234, 3172, 3188, 3360, 3016, 3093, 3125, 3203（単位：ミリ秒）。
うーん、時間かかりますね。
・・遅延評価にすればいいじゃないか！ってことで、↓のコード
def tak(x: => Int, y: => Int, z: => Int): Int = {
if (x <= y)
y
else
tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
}うむ。これで計測すると10回とも0ミリ秒。遅延評価恐るべし。
速いけど0ミリ秒じゃあよくわからないよ・・
tak(500, 50, 5)でも遅延評価版だと400ミリ秒くらい。
