哪个解决方案是最有效的，为什么要在一个复杂的列表中找到重复的数量?

Question

我有以下数组:

a = [1, 1, 1, 1, 3]
b = [2, 3, 2, 3, 3]
c = [1, 1, 1, 1, 3]

我的目标是计算每列的额外重复次数。在这种情况下，[1,2,1]出现了两次，也就是重复了一次，[1,3,1]也是如此所以总的重复次数是2次，一次是[1,2,1]一次是[1,3,1]。我已经开发了以下两种解决方案，但老实说，我不知道哪一种效果最好，为什么:

解决方案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

解决方案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

Answer 1

说明基准:

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

结果:

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)

Answer 2

所以，通过阅读这两个解决方案在方法上非常相似。虽然我不是100%确定你说的most performing是什么意思，但我猜你指的是两种解决方案的计算复杂性——所以大输入的计算成本。当有很多列时，解决方案中唯一需要花费时间的元素是遍历列数组——相比之下，其他所有元素所花费的时间都非常少。

所以在第一个解决方案中，你迭代3次-一次对列进行分组，第二次选择重复的列，然后第三次计算重复的次数(然而在这里，在最坏的情况下，你迭代的数组最多有N/2个元素)。因此，在列数组上总共有2.5次迭代。

在第二个解决方案中，你也迭代了3次。首先，在列数组上计算它们出现的次数，然后对结果(在最坏的情况下具有相同数量的元素)从每个数字中减去1，最后对数字求和-这大约给出3次迭代。

所以，第一个解可能是只是稍微提高了一点性能——然而，当处理复杂性时，我们会看函数的类型，忽略它前面的数字——在这种情况下，两种解决方案都是线性的。此外，不同的方法在ruby中以不同的方式进行了优化。因此，确定哪一个性能更好的唯一希望是通过基准测试——对(相同的)10000列重复这些算法100次，第一个解决方案需要10.5s，第二个解决方案需要18s。

Answer 3

这是一个稍微(20%)快一点的@steenslag基准的解决方案:

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)

完整脚本:https://gist.github.com/jaredbeck/edc708df10fcc0267db80bf1c31c8298