「3件 または1000件 の値が配列の中に全部含まれているかどうか」のパフォーマンス比較 ( ruby )

http://d.hatena.ne.jp/torazuka/20150210/ruby
の件。

どれが速いのか気になったので調べてみた。

まずは3件

「3つの値が、大きさ不明の配列の中に全部含まれているかどうか」が計算の趣旨なんだけど、「3つ」の側が固定になっているところがポイント。

まずは実験に使ったソースコード：

require "set"
require "benchmark"

# 元々の実装
def tora( e, w, n, ar )
  ar.include?(e) && ar.include?(w) && ar.include?(n)
end

# 配列の引き算を使って短く書く
def minus( e, w, n, ar )
  ([e, w, n] - ar).empty?
end

# 私見では、普通な感じ。
def kirika( e, w, n, ar )
  [e,w,n].all?{|x| ar.include? x }
end

# 難しい文法を利用
def ciel( e, w, n, ar )
  [e,w,n].all?(&ar.method(:include?))
end

# Set を利用
def yancya( e, w, n, ar )
  Set[e, w, n].subset? ar.to_set
end

# ar の側でループを回す。any の中に副作用があって気持ち悪い。
def nabe( e, w, n, ar )
  s=[e,w,n]
  ar.any?{ |x| s.delete x;  s.empty? }
end

srand 0

(4..16).map{ |x| 2**x }.each do |size|
  data = (1024*1024/size).times.map{ |ix|
    ar =Array.new(size){ [rand(10), rand(10)] }
    ewn = [
      ix[0]==0 ? ar.sample : -1,
      ix[1]==0 ? ar.sample : -1,
      ix[2]==0 ? ar.sample : -1,
    ]
    [ ewn, ar ]
  }

  puts "ar.size : #{data.first.last.size}"
  Benchmark.bmbm do |x|
    x.report( "tora" ){ data.each{ |(e,w,n),ar| tora( e, w, n, ar ) } }
    x.report( "minus" ){ data.each{ |(e,w,n),ar| minus( e, w, n, ar ) } }
    x.report( "kirika" ){ data.each{ |(e,w,n),ar| kirika( e, w, n, ar ) } }
    x.report( "ciel" ){ data.each{ |(e,w,n),ar| ciel( e, w, n, ar ) } }
    x.report( "yancya" ){ data.each{ |(e,w,n),ar| yancya( e, w, n, ar ) } }
    x.report( "nabe" ){ data.each{ |(e,w,n),ar| nabe( e, w, n, ar ) } }
  end
end

環境は、ruby 2.2.0。on Yosemite。

ベンチマークの結果は下図。
縦軸は、「tora」の処理時間を 1 とした相対値。

tora, kirika, ciel は、実質的な内容が同じなので時間に差がない。
tora だけは [e, w, n] という配列を作らない分速いかもしれない。

nabe が一番遅いと予想していたんだけど意外に健闘している。
それにしても、any? の中に副作用があるのは気持ち悪い。

yancya は、調査対象の値が 3つしかないので、検索が早いというメリットより Set の構築に時間が掛かるというデメリットがまさっていて、動作が遅い。

minus は、nabe と実質的に同じ計算だと思っていたんだけど、意外に遅い。なんでだろ。
引き算を速くするための工夫がアダになっていたりするのかなぁ。

1000件でもう一度

タイトルと内容があっていないというリクエストがあったので、内容をタイトルに合わせるべく、要素数を 1000 にしてもう一度。

結局タイトルも変えたけど。

1000個の ar.include?(e[0]) && ... && ar.include?(e[999]) を書こうかとも思ったけど、やっぱりやめて、今回は tora 省略。

まずは実験コード：

require "set"
require "benchmark"

# 配列の引き算を使って短く書く
def minus( ewn, ar )
  (ewn - ar).empty?
end

# 私見では、普通な感じ。
def kirika( ewn, ar )
  ewn.all?{|x| ar.include? x }
end

# 難しい文法を利用
def ciel( ewn, ar )
  ewn.all?(&ar.method(:include?))
end

# Set を利用
def yancya( ewn, ar )
  ewn.to_set.subset? ar.to_set
end

# ar の側でループを回す。any の中に副作用があって気持ち悪い。
def nabe( ewn, ar )
  s=ewn.dup
  ar.any?{ |x| s.delete x;  s.empty? }
end

srand 0

EWN=1000

(4..16).map{ |x| 2**x }.each do |size|
  data = (1024*128/size).times.map{ |ix|
    ar =Array.new(size){ [rand(10), rand(10)] }
    ewn = Array.new( ix.odd? ? ( size % 99 ) : 100 ){ ar.sample }
    ewn.push  [-1-rand(10), -1-rand(10)]  while ewn.size<EWN
    [ ewn, ar ]
  }
  puts "ar.size : #{data.first.last.size}"
  Benchmark.bmbm do |x|
    x.report( "minus" ){ data.each{ |(ewn),ar| minus( ewn, ar ) } }
    x.report( "kirika" ){ data.each{ |(ewn),ar| kirika( ewn, ar ) } }
    x.report( "ciel" ){ data.each{ |(ewn),ar| ciel( ewn, ar ) } }
    x.report( "yancya" ){ data.each{ |(ewn),ar| yancya( ewn, ar ) } }
    x.report( "nabe" ){ data.each{ |(ewn),ar| nabe( ewn, ar ) } }
  end
end

ベンチマークの結果は下図。
縦軸は、「kirika」の処理時間を 1 とした相対値。

件数が増えるとだいぶ様子が変わると予想していたんだけど、大差ない感じ。あれー。
minus の大躍進を予想していたんだけど、そうでもない感じ。

測ってみないとわからんね。