如何查找MASSIVE数组中的哪些项目不止一次出现？
这是一个非常简单的问题; 哪些项目不止一次出现在列表中？
array = ["mike", "mike", "mike", "john", "john", "peter", "clark"] 正确答案是["mike", "john"] 。
好像我们可以这样做：
array.select{ |e| ary.count(e) > 1 }.uniq
问题解决了。 可是等等！ 如果arrays非常大，该怎么办：
1_000_000.times { array.concat("1234567890abcdefghijklmnopqrstuvwxyz".split('')) }
碰巧我需要弄清楚如何在合理的时间内完成这项工作。 我们正在谈论数以百万计的记录。
对于它的价值，这个庞大的arrays实际上是10-20个较小arrays的总和。 如果比较那些比较容易，请告诉我 – 我很难过。
我们正在谈论每个文件10,000到10,000,000行，数百个文件。
有类似的东西
items = 30_000_000 array = items.times.map do rand(10_000_000) end puts "Done with seeding" puts puts "Checking what items appear more than once. Size: #{array.size}" puts t1 = Time.now def more_than_once(array) counts = Hash.new(0) array.each do |item| counts[item] += 1 end counts.select do |_, count| count > 1 end.keys end res = more_than_once(array) t2 = Time.now p res.size puts "Took #{t2 - t1}"
为你工作？
我的机器上的持续时间约为40秒。
这里有两个解决方案，它们与@ Pascal方法的基准比较。
使用集
require 'set' def multi_set(arr) s1 = Set.new arr.each_with_object(Set.new) { |e, smulti| smulti.add(e) unless s1.add?(e) }.to_a end arr = ["mike", "mike", "mike", "john", "john", "peter", "clark"] multi(arr) #=> ["mike", "john"]
正在构建s1以包含arr所有不同元素。 s1.add?(e)如果s1已经包含e ，则返回nil ，在这种情况下，如果smulti尚未包含该元素， smulti e添加到smulti 。 （请参阅Set smulti ）方法返回smulti 。
使用Array#difference
Array#difference是我建议添加到Ruby核心的方法。 另见我的答案。
class Array def difference(other) h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 } reject { |e| h[e] > 0 && h[e] -= 1 } end end def multi_difference(arr) arr.difference(arr.uniq).uniq end
基准
def more_than_once(arr) counts = Hash.new { |hash, key| hash[key] = 0 } arr.each do |item| counts[item] += 1 end counts.select do |_, count| count > 1 end.keys end require 'fruity' items = 30_000_000 arr = items.times.map { rand 10_000_000 } compare do Pascal { more_than_once(arr) } Set { multi_set(arr) } Difference { multi_difference(arr) } end Running each test once. Test will take about 4 minutes. Pascal is faster than Set by 19.999999999999996% ± 10.0% Set is faster than Difference by 30.000000000000004% ± 10.0%
当然，如果Ruby核心的一部分， difference将用C编码并进行优化。