MASSIVE配列内のどの項目が複数回表示されるかを調べる方法は？

Question

これは非常に簡単な質問です。どのアイテムがリストに複数回表示されますか？

正解は["mike", "john"]です。解決

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

問題：私たちは行うことができますように

は思えます。ちょっと待って！どのような配列は本当に大きいの場合：それはちょうどそう起こっ

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

私は妥当な時間でこれを行う方法を見つけ出す必要があります。私たちは何百万と何百万というレコードを話しています。

この大規模な配列は、実際には10-20個の小さな配列の合計です。それらを比較するのが簡単な場合は、私に知らせてください - 私は困惑しています。

私たちは、1ファイルあたり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秒です。

Answer 2

ここに、これらと@ Pascalの方法をベンチマーク比較した2つのソリューションがあります。

使用は

require 'set' 

def multi_set(arr) 
    s1 = Set.new 
    arr.each_with_object(Set.new) { |e, smulti| smulti.add(e) unless s1.add?(e) }.to_a 
end 

arr = ["mike", "mike", "mike", "john", "john", "peter", "clark"]  
multi(arr) 
    #=> ["mike", "john"] 

s1を設定arrの全ての別個の要素を含むように構築されています。 s1.add?(e)は、が既に含まれている場合は、eがsmultiに追加されている場合は、smultiにその要素が含まれていない場合、nilを返します。 （Set#add?を参照してください）smultiがメソッドによって返されます。

使用Array#difference

Array#differenceは、私はRubyのコアにproposedを追加しました方法です。私の答えhereも参照してください。もちろん

class Array 
    def difference(other) 
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 } 
    reject { |e| h[e] > 0 && h[e] -= 1 } 
    end 
end 

def multi_difference(arr) 
    arr.difference(arr.uniq).uniq 
end 

ベンチマーク

def more_than_once(arr) 
    counts = Hash.new { |hash, key| hash[key] = 0 } 
    arr.each do |item| 
    counts[item] += 1 
    end 
    counts.select do |_, count| 
    count > 1 
    end.keys 
end 

require 'fruity' 

items = 30_000_000 
arr = items.times.map { rand 10_000_000 } 

compare do 
    Pascal  { more_than_once(arr) } 
    Set  { multi_set(arr) } 
    Difference { multi_difference(arr) } 
end 

Running each test once. Test will take about 4 minutes. 
Pascal is faster than Set by 19.999999999999996% ± 10.0% 
Set is faster than Difference by 30.000000000000004% ± 10.0% 

、difference、Rubyのコアの一部であれば、Cにおいて符号化され、最適化されるであろう。