ruby - 在大列表中查找重复数字的最快方法

Question

我正在处理一个大的 ID 列表（10^5 的顺序）（它们是长数据类型）。我必须在 ID 列表中找到重复项。但我仅限于使用红宝石。

在这里，我找到了一种方法来做到这一点。我将遍历列表并将 ID 放入哈希中，但在放入哈希之前，我将检查它是否已经在哈希中。

我不确定 RUBY 中哈希的复杂性。

请给我一个更好的主意。

Answer 1

你为什么不使用Set？

require 'set'

set = Set.new
numbers.each do |number|
  puts "Number #{number} is already in the set" unless set.add?(number)
end

或者只是查找重复项：

require 'set'
set = Set.new
duplicates = numbers.reject { |number| set.add?(number) } 

Answer 2

让我们看看Benchmark怎么说：

require 'benchmark'
require 'set'


def rand_n(n, max)
  randoms = Array.new
  loop do
    randoms << rand(max)
    return randoms.to_a if randoms.size >= n
  end
end

numbers = rand_n(10000, 10000000)

counter = Hash.new
time = Benchmark.measure do
  for number in numbers
    if counter.has_key?(number)
      counter[number] = counter[number]+1
    else
      counter[number]=1
    end
  end
duplicates = counter.select{|k,v| v > 1}
end
puts time

time1 = Benchmark.measure do
  counts = Hash.new{|h,k| h[k] = 0 }
  numbers.each{|n| counts[n] +=1}
  duplicates = counts.select{|k,v| v > 1}
end
puts time1

set = Set.new
time2 = Benchmark.measure do
  duplicates = numbers.reject { |number| set.add?(number) }
end

puts time2

和输出：

  0.000000   0.000000   0.000000 (  0.006114)
  0.010000   0.000000   0.010000 (  0.008529)
  0.010000   0.000000   0.010000 (  0.006098)

编辑：更新了基准中的重复发现并更新了结果。