在大列表中查找重複號碼的最快方法

我正在處理Ids（它是長數據類型）的大型列表（10^5的順序）。我必須在Id的列表中找到重複項。但我限制使用紅寶石。在大列表中查找重複號碼的最快方法

在這裏，我找到了一種方法來做到這一點。我將遍歷列表並將Id放在哈希中，但在放入哈希之前，我會檢查它是否已經在哈希中。

我不確定在RUBY中散列的複雜性。

請給我一個更好的主意。

來源

2013-10-09 viswas

要麼紅寶石還是什麼？ – sawa

你的想法聽起來不錯。它真的很慢嗎？請分享您的結果。 – Stefan

是什麼讓你認爲Ruby中哈希的複雜性與其他語言不同？只要負載因子不太接近1，散列通常被認爲需要O（1）次。 – pjs

爲什麼不使用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) }

來源

2013-10-09 12:57:58

好的解決方案。請注意，這相當於原始海報的建議（使用「哈希」）。解決方案是'O（n）'。 –

是的，除了可能使用更少的內存（取決於實現）之外，它幾乎相同。 –

理論上是的，但實際上，有沒有不使用'Hash'來處理'Set'的實現？ –

讓我們來看看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)

編輯：更新了基準內的重複查找並更新了結果。

來源

2013-10-09 14:14:57

您的實現缺乏收集重複項。 –

@KARASZIIstván檢查所有的代碼...有三種方法產生三種不同的基準。最後一個等於你的解決方案。 –

我檢查了你的代碼，這就是我寫評論的原因。你使用計數器創建了一個哈希，但是你需要從這些哈希中獲得重複數據，並且從基準測試中缺少這些重複數據。 –

在大列表中查找重複號碼的最快方法

回答

相關問題