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つのデータを一致させる必要がありますが、両方の配列が非常に大きいため、これを行うためのより高速な方法があるかどうか疑問に思っています。

私の現在の設定では、最初の配列の各要素について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

2つの配列がすべてである場合、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 に答える