I have the following arrays:
a = [1, 1, 1, 1, 3]
b = [2, 3, 2, 3, 3]
c = [1, 1, 1, 1, 3]
my goal is to calculate the amount of extra repetitions for each column. Meaning in this case that [1,2,1] appears twice, meaning 1 duplicate, and likewise for [1,3,1] so in total the amount of duplicates is 2, once for [1,2,1] and once for [1,3,1]. I have developed the following 2 solutions but I don't know to be honest which one is the most performing and why:
Solution 1:
sum = 0
zip = a.zip(b, c)
zip.group_by { |e| e}
.select { |_, value| value.size > 1 }
.each_value { |value| sum += (value.size - 1) }
return sum
Solution 2:
zip = a.zip(b, c)
hash = Hash.new(0)
zip.each { |e| hash.store(e, hash[e]+1) }
hash.each{|e, _| hash[e] -= 1}
return hash.sum {|e, _| hash[e] }
thanks in advance
Illustrating Bench-marking :
require 'benchmark'
v1 = [1, 1, 1, 1]
v2 = [2, 3, 2, 3]
v3 = [1, 1, 1, 1 ]
def sol_1(a,b,c)
sum = 0
zip = a.zip(b, c)
zip.group_by { |e| e}
.select { |_, value| value.size > 1 }
.each_value { |value| sum += (value.size - 1) }
return sum
end
def sol_2(a,b,c)
zip = a.zip(b, c)
hash = Hash.new(0)
zip.each { |e| hash.store(e, hash[e]+1) }
hash.each{|e, _| hash[e] -= 1}
return hash.sum {|e, _| hash[e] }
end
n=1_000
Benchmark.bmbm do |x|
x.report("sol_1"){n.times{sol_1(v1, v2, v3)} }
x.report("sol_2"){n.times{sol_2(v1, v2, v3)} }
end
Results in:
Rehearsal -----------------------------------------
sol_1 0.011076 0.000000 0.011076 ( 0.011091)
sol_2 0.012276 0.000000 0.012276 ( 0.012355)
-------------------------------- total: 0.023352sec
user system total real
sol_1 0.007206 0.000000 0.007206 ( 0.007212)
sol_2 0.011452 0.000000 0.011452 ( 0.011453)
So, just by reading it both solutions are very similar in approach. While I am not 100% sure what you mean by most performing, but I'll guess that you mean computational complexity of both solutions - so computational cost for large inputs. When there is a lot of columns, the only element of the solution that takes the time is iterating over the array of columns - everything else will take very little time in comparison.
So in first solution, you're iterating 3 times - once to group the columns, second to select ones with duplicates and then 3rd time to count the repetitions (however here, in the worse case scenario, the array you iterate over has at most N/2 elements). So, in total you have 2.5 iterations over array of columns.
In second solution, you're also iterating 3 times. Firstly, over the array of columns to count how many times they appear, then over the result (which in a worst case scenario has same amount of elements) to subtract one from each number and finally to sum the numbers - this gives roughly 3 iterations.
So, first solution might be just slightly more performant - however when dealing with complexity we look at the type of function ignoring the number in front of it - in this case both solutions are linear. Additionally, different methods are optimized in different way in ruby. So the only hope of determining which one is more performant would go with benchmarks - repeating those algorithms 100 times for (the same) 10000 columns takes 10.5s for first solution and 18s for the second solution.
Here is a slightly (20%) faster solution to @steenslag's benchmark:
require 'matrix'
def sol_3(matrix)
Matrix.
columns(matrix).
to_a.
each_with_object({}) { |e, a|
digest = e.hash
a[digest] = a[digest].nil? ? 1 : a[digest] + 1
}.sum { |_, v| v > 1 ? 1 : 0 }
end
user system total real
sol_1 0.006908 0.000008 0.006916 ( 0.006917)
sol_2 0.011866 0.000018 0.011884 ( 0.011902)
sol_3 0.005532 0.000008 0.005540 ( 0.005555)
Complete script: https://gist.github.com/jaredbeck/edc708df10fcc0267db80bf1c31c8298