如何在Python中从列表中删除带有嵌套字典的重复字典？

Question

我有一个包含嵌套字典的字典列表，就像这样：

v0 = [ { 'a': 1, 'b': { 'c': 3 } },
       { 'a': 1, 'b': { 'c': 3 }, 'd': 4 },
       { 'a': 1 },
       { 'a': 1, 'b': { 'c': 3 } } ]

如何去除重复的列表元素，使结果如下所示：

v1 = [ { 'a': 1, 'b': { 'c': 3 } },
       { 'a': 1, 'b': { 'c': 3 }, 'd': 4 },
       { 'a': 1 } ]

我不关心顺序，我只想要所有元素的集合。我看过很多类似的问题，但是这些答案只适用于列表中的简单字典，而不能处理嵌套字典。例如：

v1 = [dict(t) for t in set([tuple(d.items()) for d in v0])]

如果字典没有嵌套，这个方法就可以使用。但是由于它们是嵌套的，所以我会收到错误消息“TypeError: unhashable type: 'dict'”。

- Hilton Campbell

Answer 1

>>> v0 = [ { 'a': 1, 'b': { 'c': 3 } },
...        { 'a': 1, 'b': { 'c': 3 }, 'd': 4 },
...        { 'a': 1 },
...        { 'a': 1, 'b': { 'c': 3 } } ]
>>> out = []
>>> for v in v0:
...     if v not in out:
...         out.append(v)
...         
>>> out
[{'a': 1, 'b': {'c': 3}}, {'a': 1, 'b': {'c': 3}, 'd': 4}, {'a': 1}]

- wim

---

需要注意的是，这个解决方案的时间复杂度为O(n^2)，而更高效的解决方案可以达到O(n)。 - univerio

我最终使用了这个。幸运的是，我的列表很小，性能影响并不重要，而且我发现这非常易读。 - Hilton Campbell

@univerio：这怎么是 O(n^2) 的解决方案？for v in v0 是 O(n)，而 if v not in out 是 O(1)。 - Sameer Mirji

因为对于列表来说，“not in” 的时间复杂度是 O(n)，而不是 O(1)。 - wim

Answer 2

首先，考虑是否有更简单的想法已经足够好了。

如果您的字典集不是很大，那么最后一个选项非常容易——一个列表已经像一个集合一样工作了，除了每次搜索都是线性而不是常数时间。所以，相同的代码将需要二次时间而不是线性时间，但它会工作，并且非常简单，所以如果可以接受，就这样做吧。

如果您的字典集可能会变得相当大，仍然有一个相对简单的替代方案：基于树的集合，如blist或bintrees中的集合，可以在对数时间内进行搜索。因此，相同的代码将需要对数线性时间而不是线性时间——通常已经足够了——并且再次可以工作，并且非常简单。

如果即使对数线性时间也太慢了，那么您需要一种冻结字典类型和递归冻结函数。但是PyPI和ActiveState上有实现，例如frozendict，自己编写也不太困难。

实际上，您已经完成了一半。 set([tuple(d.items()] for d in v0])进行了单层冻结，并使用元组集合伪造了一个冻结字典（对于许多用例来说不起作用，但对于您的情况来说可以接受）。因此，您只需要递归地执行相同的操作即可。

- abarnert

Answer 3

如果您满意使用二次算法，那么：

uniq = [x for n, x in enumerate(v0) if v0.index(x) == n]

否则会变成类似这样的东西。

import json
uniq = {json.dumps(x, sort_keys=True):x for x in v0}.values()

- georg