集和实施中的冻结集差异

Question

我在这个链接上检查了set是可变的https://docs.python.org/3/library/stdtypes.html#frozenset，而frozenset是不可变的，因此是散列的。那么set是如何在python中实现的，元素的查找时间是多少？实际上我有一个元组列表[（1,2），（3,4），（2,1）]，其中元组中的每个条目都是一个id，我想从这个列表中创建一个set/frozenset。在这种情况下，集合应该包含（1,2,3,4）作为元素。我可以使用frozenset从元组列表中一个接一个地将元素插入其中，还是只能使用set？

Answer 1

至于您的第一个问题，我实际上还没有检查源代码，但从集合需要包含哈希类型的对象这一事实出发，可以肯定地假设集合是使用哈希表实现的，因此它的查找时间是O（1）。

至于第二个问题，您不能一个接一个地将元素插入到frozenset中（显然，因为它是不可变的），但是没有理由使用集合；只需从组成值的列表（或其他可iterable）中构造它，例如：

data = [(1, 2), (3, 4), (2, 1)]
result = frozenset(reduce(list.__add__, [list(x) for x in data], []))

Answer 2

集合和frozensets的实现方式与哈希表相同。（否则，它们为什么需要它们的元素来实现__hash__？）事实上，如果你看^{}，它们几乎共享所有的代码。这意味着，只要哈希冲突不失控，查找和删除是O（1），插入是O（1）分期偿还。

创建frozenset的通常方法是使用其他iterable初始化它。正如gnibbler所建议的，这里最适合的可能是itertools.chain.from_iterable：

>>> L = [(1,2),(3,4),(2,1)]
>>> from itertools import chain
>>> frozenset(chain.from_iterable(L))
frozenset([1, 2, 3, 4])

Answer 3

可以从生成器表达式或其他iterable实例化frozenset。它在完成实例化之前是不可变的。

>>> L = [(1,2),(3,4),(2,1)]
>>> from itertools import chain
>>> frozenset(chain.from_iterable(L))
frozenset([1, 2, 3, 4])

Python3.3还有一个优化，当用作in运算符的右侧时，它可以将{1、2、3、4}等集合文本转换为预计算的frozensets。