Array Intersection Solution Benchmarks

array_intersection_benchmark.rb

require 'benchmark'

def cary array1, array2
  (array1 & array2).flat_map { |n| [n]*[array1.count(n), array2.count(n)].min }
end

def cary2 array1, array2
  cnt1 = cnt(array1)
  cnt2 = cnt(array2)

  (array1 & array2).flat_map { |n| [n]*[cnt1[n], cnt2[n]].min }
end

def cnt(arr)
  arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
end

def cam array1, array2
  array1.each_with_object(array2.dup).map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact
end

def mud array1, array2
  a1, a2 = array1.dup, array2.dup # we’ll mutate them

  loop.with_object([]) do |_, memo|
    break memo if a1.empty? || a2.empty?
    e = a2.delete_at(a2.index(a1.shift)) rescue nil
    memo << e if e
  end
end

def tommy array1, array2
  longer_array = array1.length > array2.length ? array1 : array2

  intersection = []
  count = 0
  longer_array.each do |item|
    if array1 == longer_array
      looped_array = array2
    else
      looped_array = array1
    end
    if item == looped_array[count]
      intersection.push(item)
    end
    count +=1
  end
  intersection
end

def ser array1, array2
  array1, array2 = [array1, array2].sort_by(&:size)
  arr_copy = array2.dup

  array1.each.with_object([]) do |el, arr|
    index = arr_copy.find_index(el)
    arr << arr_copy.slice!(index) if index
  end
end

def sah array1, array2
  a1_freq=Hash.new(0); a2_freq=Hash.new(0); dup_items=[];
  array1.each {|a| a1_freq[a]+=1 }
  array2.each {|b| a2_freq[b]+=1 }

  a1_freq.each {|k,v| a2_freq[k] ? dup_items+=[k]*[v,a2_freq[k]].min : nil}
end

# Test 1
# Example arrays processed 100,000 times

array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]  
num = 100000

Benchmark.bm(10) do |x|
  x.report("Cary:")       { num.times{cary array1, array2} }
  x.report("Cary+:")      { num.times{cary2 array1, array2} }
  x.report("Cam:")        { num.times{cam array1, array2 } }
  x.report("Mudasobwa:")  { num.times{mud array1, array2 } }
#  x.report("Tommy:")      { num.times{tommy array1, array2 } }
  x.report("Sergii:")     { num.times{ser array1, array2 } }
  x.report("Sahil:")      { num.times{sah array1, array2 } }
end

# Test 2
# 10,000 integer arrays of single digits processed 100 times
# (high degree of intersection between arrays)

array1 = array2 = []
10000.times{ array1 << rand(10) }
10000.times{ array2 << rand(10) }
num = 100

Benchmark.bm(10) do |x|
  x.report("Cary:")       { num.times{cary array1, array2} }
  x.report("Cary+:")      { num.times{cary2 array1, array2} }
  x.report("Cam:")        { num.times{cam array1, array2 } }
  x.report("Mudasobwa:")  { num.times{mud array1, array2 } }
#  x.report("Tommy:")      { num.times{tommy array1, array2 } }
  x.report("Sergii:")     { num.times{ser array1, array2 } }
  x.report("Sahil:")      { num.times{sah array1, array2 } }
end

# Test 3
# 10,000 integer arrays of integers between 1-10,000 processed 10 times
# (low degree of intersection between arrays)

array1 = array2 = []
10000.times{ array1 << rand(10000) }
10000.times{ array2 << rand(10000) }
num = 10

Benchmark.bm(10) do |x|
  x.report("Cary:")       { num.times{cary array1, array2} }
  x.report("Cary+:")      { num.times{cary2 array1, array2} }
  x.report("Cam:")        { num.times{cam array1, array2 } }
  x.report("Mudasobwa:")  { num.times{mud array1, array2 } }
#  x.report("Tommy:")      { num.times{tommy array1, array2 } }
  x.report("Sergii:")     { num.times{ser array1, array2 } }
  x.report("Sahil:")      { num.times{sah array1, array2 } }
end