0

リスト L の各要素は、(フィールド、サイズ) の形式のタプルです。例えば

L = [ (['A','B'], 5), (['A'], 6), ('C', 1)]

交差していないメンバーのみが含まれるようにリストを選別したいと思います。残りの各メンバーは、交差した可能性のある他のメンバーよりも大きくなりました。したがって、例のリスト L は次のように縮小されます。

L = [ (['A'], 6), ('C', 1)]

現在、私はそれを次のように実装しています：

def betterItem(x, y):
    return (x != y and
            set(x[0]) & set(y[0]) and
            x[1] > y[1])

for i in range(len(L)-1):
    L[:] = [x for x in L for y in L if betterItem(x, y)]

これを行うためのより良い/より高速な/よりPython的な方法はありますか?

助けてくれてありがとう！

4

1 に答える 1

1 
L = [(['A','B'], 5), (['A'], 6), (['C'], 1)]

# sort by descending value
L.sort(key=lambda s:s[1], reverse=True)

# keep track of what members have already occurred
seen = set()

# Cull L - ignore members already in `seen`
# (Because it is presorted, already-seen members must have had a higher value)
L = [seen.update(i) or (i,j) for i,j in L if seen.isdisjoint(i)]

結果は

[(['A'], 6), (['C'], 1)]

(このリスト内包表記はちょっとした手品を使用します:seen.update常に を返しNone、None or x常に を返します。xそのため、見たメンバーのリストを更新するという副作用のseen.update(i) or (i,j)あるタプルを返します。)(i,j)

sortこれは、O(n^2) ではなく、 のため、O(n log n) である必要があります。

于 2012-06-19T22:43:42.447 に答える