根据另一个键，过滤字典列表中某个键内的重复项。

Question

我是一名有用的助手，可以为您翻译文本。

我有一个Python 3.5.2中的字典列表，我正在尝试“去重”。所有的字典都是唯一的，但是有一个特定的键我想要去重，保留具有最多非空值的字典。

例如，我有以下字典列表：

d1 = {"id":"a", "foo":"bar", "baz":"bat"}
d2 = {"id":"b", "foo":"bar", "baz":None}
d3 = {"id":"a", "foo":"bar", "baz":None}
d4 = {"id":"b", "foo":"bar", "baz":"bat"}
l = [d1, d2, d3, d4]

我希望将 l 过滤为只包含唯一 id 键的字典，保留空值最少的字典。在这种情况下，函数应该保留 d1 和 d4。

我的尝试是创建一个新的键值对 "value count"，如下所示:

for d in l:
    d['val_count'] = len(set([v for v in d.values() if v]))

现在我卡住了，不知道如何筛选我的字典列表以获取唯一的 ids，其中 val_count 键是更大的值。

我可以接受其他方法，但由于资源限制，无法在此项目中使用 pandas。

期望输出：

l = [{"id":"a", "foo":"bar", "baz":"bat"},
 {"id":"b", "foo":"bar", "baz":"bat"}]

- foobarbaz

---

如果您能提供一个预期输出的示例，那将会很有帮助。您对尝试失败的描述虽然不会造成伤害，但在这种情况下并没有太大的帮助。 - AGN Gazer

@AGNGazer 我会进行更新以使其更加清晰，但我在帖子中已包含了这一内容：在这种情况下，该函数应保留d1和d4。 - foobarbaz

当所有d具有相同数量的None或当所有d都至少包含一个None时，应该发生什么？ - AGN Gazer

@AGNGazer 在这种情况下，我愿意保留第一次出现的内容。 - foobarbaz

Answer 1

我会使用 groupby，然后从每个组中选择第一个：

1) 首先按键（以创建组）和空值的数量（您所述的目标）进行降序排序列表：

>>> l2=sorted(l, key=lambda d: (d['id'], -sum(1 for v in d.values() if v))) 

2) 然后按id进行分组，并在排序列表上以d的形式呈现每个迭代器的第一个元素：

>>> from itertools import groupby
>>> [next(d) for _,d in groupby(l2, key=lambda _d: _d['id'])]
[{'id': 'a', 'foo': 'bar', 'baz': 'bat'}, {'id': 'b', 'foo': 'bar', 'baz': 'bat'}]

如果你想要一个“裁决者”来选择第一个字典，如果它们在其他方面具有相同的空值计数，你可以添加一个枚举装饰器：

>>> l2=sorted(enumerate(l), key=lambda t: (t[1]['id'], t[0], -sum(1 for v in t[1].values() if v)))
>>> [next(d)[1] for _,d in groupby(l2, key=lambda t: t[1]['id'])]

我怀疑这个额外的步骤实际上并不是必要的，因为Python的排序（和sorted）是稳定排序，而序列只会根据键和空值计数从列表顺序改变。因此，除非你确定需要使用第二个版本，否则请使用第一个版本。

- dawg

---

不错，我喜欢使用 next。性能也很好，加一。 - jpp

这绝对是所有答案中表现最好的。谢谢！ - foobarbaz

@dawg 下划线的目的是什么？ - foobarbaz

@cdc200：下划线的目的是什么？groupby返回一个键和一个迭代器，用于按该键分组的项目。由于在这种情况下我们没有使用键，因此使用“_”作为丢弃占位符是一种常见的Python习惯用法。另一个下划线“_d”的作用是以紧凑的方式具有不同的“_d”与“d”。某些版本的Python不会将lambda的命名空间与周围的推导分开，如果意外更改循环变量，则可能会发生错误。 - dawg

Answer 2

你可以使用max:

d1 = {"id":"a", "foo":"bar", "baz":"bat"}
d2 = {"id":"b", "foo":"bar", "baz":None}
d3 = {"id":"a", "foo":"bar", "baz":None}
d4 = {"id":"b", "foo":"bar", "baz":"bat"}
l = [d1, d2, d3, d4]
max_none = max(sum(c is None for c in i.values()) for i in l)
new_l = [i for i in l if sum(c is None for c in i.values()) < max_none]

输出：

[{'foo': 'bar', 'baz': 'bat', 'id': 'a'}, {'foo': 'bar', 'baz': 'bat', 'id': 'b'}]

- Ajax1234

---

为了澄清，我正在寻找一种选择具有“最少”空值/无值的字典的解决方案，这意味着如果重复的id键字典有更多的Nones，我可能仍然可以保留一个具有None的字典。在那种情况下，这仍然有效吗？ - foobarbaz

@Ajax1234，我不知道，但是我不喜欢看到没有解释的负评。所以+1。 - jpp

顺便说一下，这个解决方案似乎没有处理重复的字典（即重复的字典会被输出两次）。 - jpp

Answer 3

如果你愿意使用第三方库，你可以按照None值的数量进行排序，然后将结果输入到toolz.unique中：

from toolz import unique
from operator import itemgetter

l_sorted = sorted(l, key=lambda x: sum(v is None for v in x.values()))
res = list(unique(l_sorted, key=itemgetter('id')))

[{'baz': 'bat', 'foo': 'bar', 'id': 'a'},
 {'baz': 'bat', 'foo': 'bar', 'id': 'b'}]

如果您无法使用toolz，源代码足够小，可以自行实现。

---

性能基准测试

我只包含了那些每个id仅返回一个结果的解决方案。许多解决方案并不考虑重复字典。

l = [d1, d2, d3, d4]*1000

