Самый быстрый способ найти дублирующее число в большом списке

Question

Я имею дело с большим списком (порядка 10^5) идентификаторов (которые являются длинными типами данных). Я должен найти дубликаты в списке идентификаторов. Но я ограничусь использованием рубина.

Здесь я нашел способ сделать это. Я пройду список и поставлю идентификатор в хэш, но прежде чем вставлять его в хэш, я проверю, что он уже находится в хеше или нет.

Я не уверен в сложности хеша в 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) 

EDIT: Обновлено с дублированием в рамках теста и обновлены результаты.