1

配列内の各配列要素の交点を見つけて、交点を取得したいと思います。

入力は配列の配列です。たとえば、「以下のこのスクリプトで説明する「list_arrays」」「「filter」は、観測される交差の全長に適用する必要がある制限です。出力は、次のような配列として期待されます」[[2 、4]]」

list_arrays = [[1, 2, 3, 4], [2, 5, 6], [1, 5, 8], [8, 2, 4]]
filter = 2

first_element_array = Array.new
list_arrays.each_with_index do |each_array1, index1|        
 list_arrays.each_with_index do |each_array2, index2|
  unless index1 < index2
   intersection = each_array1 & each_array2
   if intersection.length == filter.to_i
    first_element_array.push(intersection)
   end
  end
 end
end
puts first_element_array

配列の配列が長すぎるため（百万行）、この上記の手順は実行時間が長くなります。私はこの問題を処理するための簡単で素朴な方法が必要です。誰かがそれについて簡単なアイデアを持っていますか？

4

1 に答える 1

6

コードを解読すると、「コレクションのペアの組み合わせ間の交差が特定のサイズ（例では2）の場合、その交差を返す」というように思われます。私は書くだろう（機能的アプローチ）：

list_arrays = [[1, 2, 3, 4], [2, 5, 6], [1, 5, 8], [8, 2, 4]]
list_arrays.combination(2).map do |xs, ys|
  zs = xs & ys 
  zs.size == 2 ? zs : nil
end.compact
#=> [[2, 4]]

提案された最適化：1）セットを使用し、2）カスタム抽象化を使用します（ +Enumerable#map_compactと同等ですが、sをその場で破棄し、自分で記述します）。3）述語を満たさないサブ配列を除外します。mapcompactnil

require 'set'
xss = list_arrays.select { |xs| xs.size >= 2 }.map(&:to_set)
xss.combination(2).map_compact do |xs, ys|
  zs = xs & ys 
  zs.size == 2 ? zs : nil
end
#=> [#<Set: {2, 4}>]
于 2013-02-28T14:54:12.847 に答える