HaskellとF#の解読の練習とちょっとした疑問でRubyに移植してみた
Haskell vs F#
↑の記事とそのトラックバック先の記事では関数型言語が1秒未満の世界で競ってる。なんだか凄い。
でも、これ、そのままRubyで書き直すとどの位になるんだろう。せめてHaskellの3,4倍くらい遅い感じで動くと嬉しいな。勉強にもなるし♪と思って書き直して動かしてみたら桁が違ってあわわとなったメモ。甘ちゃんでごめんなさい。
追記など
他のRuby実装について追記しました。
Cにも移植してみました。
http://d.hatena.ne.jp/takeshinoda/20120208/1328697927
JavaScriptにも移植してみました。
http://d.hatena.ne.jp/takeshinoda/20120211/1328943818
下記にコード置いておきます。
https://gist.github.com/1768665
コードと実行結果
上記エントリのF#版が書き直しやすかったので、まずはそのまま書き直した↓。
改修前版
Node = Struct.new(:df, :branches) def B(int, double) [int, double] end def induceBackwardVerySlow(nodes, values) n = values.length / 2 nodes.map do |node| node.branches.map do |k, p| p * values[n + k] * node.df end.inject(&:+) end end ITERATION = 1000 def last_values(i) Array.new(201, i.to_f) end def test_tree (0..99).map do |i| (-i..i).map do |j| Node.new(1.0, [B(j - 1, 1.0 / 6.0), B(j, 2.0 / 3.0), B(j + 1, 1.0 / 6.0)]) end end end value = lambda do |i| test_tree. reverse. inject(last_values(i)) {|values, nodes| induceBackwardVerySlow(nodes, values) }. first end puts (1..ITERATION).map(&value).max
これの実行結果↓
$ ruby -v ruby 1.9.3p0 (2011-10-30 revision 33570) [x86_64-darwin11.2.0] $ time ruby hoge.rb 999.9999999999998 ruby hoge.rb 28.88s user 0.04s system 99% cpu 28.935 total
F#の実行環境は作るの面倒くさいので置いておいて、Haskellのコードを同じマシンで実行してみるとこんな感じ↓。
$ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.4.1 $ ghc -O2 hoge.hs [1 of 1] Compiling Main ( hoge.hs, hoge.o ) Linking hoge ... $ time ./hoge 999.9999999999998 ./hoge 0.53s user 0.00s system 99% cpu 0.534 total
54倍差…。
F#のをそのまま移植してるので、そもそも書き方が良くないってのもあると思って工夫してみたけど、ワタクシの才覚ではどうにも計算時間の桁が上がらず。induceBackwardVerySlow()内のinjectやめてそのまま合算したり、Nodeを配列に展開してみたりしたけど、差はたいして埋まらず。アルゴリズム維持したままで差を詰めるのは難しい…(アルゴリズムどう変えれば良いのか分からないけどねw)。
(言い訳がてらに、F#移植してるのになんでHaskellと競ってるねん的なところもありますが…)
そういうモンだと言われてしまうとそうなんだろうけど、こういう書き方良くないよ的なのがあれば教えて欲しいです。もっとオラにRuby力があれば…。
悪あがき↓。27倍差まで縮めた。けど、だいぶ見たくないコードになりました＞＜。
改修後版
def induceBackwardSlow(nodes, values) n = values.length / 2 nodes.map do |node| (node[2] * values[n + node[1]] + node[4] * values[n + node[3]] + node[6] * values[n + node[5]]) * node[0] end end ITERATION = 1000 def last_values(i) Array.new(201, i.to_f) end def test_tree 99.downto(0).map do |i| (-i..i).map do |j| [1.0, j - 1, 1.0 / 6.0, j, 2.0 / 3.0, j + 1, 1.0 / 6.0] end end end puts((1..ITERATION).map do |i| test_tree. inject(last_values(i)) {|values, nodes| induceBackwardSlow(nodes, values) }. first end.max)
実行結果↓。
$ time ruby hoge3.rb 999.9999999999998 ruby hoge3.rb 14.26s user 0.03s system 99% cpu 14.296 total
後者のコードの計算量を減らして(ITERATION=50)プロファイルにかけてみるとこんな感じでした。う〜ん。
$ ruby -r profile hoge3.rb 49.99999999999997 % cumulative self self total time seconds seconds calls ms/call ms/call name 53.83 91.49 91.49 5000 18.30 27.59 Array#map 14.35 115.88 24.39 5000000 0.00 0.00 Array#[] 12.82 137.67 21.79 5001 4.36 40.25 Range#each 5.70 147.35 9.68 2000000 0.00 0.00 Float#* 5.43 156.57 9.22 2000000 0.00 0.00 Fixnum#+ 3.30 162.17 5.60 1500000 0.00 0.00 Float#/ 3.03 167.32 5.15 1000000 0.01 0.01 Float#+ 1.15 169.28 1.96 500000 0.00 0.00 Fixnum#- 0.13 169.50 0.22 5000 0.04 27.65 Object#induceBackwardSlow 0.08 169.63 0.13 100 1.30 315.90 Integer#downto 0.08 169.76 0.13 51 2.55 2712.94 Array#each 0.05 169.84 0.08 5051 0.02 46.12 Enumerable.map 0.03 169.89 0.05 5000 0.01 0.01 Fixnum#-@ 0.02 169.93 0.04 5000 0.01 0.01 Fixnum#/ 0.01 169.95 0.02 5000 0.00 0.00 Array#length 0.00 169.95 0.00 2 0.00 0.00 IO#set_encoding 0.00 169.95 0.00 50 0.00 0.00 Object#last_values 0.00 169.95 0.00 50 0.00 0.00 Class#new 0.00 169.95 0.00 50 0.00 0.00 Array#initialize 0.00 169.95 0.00 50 0.00 0.00 Fixnum#to_f 0.00 169.95 0.00 50 0.00 631.80 Object#test_tree 0.00 169.95 0.00 50 0.00 631.80 Enumerator#each 0.00 169.95 0.00 3 0.00 0.00 Module#method_added 0.00 169.95 0.00 50 0.00 2767.20 Enumerable.inject 0.00 169.95 0.00 50 0.00 0.00 Array#first 0.00 169.95 0.00 49 0.00 0.00 Float#<=> 0.00 169.95 0.00 1 0.00 0.00 Enumerable.max 0.00 169.95 0.00 1 0.00 0.00 Float#to_s 0.00 169.95 0.00 2 0.00 0.00 IO#write 0.00 169.95 0.00 1 0.00 0.00 IO#puts 0.00 169.95 0.00 1 0.00 0.00 Kernel.puts 0.00 169.95 0.00 1 0.00 169950.00 #toplevel
改修前と後の差分
$ diff hoge.rb hoge3.rb 1d0 < Node = Struct.new(:df, :branches) 3,7c2 < def B(int, double) < [int, double] < end < < def induceBackwardVerySlow(nodes, values)
-
- -
-
- -
-
- -
-
- -
-
- -
【追記】他のRuby実装でやったらめっさ速かったり遅くなったりする
JRuby (改修後版で実行)
$ ruby -v jruby 1.6.5.1 (ruby-1.8.7-p330) (2011-12-27 1bf37c2) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_29) [darwin-x86_64-java] $ time ruby hoge3.rb 1000.0 ruby hoge3.rb 10.04s user 0.28s system 133% cpu 7.724 total
おおっ。14倍。浮動小数点の出力の仕様が少し違うらしく、丸まっている。
JRuby(改修前版で実行)
$ time ruby hoge.rb 1000.0 ruby hoge.rb 62.71s user 1.04s system 204% cpu 31.139 total
58倍。ありゃ。だいぶ遅い。
MacRuby(改修後版で実行)
$ ruby -v MacRuby 0.10 (ruby 1.9.2) [universal-darwin10.0, x86_64] $ time ruby hoge3.rb 999.99999999991 ruby hoge3.rb 15.73s user 0.45s system 125% cpu 12.855 total
おお、24倍。
