15

可変数のセット (数nと呼びましょう) があり、それぞれに最大で m 個の要素がある場合、セットのすべてのペアのペアごとの交差を計算する最も効率的な方法は何ですか? これは、 n 個すべての集合の交点とは異なることに注意してください。

たとえば、次のセットがあるとします。

A={"a","b","c"}
B={"c","d","e"}
C={"a","c","e"}

私は見つけることができるようにしたい:

intersect_AB={"c"}
intersect_BC={"c", "e"}
intersect_AC={"a", "c"}

もう 1 つの許容される形式 (簡単にする場合) は、特定のセット内のアイテムの、同じアイテムを含むセットへのマップです。例えば：

intersections_C={"a": {"A", "C"},
                 "c": {"A", "B", "C"}
                 "e": {"B", "C"}}

その方法の 1 つは、 n 個すべてのセットの和集合の各値をそれが発生するセットのリストにマッピングする辞書を作成し、それらのすべての値を繰り返し処理してintersections_C上記のようなリストを作成することであることはわかっていますが、nが増加し、セットのサイズが大きくなりすぎると、それがどのようにスケーリングするかはわかりません。

いくつかの追加の背景情報:

  1. 各セットはほぼ同じ長さですが、非常に大きい (すべてをメモリに格納するのが現実的な問題であり、必須ではありませんが、それを回避するアルゴリズムが望ましい)。
  2. 任意の 2 つのセット間の交点のサイズは、セット自体のサイズに比べて非常に小さい
  3. それが役に立てば、入力セットの順序付けについて必要なことは何でも想定できます。
4

3 に答える 3

8

これはあなたが望むことをするはずです

import random as RND
import string
import itertools as IT

いくつかのデータをモックする

fnx = lambda: set(RND.sample(string.ascii_uppercase, 7))
S = [fnx() for c in range(5)]

セットを以下でより簡潔に参照できるように、S のセットのインデックス リストを生成します。

idx = range(len(S))

S のアイテムのすべての可能な一意のペアを取得します。ただし、集合の交差は交換可能であるため、順列ではなく組み合わせが必要です

pairs = IT.combinations(idx, 2)

関数を書く 設定された交点を実行する

nt = lambda a, b: S[a].intersection(S[b])

この関数をペアに折り畳み、各関数呼び出しの結果をその引数にキー入力します

res = dict([ (t, nt(*t)) for t in pairs ])

OPに記載されている最初のオプションに従ってフォーマットされた以下の結果は、値が2つのシーケンスの集合集合である辞書です。これらのシーケンスの 2 つのインデックスで構成されるタプルにキー付けされた各値

このソリューションは、実際には2行のコードです。(i) 順列を計算します。(ii) 次に、各順列に何らかの関数を適用し、返された値を構造化されたコンテナー (キー値) コンテナーに格納します。

このソリューションのメモリ フットプリントは最小限ですが、最後のステップでジェネレータ式を返すことにより、さらに優れた結果を得ることができます。つまり、

res = ( (t, nt(*t)) for t in pairs )

このアプローチでは、ペアのシーケンスも対応する交差点もメモリに書き出されていないことに注意してください。つまり、ペアとresの両方が反復子です。

于 2014-12-09T01:10:48.687 に答える
3

入力セットが順序付けられていると仮定できる場合、疑似マージソート アプローチが有望と思われます。各セットをソートされたストリームとして扱い、ストリームを並行して進め、現在のすべてのイテレータの中で値が最も低いストリームのみを常に進めます。イテレータが進むたびに、現在の各値を新しい最小値と比較し、一致したものを同じ項目のコレクションにダンプします。

于 2014-12-09T01:27:12.483 に答える
-4

セットの交差法を使ってみてはどうでしょうか。下記参照：

A={"a","b","c"}
B={"c","d","e"}
C={"a","c","e"}

intersect_AB = A.intersection(B)
intersect_BC = B.intersection(C)
intersect_AC = A.intersection(C)

print intersect_AB, intersect_BC, intersect_AC
于 2014-12-09T05:11:26.000 に答える