Ruby でたらいまわし関数を遅延評価する
Haskell が遅延評価で「たらいまわし関数」を高速に実行できるなら、Ruby でも Proc で遅延評価できるので、Ruby でも「たらいまわし関数」を高速化できるのではないかと思った。でぐぐってみたら、そのものズバリの記事を発見。
おお、きちんとまとまったわかりやすい記事である。このリンクだけで充分なのだが、やはり自分でやってみないとということでやってみました。基本的に上記事のコードと同じ内容です(多少好みに書き換えました)。
tarai_lazy.rb
class Proc def -(lmd) ->{self.call - lmd.call} end end def tak_lazy(x, y, z) ->{ xval = x.call yval = y.call if xval <= yval yval else tak_lazy(tak_lazy(x - ->{1}, y, z), tak_lazy(y - ->{1}, z, x), tak_lazy(z - ->{1}, x, y)).call end } end x, y, z = 12, 6, 0 tak = tak_lazy(->{x}, ->{y}, ->{z}).call puts "tak(#{x}, #{y}, #{z}) = #{tak}"
数値まで lambda で包んでしまう。実行結果。
$ time ruby tarai_lazy.rb tak(12, 6, 0) = 12 real 0m0.096s user 0m0.036s sys 0m0.020s
おお、圧倒的に速い!(Linux Mint 18.2 @ Core i5 4210U 1.70GHz; Ruby 2.3.3)
なんと、過去記事での C言語より速いではないか! 遅延評価を使わない Ruby 版と比べると、約20倍の高速化になっている(以上 user で比較)。なるほど、「たらいまわし関数」は遅延評価と相性がいいのだなと納得。まあ、Haskell 版にはさすがに敵いませんが。