Ruby - 是找到兩個非常大的數組之間差異的有效方法嗎？

Question

當涉及到發現兩個非常大的陣列之間的差異時，我遇到了有關效率和算法的問題。我希望對算法有很好理解的人可以指出我如何解決這個問題的正確方向，因爲我目前的實現需要花費很長時間。我有兩個非常大的數組。我有兩個非常大的數組。其中一個包含具有無效域名的電子郵件列表，另一個列表是我需要檢查第一個數組的混合列表。

accounts_with_failed_email_domains = [279,000 records in here] 

unchecked_account_domains = [149,000 records in here] 

我需要做的就是去通過unchecked_account_domains列表，然後比較每個條目，看看是否有在accounts_with_failed_email_domains匹配。我需要在列表之間插入所有匹配的單獨數組，以便稍後處理。

我該如何高效地編寫能夠快速檢查這些帳戶的內容。這是我到目前爲止所嘗試過的。

unchecked_account_domains = [really big array] 
unchecked_account_domains = unchecked_account_domains.sort 

accounts_with_failed_email_domains = [another huge array].sort 

unchecked_account_domains.keep_if do |email| 
    accounts_with_failed_email_domains.any? { |failed_email| email == failed_email } 
end 

# Count to see how many accounts are left 
puts unchecked_account_domains.count 

上面的這個實現一直在運行。這是第二次嘗試，仍然證明不會更好。

unchecked_account_domains = [really big array] 
unchecked_account_domains = unchecked_account_domains.sort 

accounts_with_failed_email_domains = [another huge array].sort 

unchecked_account_domains.each do |email| 
    accounts_with_failed_email_domains.bsearch do |failed_email| 
    final_check << email if email == failed_email 
    end 
end 

# Count to see how many accounts are left 
puts final_check.count 

bsearch似乎很有希望，但我敢肯定我沒有正確使用它。此外，我試圖調查這個問題comparing large lists，但這是在python，我似乎無法找到set的Ruby等價物。有沒有人有任何想法如何解決這個問題？

Answer 1

好像你可以使用Array#-：

result = unchecked_account_domains - accounts_with_failed_email_domains 

Answer 2

失敗的郵件的數組轉換爲一組（我認爲Ruby的命令是.to_set，在Ruby文檔閱讀這件事）。然後使用.include?檢查每組未經檢查的電子郵件。

它永久運行的原因是它貫穿每個檢查的整個或大部分列表。集合類應該散列列表，使查詢速度更快。如果你知道數組包含獨特的項目（或者你因爲失去重複困擾 - 我不認爲你是）

Answer 3

一個Set在這裏很有用，所以乾脆把你的大陣，做：

require 'set' 
unchecked_account_domains = [really big array] 

accounts_with_failed_email_domains = Set.new([another huge array]) 
final_check = [] 

    unchecked_account_domains.each do |email| 
    final_check << email if accounts_with_failed_email_domain.include?(email) # .include? on a set is in O(1) look up time 
    end 

Answer 4

我在這裏沒有新的解決方案，因爲已經有了很好的答案。但是，我想知道兩種基於代碼的解決方案之間是否存在性能差異。

此答案是突出顯示使用Array#-和Set#include?兩種用法的任何性能差異的基準。第一個Set#include?基準測試始終進行設置轉換，第二個基準轉換一次並保留該設置以用於後續搜索。

這裏的每個運行測試50次代碼：

require 'set' 
require 'benchmark' 

string = 'asdfghjkl' 
Times = 50 

a = 279_000.times.map {|n| "#{n}#{string}" } 
b = 149_000.times.map {|n| "#{n*2}#{string}" } 

puts RUBY_DESCRIPTION 
puts "============================================================" 
puts "Running tests for trimming strings" 

Benchmark.bm(20) do |x| 
    x.report("Array#-:")  { Times.times {|n| a - b } } 
    x.report("Set#include? #1:") do 
    Times.times do |n| 
     d = [] 
     c = Set.new(b) 
     a.each {|email| d << email if c.include?(email) } 
    end 
    end 
    x.report("Set#include? #2:") do 
    c = Set.new(b) 
    Times.times do |n| 
     d = [] 
     a.each {|email| d << email if c.include?(email) } 
    end 
    end 
end 

下面是結果：

ruby 2.2.5p319 (2016-04-26 revision 54774) [x86_64-darwin14] 
============================================================ 
Running tests for trimming strings 
          user  system  total  real 
Array#-:    12.350000 0.250000 12.600000 (13.001546) 
Set#include? #1:  16.090000 0.330000 16.420000 (17.196469) 
Set#include? #2:  8.250000 0.100000 8.350000 ( 8.726609) 

顯然，如果你只需要一個單一的差異比較，使用Array#-方法。但是，如果您需要多次執行此類操作，則預先轉換該設置會產生巨大差異，並且性能會比Array#-好。將Array轉換爲Set的成本相當高（相對），但是一旦您設置了Set，它就會更快地執行差異比較。