剔除列表以查找Python中最偉大的非相交成員

列表L中的每個元素都是表單（字段，大小）的元組。例如剔除列表以查找Python中最偉大的非相交成員

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這樣的方式？

感謝您的幫助！

來源

2012-06-19 Albeit

看起來相當pythonic給我。你在那裏的速度太慢了嗎？您可以嘗試從列表成員中找到匹配的索引對，然後僅在這些索引上調用betterItem來減少它們。 –

@Lattyware完成，感謝提醒......我的SO訪問往往是非常偶然的，我忘了這麼做。 – Albeit

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-19 22:43:42

這就是我正在尋找的東西，但它爲速度增益增加了太多的複雜性（不會有大量的列表來執行此操作）。謝謝。 – Albeit

剔除列表以查找Python中最偉大的非相交成員

回答

相關問題