Python中的reduce函数用于找到集合的并集。

Question

我正在尝试找到一组集合的并集。具体来说，我想要字典 periodic_gs 中每个键对应的 networkx 图中节点列表的并集。我希望使用 reduce 函数，因为它似乎可以合理地将所有 periodic_gs[x].nodes()（其中 x 是 periodic_gs 的键）的并集进行聚合。

以下是我的尝试:

reduce(lambda x,y: set(periodic_gs[x].nodes()).union(set(periodic_gs[y].nodes())), periodic_gs.keys(), {})

对我来说，这意味着在字典中跨每个图形取节点的并集。由于某种原因，Python告诉我：TypeError: unhashable type: 'dict'。我没有看到这个TypeError，因为periodic_gs.keys()是键列表（它们是字符串，但我不知道这会有什么影响），当替换成lambda函数的参数时会起作用。

是什么导致了类型错误，我该如何修复它？

- CodeKingPlusPlus

---

“集合的集合的并集”：一个集合不能包含另一个集合。 - Ashwini Chaudhary

发布一些样本数据和预期输出。 - Ashwini Chaudhary

Answer 1

你可以像这样使用set.union：

>>> lis = [{1, 2, 3, 4}, {3, 4, 5}, {7, 3, 6}]
>>> set().union(*lis)
set([1, 2, 3, 4, 5, 6, 7])

你可以使用reduce来做到这一点，但不要这样做：

>>> reduce(set.union, lis)
set([1, 2, 3, 4, 5, 6, 7])

由于此reduce在构建和丢弃所有中间集合时需要二次时间：

In [1]: from functools import reduce

In [2]: sets = [{x} for x in range(1000)]

In [3]: %timeit set().union(*sets)
40.9 µs ± 1.43 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [4]: %timeit reduce(set.union, sets)
4.09 ms ± 587 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

这个测试案例的速度慢了100倍，而且可能会更糟。

对于你的代码，应该这样做：

set().union(*(x.nodes() for x in periodic_gs.values()))

- Ashwini Chaudhary

---

不过，对于一个序列的序列和一个空的起始 set()，并没有必要使用 union()。 - Martijn Pieters

*的文档在哪里？ - CodeKingPlusPlus

@CodeKingPlusPlus *args和**kwargs是什么意思？ - Ashwini Chaudhary

@ChaimG 我也提供了一个答案。 - Martijn Pieters

Answer 2

{} 是一个空字典，而不是一个集合。使用 set() 来创建一个空集合。

然而，我认为你误解了 reduce() 在这里的工作方式；x 是 lambda 的前一个返回值，而 y 是序列中的下一个值。因为你返回了一个集合，所以 x 在这里总是一个集合，而你不能将其用作 periodic_gs 的键。

如果你想要得到图中所有节点的并集，可以使用 itertools.chain.from_iterable() 和 set()：

from itertools import chain

set(chain.from_iterable(periodic_gs[key].nodes() for key in periodic_gs))

这将从每个 nodes() 调用中创建一个集合。

要使用 reduce()，您需要考虑第一个参数始终是一个集合：

reduce(lambda res, key: res.union(periodic_gs[key].nodes()),  periodic_gs, set())

我假设这里的periodic_gs是可迭代的（产生键），就像普通字典一样。如果不是，请使用periodic_gs.keys()。

下面是一个使用普通字典的快速演示：

>>> example = {'foo': [1,2,3], 'bar': [3, 4, 1]}
>>> reduce(lambda res, key: res.union(example[key]), example, set())
set([1, 2, 3, 4])

- Martijn Pieters

---

现在它显示为“不可哈希类型：set”。 - CodeKingPlusPlus

@CodeKingPlusPlus：你使用reduce的方式不对，输出总是一个集合，但你却假设x是其他东西。 - Martijn Pieters

Answer 3

你的代码存在几个问题。 你提供给reduce的初始化器{}是一个空的dict，而不是你所假设的set，因此导致了第一个类型错误。 然而，即使你解决了这个问题，仍然存在一个更大的问题： lambda计算出一个包含节点的set对象，并且这个set被用作下一次调用lambda的x值，它试图将其用作periodic_gs的键，从而导致第二个类型错误。 更重要的是，如果你只是用它们来访问值，那么在迭代字典的键时没有意义; 只需一开始就迭代值！ 将一堆列表转换为集合，然后取它们的并集也没有意义，当你可以将它们全部连接起来并取结果的并集时。

我建议完全重写代码如下：

set(n for val in periodic_gs.values() for n in val.nodes())

- jwodder

Answer 4

您可以使用reduce函数来获取多个集合的并集，如下所示：

>>> import operator
>>> a = set([1, 3, 5])
>>> b = set([2, 4, 6])
>>> c = set([0, 7, 8])
>>> reduce(operator.or_, [a, b, c])
set([0, 1, 2, 3, 4, 5, 6, 7, 8])

- FogleBird

Answer 5

你不能拥有一个set的set，因为set的元素需要是可哈希的。但是你可以创建一个frozenset的set。

{frozenset(n) for val in periodic_gs.values() for n in val.nodes()}

- John La Rooy