効率的ルビー

Question

で2つのアレイからのデータを一致させるためにどのように今、私はこれを持っている：

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つの作品を一致させる必要がありますが、両方の配列が非常に大きいと私は場合は思ったんだけどそここれを行うより速い方法です。

私の現在の設定では、第1の配列の各要素について第2の配列の各要素を調べる必要がありますが、これはひどく非効率的です。

Answer 1

：

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

パフォーマンスが良いことがあります。しかし、メモリ集中。

Answer 2

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）と思われます。

Answer 3

DigitalRossが既に述べたように、これはO（n^2）であるため、これは非常に遅いです。それを仮定すると？代わりに、あなたは、インデックスを構築し、その代わりに、それは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 

これは最初の2つの要素の組み合わせを想定していますarray1内のすべての要素のうち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 

：付属していない場合、コードは少し複雑になります。

私は役立つことを願っています。マップや交差点を組み合わせる