shonen.hateblo.jp

やったこと,しらべたことを書く.

配列とEnumerable,どちらが高速?

問題

いくつかのrubyコードに対して実行時間を計測する.

require 'benchmark'

# p `ruby -v`

foo = (1..5050505)
[
    'foo.reduce(:+)',
    'foo.to_a.reduce(:+)',
    'foo.to_a.reverse.reduce(:+)',
    'foo.each.reduce(:+)',
    'foo.each.to_a.reduce(:+)',
    'foo.reverse_each.reduce(:+)',
    'foo.reverse_each.to_a.reduce(:+)'
].each do |e|
    puts e
    p Benchmark.realtime { eval(e) }
end

どのコードが高速で,どのコードが低速だろうか?

予想

  • foo.to_a.reduce(:+) は低速だろう.Range (1..3030303) を 一度配列化するため,3030303*8byteのメモリを確保する手間が掛かるから.
  • foo.to_a.reverse.reduce(:+) はさらに低速だろう.配列化した上に,reverse操作をしているから.
  • foo.reduce(:+)foo.each.reduce(:+) は変わらないのでは.
  • reverse_each を使ったほうが良いのか reverse 使ったほうが良いのか知りたくて実験した

実際には

環境によって結果がころころ変わる.

wandbox

ruby 2.0.0-p648

一番期待通りだった結果から.

foo.reduce(:+)
0.422865207
foo.to_a.reduce(:+)
1.08674423
foo.to_a.reverse.reduce(:+)
1.603410527
foo.each.reduce(:+)
0.383624219
foo.each.to_a.reduce(:+)
0.956897335
foo.reverse_each.reduce(:+)
1.028164733
foo.reverse_each.to_a.reduce(:+)
1.791400497

やっぱり to_aインスタンス化するので遅いですね. reverse_eachto_a 並に遅いです.each を使って定義されているとの事なので,配列に一旦押し込んでいるのでしょうか.

ruby 1.8.7-p358

Time Limit Exceedでした. この頃のRuby はやっぱり遅い!

ruby 2.3.3

foo.reduce(:+)
0.43357594311237335
foo.to_a.reduce(:+)
1.233360068872571
foo.to_a.reverse.reduce(:+)
1.7924626003950834
foo.each.reduce(:+)
0.5590240471065044
foo.each.to_a.reduce(:+)
1.1674661748111248
foo.reverse_each.reduce(:+)
1.1371833588927984
foo.reverse_each.to_a.reduce(:+)
1.949059072881937

2.0.0 と変化なし.ただ若干遅いような.

ruby 2.4.3

foo.reduce(:+)
0.4620166979730129
foo.to_a.reduce(:+)
0.5434980448335409
foo.to_a.reverse.reduce(:+)
0.8991025779396296
foo.each.reduce(:+)
0.36869976855814457
foo.each.to_a.reduce(:+)
0.5822492782026529
foo.reverse_each.reduce(:+)
0.8750727437436581
foo.reverse_each.to_a.reduce(:+)
1.2820214964449406

全ての to_a が早くなりました.foo.to_a.reduce(:+)foo.reduce(:+)0.1msしか違わない.

ruby 2.5.1

foo.reduce(:+)
0.31516589038074017
foo.to_a.reduce(:+)
0.6082005519419909
foo.to_a.reverse.reduce(:+)
1.1273395996540785
foo.each.reduce(:+)
0.32723737694323063
foo.each.to_a.reduce(:+)
0.604427982121706
foo.reverse_each.reduce(:+)
0.9205244313925505
foo.reverse_each.to_a.reduce(:+)
0.6740624848753214

reverse_each.to_a が早くなってる.to_a すると早くなるんですね…

ideone

ruby 2.3.3

foo.reduce(:+)
0.2855961509048939
foo.to_a.reduce(:+)
0.39363980293273926
foo.to_a.reverse.reduce(:+)
0.4211822748184204
foo.each.reduce(:+)
0.2322438396513462
foo.each.to_a.reduce(:+)
0.39031748846173286
foo.reverse_each.reduce(:+)
0.38831575214862823
foo.reverse_each.to_a.reduce(:+)
0.5566895194351673

Windows[msys2]

ruby 2.4.3p205

"ruby 2.4.3p205 (2017-12-14 revision 61247) [x64-mingw32]\n"

foo.reduce(:+)
0.6485602000029758
foo.to_a.reduce(:+)
0.3039164000074379
foo.to_a.reverse.reduce(:+)
0.3378013000037754
foo.each.reduce(:+)
0.6483177999907639
foo.each.to_a.reduce(:+)
0.31006479999632575
foo.reverse_each.reduce(:+)
0.9291686000069603
foo.reverse_each.to_a.reduce(:+)
0.5548352999903727

each より to_a したほうが早い.何で?

jit

Ruby はどんどん高速化され続けていて,Ruby 2.6ではJIT (Just-in-time) コンパイラが導入されています.(Ruby 2.6.0-preview2 Released) どうなるやら.