ruby - 数据结构 : iterating over two arrays vs converting to sets and performing intersect operation in ruby

Question

假设我有 a1 和 a2:

a1 = [1,2,3]
a2 = [4,2,5]

要查看 a1 是否与 a2 共享任何元素，我可以遍历每个元素并比较每个元素:

def intersect?(x,y)
  a1.each do |x|
    a2.each do |y|
      if x == y return true
    end
  end
  false
end

但更简单的是，(a1.to_set & a2.to_set).present? 给了我同样的答案。

我假设集合操作更快更有效？如果这是真的，考虑到每个数组上的 .to_set 操作的开销(如果有的话)是否仍然正确？

蒂亚

Answer 1

steenslag 的回答有一个有趣的观察，即 array & array 比 set & set 更快。看起来大部分惩罚似乎是从第一组的底层哈希中获取 key 以进行枚举的费用。在操作的左侧使用数组并在右侧使用集合的混合方法速度更快。如果您只想知道是否有任何交集，使用 #any? 的相同方法甚至更快:

#!/usr/bin/env ruby

require 'set'
require 'benchmark'

f = 10_000
ar1 = (1..(10*f)).to_a # 100_000 elements
ar2 = ((5*f)..(15*f)).to_a # also 100_000 elements
set1 = ar1.to_set
set2 = ar2.to_set
n = 10

Benchmark.bm(10) do |testcase|
  testcase.report('Array'){ n.times{ ar1 & ar2 } }
  testcase.report('Set'){ n.times{ set1 & set2 } }
  testcase.report('Set2'){ n.times{ ar1.select{ |element| set2.include? element } } }
  testcase.report('Set2present'){ n.times{ ar1.any?{ |element| set2.include? element } } }
end


$ ruby -v => ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]

                user     system      total        real
Array       0.680000   0.030000   0.710000 (  0.720882)
Set         1.130000   0.020000   1.150000 (  1.150571)
Set2        0.430000   0.000000   0.430000 (  0.434957)
Set2present  0.210000   0.010000   0.220000 (  0.220990)