python - python：根据分数删除重复元素

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，请改用。

结果（排序改变，因为 adict没有固定的排序）：

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

这将重建字典。如果涉及其他键，则需要为 each 存储整个字典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

使用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 3

这是我的解决方案，使用来自itertools的 groupby 。

>>> 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}

回复：阿什维尼

我已经进行了性能测试，比较了不同的解决方案。以下是图表形式的结果：

我在'id'这里只使用了 10 个不同的键值，您可以自己玩代码，看看 的组成如何lst影响结果。将值的数量更改为id列表中项目数量的一半使 Ashwini 成为明显的胜利者，并将我们其他人放在一起：

当您将O(n)解决方案与对O(n*log(n))数日志图中的解决方案进行比较时，它的外观如下：

所以，我不太确定就大 O 论点得出什么结论。

Answer 4

>>> 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 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'])]

您不妨决定先就地排序，以避免以触摸输入为代价的额外空间。

所有这些在时间和空间复杂性方面可能不是最优的，但它非常优雅。