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