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似乎很有希望,但我很确定我没有正确使用它.此外,我试着调查这个问题比较大型列表,但这是在python,我似乎无法找到一个Ruby的等价物set.有没有人对如何解决这个问题有任何想法？

Answer 1

看起来你可以使用Array#-:

result = unchecked_account_domains - accounts_with_failed_email_domains

Answer 2

我这里没有新的解决方案,因为已经采取了良好的答案.但是,我想看看这两个基于代码的解决方案之间是否存在性能差异.

这个答案是一个基准,以突出使用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#-.将数组转换为Set的成本相当高(相对而言),但是一旦有了Set,它就会更快地执行差异比较.