Ruby - è un modo efficace per trovare la differenza tra due array molto grandi?

Question

Ho un problema riguardante l'efficienza e gli algoritmi quando si tratta di trovare la differenza tra due array molto grandi. Spero che qualcuno con una buona conoscenza degli algoritmi possa indicarmi la giusta direzione su come risolverlo, poiché le mie attuali implementazioni richiedono una quantità di tempo estremamente lunga.

Problema:

Ho due molto grandi array. Uno contiene un elenco di e-mail con nomi di dominio non validi e l'altro è un elenco misto che devo controllare con il primo array.

accounts_with_failed_email_domains = [279,000 records in here] 

unchecked_account_domains = [149,000 records in here] 

Che cosa devo fare è passare attraverso la lista dei unchecked_account_domains e quindi confrontare ogni voce per vedere se v'è una corrispondenza nel accounts_with_failed_email_domains. Ho bisogno di inserire tutte le corrispondenze tra gli elenchi in un array separato per essere elaborato in seguito.

Come scrivere in modo efficiente qualcosa che possa controllare rapidamente questi account. Ecco cosa ho provato finora.

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 

Questa implementazione di cui sopra è stata eseguita per sempre. Ecco il secondo tentativo che non si è ancora dimostrato migliore.

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 sembrava essere promettente, ma sono abbastanza sicuro che non sto usando questo modo corretto. Inoltre, ho provato a esaminare questa domanda comparing large lists ma questo è in python e non riesco a trovare un equivalente Ruby per set. Qualcuno ha qualche idea su come risolvere questo?

Answer 1

sembra che è possibile utilizzare Array#-:

result = unchecked_account_domains - accounts_with_failed_email_domains 

Answer 2

convertire la matrice di email falliti di un set (credo che il comando di Ruby è .to_set, leggere su di esso nella documentazione di Ruby). Quindi controlla ciascuna delle e-mail deselezionate sul set usando .include?.

Il motivo per cui viene eseguito per sempre è che percorre l'intero o gran parte dell'elenco per ciascun controllo. La classe dell'insieme dovrebbe cancellare l'elenco, rendendo le query molto più veloci.

Answer 3

Un Set sarebbe utile qui se si conosce l'array contiene oggetti unici (o non lo sei infastidito da perdere duplicati - che io non credo che tu sia), così semplicemente prendere il vostro grande array e fare:

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

Non avevo una nuova soluzione qui, perché le buone risposte erano già state prese. Tuttavia, volevo vedere se c'era una differenza di prestazioni tra le due soluzioni basate su codice.

Questa risposta è un punto di riferimento per evidenziare eventuali differenze di prestazioni nell'uso di Array#- e due usi di Set#include?. Il primo benchmark Set#include? esegue sempre la conversione dell'insieme e il secondo converte una volta e mantiene il set per le ricerche successive.

Ecco il codice che viene eseguito ogni test 50 volte:

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 

Ecco i risultati:

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) 

Chiaramente, se avete solo bisogno di un confronto singole differenze, utilizzare l'approccio Array#-. Tuttavia, se hai bisogno di fare questo tipo di cose più volte, la pre-conversione del set fa un'enorme differenza ed è migliore di Array#-. Il costo di convertire la matrice in un set è abbastanza alto (comparativamente), ma una volta che hai un set, esegue il confronto delle differenze molto più rapidamente.