arrays - 如何查找 MASSIVE 数组中哪些项出现多次？

Question

这是一个非常简单的问题；哪些项目在列表中出现多次？

array = ["mike", "mike", "mike", "john", "john", "peter", "clark"]

正确答案是["mike", "john"]。

看来我们可以这样做:

array.select{ |e| ary.count(e) > 1 }.uniq

问题已解决。可是等等!如果数组真的很大怎么办:

1_000_000.times { array.concat("1234567890abcdefghijklmnopqrstuvwxyz".split('')) }

碰巧我需要弄清楚如何在合理的时间内做到这一点。我们谈论的是数以百万计的记录。

就其值(value)而言，这个巨大的数组实际上是 10-20 个较小数组的总和。如果比较这些更容易，请告诉我 - 我被难住了。

我们谈论的是每个文件 10,000 到 10,000,000 行，数百个文件。

Answer 1

做类似的事情

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 秒。