たらい回し関数

小飼弾さんのブログの過去記事（参照）を読んでいて、「たらい回し」関数ってのの存在を知りました。コードを読んでいて何の意味があるのだろうと思っていたら、関数呼び出しのベンチマークに使う有名な関数なのですね。Wikipedia に書いてありました。
竹内関数 - Wikipedia
発明したのは日本人だそうです。

で、結果を見てみたら、Ruby は惨憺たる結果ですな。でも、おもしろそうなので自分でもやってみました。コードと数値は弾さんのままで、Linux Mint 17.2 で実行しました。Ruby 2.2.3 です。結果は

tak(12, 6, 0) = 12

real	0m0.741s
user	0m0.712s
sys	0m0.024s

です。比べ物にならないくらい高速化されていますね。まあ、最近の PC が速いのかも知れないが、僕のノートパソコンはふつうの VAIO です。

ついでに Python 2.7 でもやってみました。これも弾さんのままです。

tak(12, 6, 0) = 12

real	0m1.336s
user	0m1.328s
sys	0m0.008s 

へえ、Ruby の方が速いですね。Ruby 頑張りました。弾さんの結果だと Python の圧勝ですが。

弾さんの Ruby コードを載せておきますね。こんな風に書くんだ。

def tak(x, y, z)
  if x <= y
  then y
  else tak(tak(x-1, y, z),
           tak(y-1, z, x),
           tak(z-1, x, y))
  end
end

x, y, z = ARGV.size == 3 ? ARGV.map{|s| s.to_i } : [10, 5, 0]
puts "tak(#{x}, #{y}, #{z}) = #{ tak(x, y, z) }";

僕ならメソッドの部分は

def tak(x, y, z)
  (x <= y) ? y : tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
end

などと書いてしまうでしょうな。

Ruby でも弾さんの C 並の結果が出ているので、これはやはりハードウェアの10年間の進歩が大きいのでしょうね。

ついでだ、C でもやっておこう。

tak(12, 6, 0) = 12

real	0m0.077s
user	0m0.076s
sys	0m0.000s

さすがに C だ。弾さんの結果と比較すると、C で6.8倍、Python で8.0倍、Ruby で37.9倍になっている（user で比較）ので、Ruby が頑張って高速化したのがわかります。まあ、以前は遅すぎたのだな。