Show at what set size inclusion tests are faster for sets vs arrays.

set-cardinality-bm.rb

#!/usr/bin/env ruby

require 'benchmark'
require 'set'

N = 5_000_000

MAX_CARD = 5

ARRAYS = (0..MAX_CARD).map {|i| (1..i).to_a}
SETS   = ARRAYS.map {|a| a.to_set}

def pick(max,v)
  p = v % max
end

puts RUBY_DESCRIPTION
Benchmark.bm(15) do |x|
  (0..MAX_CARD).each do |i|
    a,s = ARRAYS[i], SETS[i]
    x.report("arr-mixed-#{i}") { N.times{ |j| a.include?( j % (i+1) ) } }
    x.report("set-mixed-#{i}") { N.times{ |j| s.include?( j % (i+1) ) } }
    x.report("arr-miss-#{i}") { N.times{ |j| a.include?( 0 ) } }
    x.report("set-miss-#{i}") { N.times{ |j| s.include?( 0 ) } }
  end
end

__END__
ruby 2.0.0p195 (2013-05-14 revision 40734) [x86_64-darwin11.4.2]
                      user     system      total        real
arr-mixed-0       0.550000   0.000000   0.550000 (  0.548123)
set-mixed-0       1.000000   0.000000   1.000000 (  1.002498)
arr-miss-0        0.540000   0.000000   0.540000 (  0.542482)
set-miss-0        0.910000   0.000000   0.910000 (  0.918988)
arr-mixed-1       0.670000   0.000000   0.670000 (  0.663650)
set-mixed-1       1.170000   0.000000   1.170000 (  1.174595)
arr-miss-1        0.880000   0.010000   0.890000 (  0.891336)
set-miss-1        0.740000   0.000000   0.740000 (  0.743757)
arr-mixed-2       0.860000   0.000000   0.860000 (  0.861132)
set-mixed-2       1.250000   0.000000   1.250000 (  1.250007)
arr-miss-2        0.910000   0.000000   0.910000 (  0.913444)
set-miss-2        0.830000   0.000000   0.830000 (  0.831363)
arr-mixed-3       1.200000   0.010000   1.210000 (  1.200926)
set-mixed-3       1.100000   0.000000   1.100000 (  1.108376)
arr-miss-3        1.010000   0.000000   1.010000 (  1.017262)
set-miss-3        1.020000   0.000000   1.020000 (  1.017147)
arr-mixed-4       1.460000   0.000000   1.460000 (  1.470597)
set-mixed-4       1.180000   0.000000   1.180000 (  1.183817)
arr-miss-4        1.500000   0.010000   1.510000 (  1.503451)
set-miss-4        0.830000   0.000000   0.830000 (  0.837214)
arr-mixed-5       1.280000   0.000000   1.280000 (  1.275837)
set-mixed-5       1.200000   0.000000   1.200000 (  1.211772)
arr-miss-5        1.620000   0.000000   1.620000 (  1.617467)
set-miss-5        1.000000   0.010000   1.010000 (  1.008918)


ruby 1.9.2p318 (2012-02-14 revision 34678) [x86_64-darwin10.8.0]
                     user     system      total        real
arr-mixed-0      0.740000   0.010000   0.750000 (  0.737946)
set-mixed-0      1.290000   0.000000   1.290000 (  1.297809)
arr-miss-0       0.600000   0.000000   0.600000 (  0.602810)
set-miss-0       0.770000   0.000000   0.770000 (  0.768927)
arr-mixed-1      0.880000   0.000000   0.880000 (  0.880739)
set-mixed-1      1.310000   0.010000   1.320000 (  1.316388)
arr-miss-1       0.700000   0.000000   0.700000 (  0.703231)
set-miss-1       0.850000   0.000000   0.850000 (  0.855361)
arr-mixed-2      1.070000   0.000000   1.070000 (  1.068229)
set-mixed-2      1.100000   0.010000   1.110000 (  1.102633)
arr-miss-2       1.070000   0.000000   1.070000 (  1.081605)
set-miss-2       0.950000   0.000000   0.950000 (  0.947256)
arr-mixed-3      0.920000   0.000000   0.920000 (  0.920215)
set-mixed-3      1.300000   0.010000   1.310000 (  1.308588)
arr-miss-3       1.140000   0.000000   1.140000 (  1.148342)
set-miss-3       1.080000   0.000000   1.080000 (  1.078418)
arr-mixed-4      1.320000   0.000000   1.320000 (  1.324027)
set-mixed-4      0.940000   0.010000   0.950000 (  0.942848)
arr-miss-4       1.260000   0.000000   1.260000 (  1.260542)
set-miss-4       1.140000   0.000000   1.140000 (  1.142898)
arr-mixed-5      1.300000   0.010000   1.310000 (  1.303553)
set-mixed-5      1.160000   0.000000   1.160000 (  1.171796)
arr-miss-5       1.700000   0.000000   1.700000 (  1.700517)
set-miss-5       0.870000   0.000000   0.870000 (  0.877750)


ruby 1.8.7 (2011-02-18 patchlevel 334) [i686-darwin10.8.0], MBARI 0x6770, Ruby Enterprise Edition 2011.03
                     user     system      total        real
arr-mixed-0      2.180000   0.000000   2.180000 (  2.178587)
set-mixed-0      3.280000   0.000000   3.280000 (  3.298847)
arr-miss-0       0.900000   0.010000   0.910000 (  0.895553)
set-miss-0       2.070000   0.000000   2.070000 (  2.078039)
arr-mixed-1      2.410000   0.000000   2.410000 (  2.417680)
set-mixed-1      3.270000   0.010000   3.280000 (  3.291919)
arr-miss-1       1.570000   0.000000   1.570000 (  1.575703)
set-miss-1       1.920000   0.000000   1.920000 (  1.925637)
arr-mixed-2      2.300000   0.010000   2.310000 (  2.311009)
set-mixed-2      2.840000   0.000000   2.840000 (  2.845896)
arr-miss-2       1.850000   0.010000   1.860000 (  1.856941)
set-miss-2       1.870000   0.000000   1.870000 (  1.873820)
arr-mixed-3      2.360000   0.000000   2.360000 (  2.365620)
set-mixed-3      2.960000   0.010000   2.970000 (  2.966920)
arr-miss-3       2.250000   0.000000   2.250000 (  2.265190)
set-miss-3       1.710000   0.000000   1.710000 (  1.708603)
arr-mixed-4      2.560000   0.010000   2.570000 (  2.573988)
set-mixed-4      3.100000   0.000000   3.100000 (  3.103052)
arr-miss-4       2.290000   0.010000   2.300000 (  2.299604)
set-miss-4       1.740000   0.000000   1.740000 (  1.749446)
arr-mixed-5      2.620000   0.000000   2.620000 (  2.629772)
set-mixed-5      3.190000   0.010000   3.200000 (  3.202189)
arr-miss-5       2.260000   0.000000   2.260000 (  2.272449)
set-miss-5       1.730000   0.000000   1.730000 (  1.730482)