ruby-on-rails - Ruby - 通过嵌套属性选择属于两个数组的项目的最快方法

Question

我的 Ruby 查询真的很慢。我正在寻找一种更快的方法来选择属于两个数组的项目

listA 是具有属性 name

的 objectA 的列表

listB 是具有属性 name

的 objectB 的列表

listA 中可以有多个项目都具有相同的name，但 listB 中没有相同的name。 listA 中还有一些项目的name 不在listB 中。我想要一个函数(循环)来返回 listA 中的所有项目，其中它们的 name 在 listB 中。

这是我目前的解决方案，但它太慢了。我怎样才能让它更快？

z = 0
new = []
while z < listB.length 
    hold = listA.select{|obj| obj.name == listB[z].name}
    new += hold
    z += 1
end

Answer 1

您想最大限度地提高查找速度。您可以达到的最佳查找速度是使用哈希的 O(1)。下面描述的我的方法比您的代码快 1000 倍，比使用 include? for n=10000

的循环快 350 倍

编辑 2:This link更详细地解释了为什么哈希查找很快。

names = {}
listB.each{|item| names[item.name] = true}
result = listA.select{|item| names[item.name]}

编辑:基准更新。

• 03/08/2015 - 添加了 user12341234 设置方法

---

基准代码

class MyObject
  def initialize(name)
    @name = name
  end

  def name
    @name
  end
end

n=10000
k=n/10

listA = (1..n).map{ MyObject.new(('a'..'z').to_a.shuffle[0,8].join)}
listB = listA.sample(k)
listB += (1..(n-k)).map{ MyObject.new(('a'..'z').to_a.shuffle[0,8].join)}

require 'benchmark'
require 'set'

Benchmark.bm do |x|
    x.report("Hash") do
        names = {}
        listB.each{|item| names[item.name] = true}
        result = listA.select{|item| names[item.name]}
    end

    x.report("OP's code") do
        z = 0
        new = []
        while z < listB.length 
            hold = listA.select{|obj| obj.name == listB[z].name}
            new += hold
            z += 1
        end
    end

    x.report("Include") do
      names = listB.map(&:name)
      listA.select{|obj| names.include?(obj.name) }
    end

    x.report("Set") do 
        names = listB.map(&:name).to_set
        listA.select{|item| names.include?(item.name)}
    end
end

---

基准

规范:

• 英特尔酷睿 i7 920 @ 2.67 GHz
• 13 GB 内存
• Windows 8 x64
• ruby 21 x64

结果:

Algorithm       user     system      total        real
Hash         0.015000   0.000000   0.015000 (  0.013002)
OP's code   26.053000   0.016000  26.069000 ( 26.161283)
Include      9.219000   0.000000   9.219000 (  9.244161)
Set          0.016000   0.000000   0.016000 (  0.013001)