ruby - 大きなリストで重複する番号を見つける最速の方法

Question

Id (長いデータ型) の大きなリスト (10^5 のオーダー) を扱っています。Id のリストで重複を見つける必要があります。しかし、私はルビーの使用に制限されています。

ここで私はこれを行う方法を見つけました。リストをトラバースして ID をハッシュに入れますが、ハッシュに入れる前に、それが既にハッシュされているかどうかを確認します。

RUBY のハッシュの複雑さについてはよくわかりません。

より良いアイデアを提案してください。

Answer 1

ベンチマークの内容を見てみましょう。

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)

編集:ベンチマーク内の重複した結果で更新し、結果を更新しました。