http://rubikitch.com/に移転しました このページをアンテナに追加 RSSフィード

2008-12-10

[]Array#permutationがなぜEnumeratorを返すのか・Rubyのメソッド呼び出しはコストがでかい

Send + More = Money - Ruby初心者prinyの学習帳 - Rubyist

もっと金くれや問題 - http://rubikitch.com/に移転しましたで俺と同じような解答があった。

Array#permutationはEnumeratorを返す。というのは、配列で返していたら、すべての順列をメモリ記憶しないといけないのでメモリコストがでかくなってしまうからだ。10P8(10個の数字を8つ選ぶ順列の個数)は1814400個とかなり多い。8要素の配列が1814400個もあるのだから。メモリ使用量はEnumeratorを使った場合は1.8MBに対して、to_aした場合は128MBにも到達する。領域確保だけでも無駄が出てしまう。

$ ruby -e 'p (0..9).to_a.permutation(8).count'
1814400
$ ruby -e '(0..9).to_a.permutation(8).count; system "ps axwu|grep #$$"'; 
1001      4338 78.0  0.0   3472  1760 pts/55   S+   06:44   0:01 ruby -e (0..9).to_a.permutation(8).count; system "ps axwu|grep #$$"
$ ruby -e '(0..9).to_a.permutation(8).to_a.length; system "ps axwu|grep #$$"'; 
1001      4343 64.0  6.1 129348 127608 pts/55  R+   06:44   0:02 ruby -e (0..9).to_a.permutation(8).to_a.length; system "ps axwu|gre

もひとつ。Rubyのメソッド呼び出しはコストがでかい。だから、1814400回も回るループでは極力メソッド呼び出しを減らすべきだ。checkメソッドをインライン化する。

  if send + more == money && s * m > 1
    return true
  else
    return false
  end

これも冗長。「send + more == money && s * m > 1」で十分。

ベンチマークをとってみる。send-more-money.rbは俺解答。send-more-money-to_a.rbは俺解答で(0..9).to_a.permutation(8).to_a.eachに置き換えたもの、send-more-money-priny.rbはg:rubyist:id:prinyさんのもの。

$ time ruby18 send-more-money.rb > /dev/null
ruby18 send-more-money.rb > /dev/null  11.42s user 0.02s system 96% cpu 11.863 total
$ time ruby18 send-more-money-to_a.rb > /dev/null
ruby18 send-more-money-to_a.rb > /dev/null  13.24s user 0.30s system 95% cpu 14.127 total
$ time ruby18 send-more-money-priny.rb > /dev/null
ruby18 send-more-money-priny.rb > /dev/null  17.80s user 0.37s system 96% cpu 18.798 total

ようは同じアルゴリズムであっても、書き方によってはこれだけの効率差が出るということ。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rubikitch/20081210/1228858392