速度測定 - longicornの日記

仕事をしていて、気になりだしたので家で実験。

Rubyのバージョン 1.8.5

each_with_indexが遅い

ソース

#!/usr/bin/env ruby

require 'benchmark'

n = 500000
Benchmark.bm do |x|
  ary = Array.new(n)

  x.report{
    i = 0
    ary.each do |val|
      val = 100
      i += 1
    end
  }

  x.report{
    ary.each_with_index do |val, i|
      val = 100
    end
  }
end

結果

$ ./hoge.rb 
      user     system      total        real
  0.920000   0.250000   1.170000 (  1.186080)  #=>each + カウンタ
  3.070000   0.370000   3.440000 (  3.459685)  #=>each_with_index


$ irb
irb(main):001:0> 3.459685/1.186080
=> 2.91690695399973

each_with_indexの方がeachよりも倍以上遅い。
何故？？

map

#!/usr/bin/env ruby

require 'benchmark'
require 'pp'


n = 500000
Benchmark.bm do |x|
  ary = Array.new(n)

  x.report{
    ary.map{100}

  }

  #破壊的
  x.report{
    i = 0
    ary.each do
      ary[i] = 100
      i += 1
    end
  }

  #新しいArrayに追加
  x.report{
    ret = []
    ary.each do
      ret << 100
    end
  }
end

$ ./hoge.rb 
      user     system      total        real
  0.410000   0.160000   0.570000 (  0.576854)  #=>map
  0.870000   0.090000   0.960000 (  0.984442)  #=>破壊的
  0.570000   0.140000   0.710000 (  0.723962)  #=>新しいArrayに追加

まあ予想通りにmapが早い。

HashとArray

これが今仕事で悩んでいる部分。(細かいことはいえないけど)

データ生成

なんか意味のあるデータが欲しいのでTime.nowを使用する。

#!/usr/bin/env ruby

require 'benchmark'
require 'pp'


n = 500000
Benchmark.bm do |x|
  ary = Array.new(n)
  h = Hash.new

  x.report{
    ary.map{Time.now}
  }

  x.report{
    n.times do |i|
      h[i] = Time.now
    end
  }
end

$ ./hoge.rb 
      user     system      total        real
  1.190000   0.490000   1.680000 (  3.246003)
  2.480000   0.540000   3.020000 (  3.347390)

結果を見ると、僅かだがHashの方が遅い。
これは予想外の結果。
ネットで調べた限りでは、Hashの方が早いとあったのでそう信じていた。
データ数が多く、全ての領域を使用する場合はHashの方が遅いのか？

まあ、Cで考えれば、Arrayは領域を取得するだけだが、
HashはHash値計算があるので遅いのか？
データ領域が巨大でも一部分しか使用しないのであれば、
圧倒的にHashが早いはずだけど。

メモリ使用率

ある程度の大きさのデータを作成してどのくらいメモリを使用するか。
データはIMbyte。

まずはArray

#!/usr/bin/env ruby

#IM
n = 1024*1024

ary = Array.new(n)

while 1
  sleep 10
end

Hash版。

#!/usr/bin/env ruby

#IM
n = 1024*1024

h = Hash.new(n)

n.times do |i|
  h[i] = 100
end

while 1
  sleep 10
end

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
hoge     22434  0.6  1.2   7956  6392 pts/1    S+   21:49   0:00 ruby ./hoge.rb  #=>Array
hoge     22462 49.8  5.3  29312 27728 pts/1    S+   21:50   0:02 ruby ./hoge.rb  #=>Hash

CPU使用率はHashの方がtimesで回しているので仕方ないとしても、
明らかにHashの方がメモリ使用量は多い。
結論としてはデータの量が多い場合にはArrayの方が効率がよい可能性が高い。

探索はHashの方が早いらしい。
http://www.loveruby.net/w/OptimizingRubyProgram.html

探索： Array と Hash

重複しない集合を得たいとき。Array に入れておいて uniq! するよりも Hash のキーとして登録していくほうが圧倒的に速い。 hash メソッドの値をうまく設定するのもコツ。

Array#index より Hash のほうが速い。どのくらい速いかというと、 Array のインデックス 0 でヒットしても Hash のほうが速い (ことが多い)。なぜだぁ。