%timeit dawg(l)  # 11.4 ms
%timeit jpp(l)   # 7.91 ms
%timeit tsw(l)   # 4.23 s

from operator import itemgetter
from itertools import groupby
from toolz import unique

def dawg(l):
    l2=sorted(enumerate(l), key=lambda t: (t[1]['id'], -sum(1 for v in t[1].values() if v), t[0]))
    return [next(d)[1] for _,d in groupby(l2, key=lambda t: t[1]['id'])]

def jpp(l):
    l_sorted = sorted(l, key=lambda x: sum(v is None for v in x.values()))
    return list(unique(l_sorted, key=itemgetter('id')))

def tsw(l):
    for d in l:
        d['val_count'] = len(set([v for v in d.values() if v]))
    new = [d for d in l if d['val_count'] == max([d_other['val_count'] for d_other in l if d_other['id'] == d['id']])]
    return [x for i, x in enumerate(new) if x['id'] not in {y['id'] for y in new[:i]}]

- jpp

---

我是基准测试的爱好者。谢谢你。但是为了公平起见，您应该使用我的答案中的非枚举版本，因为tool.unique也没有被枚举。这使得“dawg”版本的时间略微更快... - dawg

Answer 4

这里有一种使用列表推导的方法，它使用了你已经计算出来的 'val_count' 值：

new = [d for d in l if d['val_count'] == max([d_other['val_count'] for d_other in l if d_other['id'] == d['id']])]

给定：

[{'baz': 'bat', 'foo': 'bar', 'id': 'a', 'val_count': 3},
 {'baz': 'bat', 'foo': 'bar', 'id': 'b', 'val_count': 3}]

这个程序通过比较当前字典的'val_count'和所有具有相同'id'的字典中最大的'val_count'来工作。请注意，在平局的情况下，所有具有最大'val_count'的字典都将被保留。

以下代码行应处理平局，仅保留特定'id'的第一个实例：

final = [x for i, x in enumerate(new) if x['id'] not in {y['id'] for y in new[:i]}]

解决这个问题可能有更高效的方法，但是这个方法至少可以工作，并且根据您的数据集大小可能适合您的需求。

- sjw

---

你有任何关于如何打破平局的建议吗？ - foobarbaz

@cdc200 - 请查看编辑，以了解在出现平局的情况下仅保留某个“id”的第一个实例的方法。 - sjw

这个解决方案对于大型列表来说效率低下（请参见基准测试）。 - jpp

@jpp - 是的，这并不奇怪，因为当我写下这个解决方案时，其他解决方案并没有产生正确的结果，所以这只是一个快速的“口胡”解决方案。后来发布的解决方案显然更好。 - sjw

Answer 5

我会这样做：

num = [list(x.values()).count(None) for x in l]
ls = [x for _,x in sorted(zip(num, l), key=lambda z: z[0])]

然后从排序列表(ls)中保留您想要的尽可能多的值。

例如，为了仅保留具有最高数量的非-None值(所有具有相同数量的非-None值的字典)，您可以执行以下操作：

num = [list(x.values()).count(None) for x in l]
ls, ns = zip(*[(x, d) for d, x in sorted(zip(num, l), key=lambda z: z[0])])
top_l = ls[:list(reversed(ns)).index(ns[0])]

---

编辑：根据@jpp的评论，我已经更新了我的代码以处理重复的id键。以下是更新后的代码：

def agn(l):
    num = [list(x.values()).count(None) for x in l]
    ls, ns = zip(*[(x, d) for d, x in sorted(zip(num, l), key=lambda z: z[0])])
    top_l = ls[:list(reversed(ns)).index(ns[0])]
    return list(dict((d['id'], d) for d in top_l).values())

我们还可以使用与@jpp's answer中相同的定义和设置来添加时间比较：

In [113]: %timeit tsw(l)
3.9 s ± 60.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [114]: %timeit dawg(l)
7.48 ms ± 191 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [115]: %timeit jpp(l)
5.83 ms ± 104 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [116]: %timeit agn(l)
4.58 ms ± 86.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

- AGN Gazer

---

@jpp 我已更新我的解决方案以消除重复项。之前没有注意到这个要求。谢谢！ - AGN Gazer

Answer 6

@cdc200，你可以尝试下面的代码。我在这里使用了字典的概念。

注意：字典被定义为具有唯一键的无序数据项集合。

我使用了OrderedDict()代替dict()来保留键的顺序。查看这篇不错的文章Python中的OrderedDict - GeeksforGeeks。

import json
from collections import OrderedDict

d1 = {"id":"a", "foo":"bar", "baz":"bat"}
d2 = {"id":"b", "foo":"bar", "baz":None}
d3 = {"id":"a", "foo":"bar", "baz":None}
d4 = {"id":"b", "foo":"bar", "baz":"bat"}
l = [d1, d2, d3, d4]

d = OrderedDict ();

for index, item in enumerate(l):
    if item["id"] not in d:
        d[item["id"]] =item
    else:
        nones1, nones2 = 0, 0
        for k in item:
            if item[k] is None:
                 nones1 = nones1 + 1
            if d[item["id"]][k] is None:
                 nones2 = nones2 + 1

        if nones2 > nones1:
            d[item["id"]] = item

l = [dict_item for dict_item in d.values()]

print (l)

"""
{'foo': 'bar', 'id': 'a', 'baz': 'bat'}, {'foo': 'bar', 'id': 'b', 'baz': 'bat'}]
"""

# Pretty printing the above dictionary
print(json.dumps(l, indent=4))

"""
[
    {
        "foo": "bar",
        "id": "a",
        "baz": "bat"
    },
    {
        "foo": "bar",
        "id": "b",
        "baz": "bat"
    }
]
"""

谢谢。

- hygull

---

如果您能解释一下您提到的概念是如何应用的，那就太好了。 - Mad Physicist