3

私は約のデータセットを持っています。可変長の 9K リスト (1 ～ 100K 要素)。このデータセットで考えられるすべての 2 リストの組み合わせの交点の長さを計算する必要があります。各リストの要素は一意であるため、Python でセットとして保存できることに注意してください。

Pythonでこれを実行する最も効率的な方法は何ですか?

編集交差値を対応するリストのペアに一致させる機能が必要であることを指定するのを忘れていました。迅速な対応に感謝し、混乱をお詫びします。

4

3 に答える 3

3

たとえば、セットが s に格納されている場合:

s = [set([1, 2]), set([1, 3]), set([1, 2, 3]), set([2, 4])]

次に、itertools.combinationsを使用してそれらを 2 つずつ取得し、交差を計算できます (Alex が指摘したようにcombinations、バージョン 2.6 以降でのみ使用できることに注意してください)。ここにリスト内包表記があります（例のためだけに）：

from itertools import combinations
[ i[0] & i[1] for i in combinations(s,2) ]

または、ループで、おそらく必要なものです：

for i in combinations(s, 2):
    inter = i[0] & i[1]
    # processes the intersection set result "inter"

したがって、それらのそれぞれの長さを取得するには、その「処理」は次のようになります。

    l = len(inter)

これは、イテレータを使用してすべての組み合わせを計算し、それらすべてを事前に準備するわけではないため、非常に効率的です。

編集: このメソッドでは、リスト "s" 内の各セットは、実際には、ジェネレーターのように、セットを返す別のものになる可能性があることに注意してください。メモリが不足している場合は、リスト自体が単なるジェネレーターになる可能性があります。ただし、これらの要素をどのように生成するかによっては、はるかに遅くなる可能性がありますが、セットのリスト全体を同時にメモリに保持する必要はありません (あなたのケースでは問題になるわけではありません)。

たとえば、各セットが関数から作成されている場合gen:

def gen(parameter):
    while more_sets():
        # ... some code to generate the next set 'x'
        yield x

with open("results", "wt") as f_results:
    for i in combinations(gen("data"), 2):
        inter = i[0] & i[1]
        f_results.write("%d\n" % len(inter))

編集2：インデックスを収集する方法（redratのコメントに従って）。

コメントで答えた簡単な解決策に加えて、セットのインデックスを収集するより効率的な方法は、 のリストでは(index, set)なく のリストを持つことですset。

新しい形式の例:

s = [(0, set([1, 2])), (1, set([1, 3])), (2, set([1, 2, 3]))]

とにかく組み合わせを計算するためにこのリストを作成している場合は、新しい要件に簡単に適応できるはずです。メインループは次のようになります。

with open("results", "wt") as f_results:
    for i in combinations(s, 2):
        inter = i[0][1] & i[1][1]
        f_results.write("length of %d & %d: %d\n" % (i[0][0],i[1][0],len(inter))

ループでは、タプルi[0]になるので、最初のセットであるそのインデックスもそうです。i[1](index, set)i[0][1]i[0][0]

于 2009-11-18T17:59:17.390 に答える
2

結果の (N x N/2) 行列、つまり O(N 二乗) 出力を生成する必要があるため、O(N 二乗) 未満のアプローチはありません。もちろん、どの言語でも同様です。（Nはあなたの質問では「約9K」です）。したがって、(a) 必要な N 個のセットを作成し、(b) それらを繰り返し処理して出力を生成すること、つまり最も単純なアプローチよりも本質的に速い方法はないと思います。IOW:

def lotsofintersections(manylists):
  manysets = [set(x) for x in manylists]
  moresets = list(manysets)
  for  s in reversed(manysets):
    moresets.pop()
    for z in moresets:
      yield s & z

このコードはすでにいくつかのマイナーな最適化を追加しようとしています (たとえば、他の O(N 二乗) 係数を追加する可能性のあるリストの先頭からのスライスまたはポップを回避することによって)。

利用可能なコアやノードが多数あり、並列アルゴリズムを探している場合は、もちろん別のケースです。その場合は、クラスターの種類、サイズ、ノードとコアが最適に通信できる方法について言及できますか?など？

編集：OPがコメント（！）でさりげなく言及しているように、交差するセットの数が実際に必要であると述べています（本当に、仕様のそのような重要な部分を省略するのはなぜですか?!少なくとも質問を編集してそれらを明確にしてください...） 、これを次のように変更するだけで済みます。

  L = len(manysets)
  for i, s in enumerate(reversed(manysets)):
    moresets.pop()
    for j, z in enumerate(moresets):
      yield L - i, j + 1, s & z

（プログレッシブ識別子を「1から数える」必要がある場合-そうでなければ明らかな変更）。

しかし、それが仕様の一部である場合は、より単純なコードを使用することもできます。moresets は忘れてください。

  L = len(manysets)
  for i xrange(L):
    s = manysets[i]
    for j in range(i+1, L):
      yield i, j, s & manysets[z]

今回は、多様性のために、代わりに「0からカウント」したいと仮定します;-)

于 2009-11-18T17:36:58.320 に答える
0

これを試して：

_lists = [[1, 2, 3, 7], [1, 3], [1, 2, 3], [1, 3, 4, 7]]
_sets = map( set, _lists )
_intersection = reduce( set.intersection, _sets )

インデックスを取得するには:

_idxs = [ map(_i.index, _intersection ) for _i in _lists ]

乾杯、

ホセ・マリア・ガルシア

PS：申し訳ありませんが、質問を誤解しました

于 2009-12-22T11:19:02.343 に答える