Skip to content

Instantly share code, notes, and snippets.

@bbugh
Created March 8, 2018 16:04
Show Gist options
  • Save bbugh/cbbde8b48cbb16286044f6893e1f2e5f to your computer and use it in GitHub Desktop.
Save bbugh/cbbde8b48cbb16286044f6893e1f2e5f to your computer and use it in GitHub Desktop.
Benchmarking for checking if one array contains another in Ruby
Warming up --------------------------------------
subtract 233.432k i/100ms # higher is better
bitwise & == 164.352k i/100ms
bitwise & size 218.548k i/100ms
bitwise & [] 200.794k i/100ms
contains_all 74.648k i/100ms
contains_all_count 112.634k i/100ms
set 19.238k i/100ms
set cached 194.675k i/100ms
all? include? 144.048k i/100ms
Calculating -------------------------------------
subtract 5.723M (± 6.7%) i/s - 28.479M in 5.002088s
bitwise & == 2.752M (± 3.3%) i/s - 13.806M in 5.022462s
bitwise & size 4.803M (± 6.2%) i/s - 24.040M in 5.027104s
bitwise & [] 3.990M (± 4.7%) i/s - 20.079M in 5.043979s
contains_all 912.814k (± 4.9%) i/s - 4.554M in 5.002096s
contains_all_count 1.589M (± 6.2%) i/s - 7.997M in 5.057523s
set 206.133k (± 2.9%) i/s - 1.039M in 5.043780s
set cached 3.847M (± 4.4%) i/s - 19.273M in 5.020417s
all? include? 2.183M (± 3.3%) i/s - 10.948M in 5.021192s
Comparison: (higher is better)
subtract: 5723282.1 i/s
bitwise & size: 4803227.2 i/s - 1.19x slower
bitwise & []: 3990081.0 i/s - 1.43x slower
set cached: 3846838.4 i/s - 1.49x slower
bitwise & ==: 2751914.6 i/s - 2.08x slower
all? include?: 2182757.5 i/s - 2.62x slower
contains_all_count: 1588738.7 i/s - 3.60x slower
contains_all: 912813.5 i/s - 6.27x slower
set: 206133.5 i/s - 27.76x slower
# Collecting the solutions from Stack Overflow
# https://stackoverflow.com/questions/7387937/how-to-determine-if-one-array-contains-all-elements-of-another-array
require 'set'
require 'benchmark/ips'
sub_array = %i[alpha omega]
main_array = %i[alpha beta omega zeta shoe]
sub_array_set = Set.new(sub_array)
main_array_set = Set.new(main_array)
class Array
def contains_all?(ary)
ary.uniq.all? { |x| count(x) >= ary.count(x) }
end
end
def contains_all_count?(a, b)
b.all? { |x| a.count(x) >= b.count(x) }
end
Benchmark.ips do |x|
# this is the selected answer and it's the fastest
x.report('subtract') { (sub_array - main_array).empty? }
x.report('bitwise & ==') { (sub_array & main_array) == sub_array }
x.report('bitwise & size') { (sub_array & main_array).size == sub_array.size }
x.report('bitwise & []') { (sub_array & main_array) == [] }
x.report('contains_all') { main_array.contains_all?(sub_array) }
x.report('contains_all_count') { contains_all_count?(main_array, sub_array) }
x.report('set') { Set.new(main_array).subset?(Set.new(sub_array)) }
x.report('set cached') { main_array_set.subset?(sub_array_set) }
x.report('all? include?') { sub_array.all? { |e| main_array.include?(e) } }
x.compare!
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment