2

いくつかの選択された回答の回答を見つけようとしましたが、うまくいかないようです。リストのリストをマージする必要があります。

[[283, 311], [311, 283, 316], [150, 68], [86, 119], [259, 263], [263, 259, 267], [118, 87], [262, 264], [264, 262], [85, 115], [115, 85], [244, 89], [140, 76, 82, 99], [236, 111], [330, 168], [76, 63, 107, 124, 128, 135, 140], [131, 254], [254, 131], [21, 38], [38, 21], [220, 291], [291, 220], [296, 46], [64, 53, 57, 61, 63, 65, 66, 76, 96, 100, 103, 114, 123, 127, 128, 130, 148, 149], [274, 240], [157, 225, 234], [225, 247], [233, 44], [89, 244], [80, 101], [210, 214], [78, 155], [55, 139], [102, 74, 75, 132], [105, 252], [149, 55, 59, 63, 71, 73, 81, 100, 102, 116, 122, 138, 146], [97, 231], [231, 97], [155, 78], [239, 305], [305, 239], [145, 94, 248], [147, 150], [61, 64], [152, 219], [219, 152], [246, 250], [252, 105], [223, 235], [235, 223], [237, 60, 344], [344, 237], [182, 129], [331, 117], [12, 2, 8, 10, 13, 15], [250, 246]]

私が欲しいのは、たとえば、に[283,311]存在することだけ[311,283,316]です。次に、両方をマージして、上記のリストに 1 つのリストのみを作成する必要があります。リストが他のリストに存在する場合は、リストをマージする必要があります。

ループ内のループを使用してそれを行うことができますが、これを達成するためのpythonicな方法を探していることに注意してください。また、少なくとも 1 つの共通要素を共有するリストをマージする方法を知っている場合は、共有してください。

編集 ：

Pythonicアプローチを探していることを忘れないでください。コアのPythonicアプローチを使用することは不可能だと思います。次に、ループを使用した次の可能な解決策は何ですか。リストのリストを30分ごとに100万を超えるアイテムとマージする必要があるため、効率が必要です。for ループ内で for ループを使用してから 2 つの項目を比較しましたが、時間がかかりすぎています。

4

3 に答える 3

3

私はこれがうまくいくと思う...

a = [[283, 311], [311, 283, 316], [150, 68], [86, 119], [259, 263], [263, 259, 267], [118, 87], [262, 264], [264, 262], [85, 115], [115, 85], [244, 89], [140, 76, 82, 99], [236, 111], [330, 168], [76, 63, 107, 124, 128, 135, 140], [131, 254], [254, 131], [21, 38], [38, 21], [220, 291], [291, 220], [296, 46], [64, 53, 57, 61, 63, 65, 66, 76, 96, 100, 103, 114, 123, 127, 128, 130, 148, 149], [274, 240], [157, 225, 234], [225, 247], [233, 44], [89, 244], [80, 101], [210, 214], [78, 155], [55, 139], [102, 74, 75, 132], [105, 252], [149, 55, 59, 63, 71, 73, 81, 100, 102, 116, 122, 138, 146], [97, 231], [231, 97], [155, 78], [239, 305], [305, 239], [145, 94, 248], [147, 150], [61, 64], [152, 219], [219, 152], [246, 250], [252, 105], [223, 235], [235, 223], [237, 60, 344], [344, 237], [182, 129], [331, 117], [12, 2, 8, 10, 13, 15], [250, 246]]
aa = set(map(frozenset,a))  #eliminate duplicates
result =  [x for x in aa if not any(x < y for y in aa)]

これによりfrozensetオブジェクトのリストが得られますが、簡単にリストのリストに戻すことができます。

result = [list(fset) for fset in result]

残念ながら、それは二次的な複雑さを持っています...それについて本当に何かする必要があるかどうかはわかりません...（それをリストのままにしておくと、FWIWよりもはるかに複雑になります）

アルゴリズム的に少し優れた2番目のアプローチを次に示します。

from itertools import takewhile
def foo2(aa):
    aa = sorted(set(map(frozenset,a)),key=len)
    def conditional(x,aa):
        xlen = len(x)
        return any(x < y for y in takewhile(lambda z: xlen <= len(z),aa))
    return [x for x in aa if not conditional(x,aa)]

もちろん、実際のデータで実際にパフォーマンスが向上するかどうかを確認する必要があります (テスト データの場合、リストが十分に大きくなく、conditional関数とtakewhileインスタンスを生成するオーバーヘッドがあり、lambda価値がありません。

好奇心のために、ここに私のベンチマークがあります：

a = [[283, 311], [311, 283, 316], [150, 68], [86, 119], [259, 263], [263, 259, 267], [118, 87], [262, 264], [264, 262], [85, 115], [115, 85], [244, 89], [140, 76, 82, 99], [236, 111], [330, 168], [76, 63, 107, 124, 128, 135, 140], [131, 254], [254, 131], [21, 38], [38, 21], [220, 291], [291, 220], [296, 46], [64, 53, 57, 61, 63, 65, 66, 76, 96, 100, 103, 114, 123, 127, 128, 130, 148, 149], [274, 240], [157, 225, 234], [225, 247], [233, 44], [89, 244], [80, 101], [210, 214], [78, 155], [55, 139], [102, 74, 75, 132], [105, 252], [149, 55, 59, 63, 71, 73, 81, 100, 102, 116, 122, 138, 146], [97, 231], [231, 97], [155, 78], [239, 305], [305, 239], [145, 94, 248], [147, 150], [61, 64], [152, 219], [219, 152], [246, 250], [252, 105], [223, 235], [235, 223], [237, 60, 344], [344, 237], [182, 129], [331, 117], [12, 2, 8, 10, 13, 15], [250, 246]]

def foo1(aa):
    aa = set(map(frozenset,a))  #eliminate duplicates
    return [x for x in aa if not any(x < y for y in aa)]

from itertools import takewhile
def conditional(x,aa,takewhile=takewhile):
    xlen = len(x)
    return any(x < y for y in takewhile(lambda z: xlen <= len(z),aa))

def foo2(aa):
    aa = sorted(set(map(frozenset,a)),key=len)
    return [x for x in aa if not conditional(x,aa)]

print set(foo1(a)) == set(foo2(a))

import timeit
N = 10000
print timeit.timeit('foo1(a)','from __main__ import foo1,a',number=N)
print timeit.timeit('foo2(a)','from __main__ import foo2,a',number=N)
于 2013-04-19T14:31:44.703 に答える
3

これは、多数の小さなセットがある場合、@ mgilson よりも高速であると思われる別のアプローチです。

from collections import defaultdict

sets = set(map(frozenset, lists))

def remove_subsets(sets):
    # map each element to the sets in which it occurs
    sets_containing = defaultdict(set)
    for s in sets:
        for x in s:
            sets_containing[x].add(s)

    for s in sets:
        supersets = set.intersection(*(sets_containing[x] for x in s))
        if len(supersets) == 1:
            yield s

違いは主に最後のループにあります。このループは、n(n-1)/2 個の異なるセットのペアすべてを実行するのではなく、外側のループのn 個のセットのみを実行し、次のいくつかの要素を含む候補スーパーセットのセットを実行します。検討中のセット。reduce空のセットを生成するときに早期に停止することで、さらに最適化できます。

于 2013-04-19T14:58:57.130 に答える