Compare speed of key lookup using Hash, Set and Array.

hash-array-set-lookup.rb

require "benchmark/ips"
require "benchmark/memory"
require "set"

SIZE = 50

def mk_key(i)
  "key-#{i}"
end

def init_set(size)
  memory = Set.new
  size.times { |i| memory << mk_key(i) }
  memory
end

def init_array(size)
  memory = Array.new
  size.times { |i| memory << mk_key(i) }
  memory
end

def init_hash(size)
  memory = Hash.new
  size.times { |i| memory[mk_key(i)] = nil }
  memory
end

def find_set_or_array(memory)
  SIZE.times { |i| memory.include?(mk_key(i)) }
end

def find_hash(memory)
  SIZE.times { |i| memory.key?(mk_key(i)) }
end

puts "SIZE = #{SIZE}\n"

Benchmark.ips do |x|
  x.report("set") { find_set_or_array(init_set(SIZE))  }
  x.report("array") { find_set_or_array(init_array(SIZE))  }
  x.report("hash") { find_hash(init_hash(SIZE)) }
  x.compare!
end

Benchmark.memory do |x|
  x.report("set") { find_set_or_array(init_set(SIZE))  }
  x.report("array") { find_set_or_array(init_array(SIZE))  }
  x.report("hash") { find_hash(init_hash(SIZE)) }
  x.compare!
end

Results:

SIZE = 10

Warming up --------------------------------------
                 set     8.957k i/100ms
               array    11.759k i/100ms
                hash     9.076k i/100ms
Calculating -------------------------------------
                 set     92.059k (± 2.8%) i/s -    465.764k in   5.063445s
               array    132.026k (± 2.8%) i/s -    670.263k in   5.080811s
                hash     99.548k (± 3.8%) i/s -    499.180k in   5.021989s

Comparison:
               array:   132026.5 i/s
                hash:    99547.6 i/s - 1.33x  slower
                 set:    92059.1 i/s - 1.43x  slower

Calculating -------------------------------------
                 set     2.736k memsize (     0.000  retained)
                        52.000  objects (     0.000  retained)
                        20.000  strings (     0.000  retained)
               array     1.800k memsize (     0.000  retained)
                        41.000  objects (     0.000  retained)
                        20.000  strings (     0.000  retained)
                hash     2.696k memsize (     0.000  retained)
                        51.000  objects (     0.000  retained)
                        20.000  strings (     0.000  retained)

Comparison:
               array:       1800 allocated
                hash:       2696 allocated - 1.50x more
                 set:       2736 allocated - 1.52x more

SIZE = 50

Warming up --------------------------------------
                 set     1.918k i/100ms
               array     1.794k i/100ms
                hash     1.869k i/100ms
Calculating -------------------------------------
                 set     17.833k (±13.7%) i/s -     88.228k in   5.063737s
               array     19.079k (± 3.2%) i/s -     96.876k in   5.082971s
                hash     20.073k (± 3.9%) i/s -    100.926k in   5.035749s

Comparison:
                hash:    20072.9 i/s
               array:    19079.1 i/s - same-ish: difference falls within error
                 set:    17833.3 i/s - same-ish: difference falls within error

Calculating -------------------------------------
                 set    12.656k memsize (     0.000  retained)
                       252.000  objects (     0.000  retained)
                        50.000  strings (     0.000  retained)
               array     8.488k memsize (     0.000  retained)
                       201.000  objects (     0.000  retained)
                        50.000  strings (     0.000  retained)
                hash    12.616k memsize (     0.000  retained)
                       251.000  objects (     0.000  retained)
                        50.000  strings (     0.000  retained)

Comparison:
               array:       8488 allocated
                hash:      12616 allocated - 1.49x more
                 set:      12656 allocated - 1.49x more

SIZE = 100

Warming up --------------------------------------
                 set   928.000  i/100ms
               array   602.000  i/100ms
                hash   919.000  i/100ms
Calculating -------------------------------------
                 set      8.938k (± 8.8%) i/s -     44.544k in   5.024931s
               array      6.391k (± 7.0%) i/s -     31.906k in   5.019873s
                hash      9.566k (± 9.6%) i/s -     47.788k in   5.053251s

Comparison:
                hash:     9565.5 i/s
                 set:     8938.5 i/s - same-ish: difference falls within error
               array:     6390.7 i/s - 1.50x  slower

Calculating -------------------------------------
                 set    25.184k memsize (     0.000  retained)
                       502.000  objects (     0.000  retained)
                        50.000  strings (     0.000  retained)
               array    17.064k memsize (     0.000  retained)
                       401.000  objects (     0.000  retained)
                        50.000  strings (     0.000  retained)
                hash    25.144k memsize (     0.000  retained)
                       501.000  objects (     0.000  retained)
                        50.000  strings (     0.000  retained)

Comparison:
               array:      17064 allocated
                hash:      25144 allocated - 1.47x more
                 set:      25184 allocated - 1.48x more