蟒蛇：刪除基於分數

Question

重複的元素假設我有以下列表

l = [ {'id':1, 's':1.0 }, {'id':3, 's': 0.6}, {'id':1, 's': 1.5} ] 

我想刪除重複的'id'值，根據他們的's'值的元素。
在前面的例子中，我想放棄第一個元素，因爲第一個和第三個元素都有'id'==1，並且l[0]['s'] < l[2]['s']我想要l[0]被丟棄。

因此我預計輸出（我不關心的元素在輸出列表的順序）

[ {'id':1, 's':1.5}, {'id':3, 's':0.6} ] 

Answer 1

我會使用一個映射來跟蹤ID和他們的成績：

from collections import defaultdict 

id_to_scores = defaultdict(list) 

for entry in l: 
    id_to_scores[entry['id']].append(entry['s']) 

output = [{'id': k, 's': max(v)} for k, v in id_to_scores.iteritems()] 

使用.items()，而是如果你使用Python 3

結果（順序改變，因爲一個dict沒有固定的順序）：

>>> [{'id': k, 's': max(v)} for k, v in id_to_scores.iteritems()] 
[{'s': 1.5, 'id': 1}, {'s': 0.6, 'id': 3}] 

這將重建字典。如果有其他的鍵，你需要存儲整個字典每id，而不僅僅是得分：

per_id = defaultdict(list) 

for entry in l: 
    per_id[entry['id']].append(entry) 

output = [max(v, key=lambda d: d['s']) for v in per_id.itervalues()] 

Answer 2

>>> L = [ {'id':1, 's':1.0 }, {'id':3, 's': 0.6}, {'id':1, 's': 1.5} ] 
>>> res = {} 
>>> for d in L: 
     id_ = d['id'] 
     res[id_] = max(res.get(id_, {}), d, key=lambda x: x.get('s', float('-inf'))) 


>>> res.values() 
[{'s': 1.5, 'id': 1}, {'s': 0.6, 'id': 3}] 

Answer 3

這裏是我的解決方案，使用GROUPBY從itertools。

>>> l = [ {'id':1, 's':1.0 }, {'id':3, 's': 0.6}, {'id':1, 's': 1.5} ] 
>>> from itertools import groupby 
>>> key = lambda dct: dct['id'] 
>>> l.sort(key=key) 
>>> for key, group in groupby(l, key=key): 
...  print max(group, key=lambda dct: dct['s']) 
... 
{'s': 1.5, 'id': 1} 
{'s': 0.6, 'id': 3} 

回覆：阿什維尼

我已經做了performance test，比較不同的解決方案。這裏的結果，以圖表形式：

我只用10個不同的值，爲'id'關鍵在這裏，你可以與自己的代碼看lst成分如何影響結果玩。更改id值的數量列表中的項目數量的一半，使阿什維尼明確的勝利者，並集中使我們的休息：

這是當你比較的O(n)它的外觀解決方案在雙對數圖的O(n*log(n))解決方案：

所以，我不太清楚有關於大O參數得出什麼結論。

Answer 4

使用collections.defaultdict：

In [58]: dic=defaultdict(dict) 

In [59]: for x in lis: 
    idx=x['id'] 
    if dic[idx].get('s',float('-inf')) < x ['s']: 
     dic[idx]=x 
    ....:   

In [60]: dic.values() 
Out[60]: [{'id': 1, 's': 1.5}, {'id': 3, 's': 0.6}] 

使用簡單的dict：

In [71]: dic={} 

In [72]: for x in lis: 
    idx=x['id'] 
    if dic.get(idx, {'s': float('-inf')}) ['s'] < x['s']: 
     dic[idx]=x 
    ....:   

In [73]: dic.values() 
Out[73]: [{'id': 1, 's': 1.5}, {'id': 3, 's': 0.6}] 

Answer 5

>>> l2={} 
>>> for y in l: 
     l2.setdefault(y['id'],[]).append(y['s']) 
>>> l3=[{'id':k,'s':max(v)} for k,v in l2.items()] 
>>> print l3 

給出：

[{'id': 1, 's': 1.5}, {'id': 3, 's': 0.6}] 

Answer 6

排序降序s，從而使每個id，最高s排在第一位。然後只挑選第一個出現的id。

seen = set() 
output = [d for d in sorted(l, key=lambda d: d['s'], reverse=True) 
      if d['id'] not in seen and not seen.add(d['id'])] 

你可能會決定首先排序，以避免額外的空間以觸摸輸入爲代價。

所有這些在時間和空間複雜性方面可能都不是最佳的，但它非常優雅。