1

各行にスペースで区切られた数字を含むファイルがあります。各行は番号のリストに対応しています。
現在、そのような行は約300,000行あります（各行には平均で約100個の数字が含まれています）。
そのようなすべてのリストの相互交差を見つけたいと思います。つまり、最初のリストが他のすべてのリストと交差し、次に2番目のリストが他のすべてのリストと交差するというように続きます。
使ってます 

set(a) & set(b)

ここで、aとbはリストであり、二重ループで反復されます。
しかし、これには時間がかかりすぎます。例：最初のリストが他のすべてのリストと交差している場合、約3分かかりました。
どうすればこれを効率的に行うことができますか？（他の言語/ツールを使用している可能性があります）

4

3 に答える 3

5

ここではジェネレーター式を使用する必要があります。これらは遅延評価を行い、多くのメモリを節約します。

In [46]: from itertools import imap

In [47]: a = [[1,2,3], [2,3,4], [3,4,5]]

In [48]: reduce(set.intersection,imap(set,a))
Out[48]: set([3])

あなたのファイルが次のようになると考えてください：

1 2 3
2 3 4
3 4 5

コード: 使用itertools.combinations():

with open("abc.txt") as f:
    lines=(map(int,x.split()) for x in f)
    for x in combinations(lines,2):
        print x,'-->',reduce(set.intersection,imap(set,x))
   ....:         
([1, 2, 3], [2, 3, 4]) --> set([2, 3])
([1, 2, 3], [3, 4, 5]) --> set([3])
([2, 3, 4], [3, 4, 5]) --> set([3, 4])
于 2013-01-22T10:21:59.247 に答える
1

逆インデックス、つまりマッピング番号=>この番号を含む行のリストを作成することで、これを最適化できると思います。たとえば、10行 5、100、200 で発生した場合は、

10: [5, 100, 200]

これをさらに最適化するために、行リストをペアのセットとして保存できます。

10: set( (5,100), (5,200), (100,200) )

次に、list_a + list_b の交点を計算するには、関連する行リストに が含まれるすべての数値を検索します(list_a, list_b)。

于 2013-01-22T11:25:26.640 に答える
1

最初のアイデアは、最初にすべてのセットを一度構築し、すべてがメモリに収まる場合は、それらを交差させることです。

300000 行と 300000 行のすべての交差が本当に必要な場合は、とにかく時間がかかります。たぶん、あなたの問題を再考する必要があります。

于 2013-01-22T10:42:38.447 に答える