3

现在我有这个：

array1 = [obj1, obj2, obj3, obj4]
array2 = [obj1, obj2, obj5, obj6]

array1.each do |item1|
  array2.each do |item2|
    if (item1[0] == item2[0]) && (item1[1] == item2[1])
      p "do stuff"
    end
  end
end

我需要匹配每个数组中的 2 条数据，但是两个数组都非常大，我想知道是否有更快的方法来做到这一点。

我当前的设置需要为第一个数组中的每个元素查看第二个数组中的每个元素，这似乎非常低效。

4

3 回答 3

2

结合地图和路口：

(array1.map { |a| a.first 2 } & array2.map { |a| a.first 2 }).each do
  p "do_stuff"
end

性能应该不错。虽然内存密集。

于 2012-04-17T23:15:58.040 回答
1

如果您只拥有这两个数组，则无法避免 DigitalRoss 提到的 O(n^2) 复杂性。但是，您可以为数据编制索引，这样下次您就不必再重复一遍了。在最简单的情况下，您可以使用哈希来允许根据测试中使用的标准直接访问您的数据：

index1 = array1.each_with_object({}){|e, acc|
  acc[[e[0], e[1]]] ||= []
  acc[[e[0], e[1]]] << e
}

另一个数组也是如此。然后，您的循环将如下所示：

index1.each do |key1, vals1|
  if vals2 = index2[key1]
    vals1.product(vals2).each do |e1, e2|
      p do_stuff
    end
  end
end

我相信，也就是 O(n)。

于 2012-04-16T20:49:04.400 回答
1

这非常慢，因为 - 正如 DigitalRoss 已经说过的 - 它是 O(n^2)。假设 eql? 对你来说和 == 一样好，你可以建立一个索引并迭代它，而不是 O(n+m)：

array1 = [obj1, obj2, obj3, obj4]
array2 = [obj1, obj2, obj5, obj6]
index  = {}
found  = []

array1.each do |item1| index[item1.first(2)] = item1 end
array2.each do |item2|
  item1 = index[item2.first(2)]
  found << [item1,item2] if item1 then
end

found.each do |item1, item2| puts "do something" end

这假定 array1 中所有元素的前 2 个元素的组合在 array1 中是唯一的。如果不是这样，代码会稍微复杂一些：

array1 = [obj1, obj2, obj3, obj4]
array2 = [obj1, obj2, obj5, obj6]
index  = {}
found  = []

array1.each do |item1|
  key          = item1.first(2)
  index[key] ||= []
  index[key]  << item1
end
array2.each do |item2|
  items_from_1 = index[item2.first(2)]
  if items_from_1 then
    found.concat(items_from_1.map { |item1| [item1,item2] })
  end
end

found.each do |item1, item2| puts "do something" end

由于您没有提供任何示例数据，因此我没有测试代码。

我希望这会有所帮助。

于 2012-04-16T20:52:20.393 回答