set和frozenset在实现上的差异

Question

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

Answer 1

您可以从生成器表达式或其他可迭代实例化冻结集.在完成实例化之前,它不是不可变的.

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

Answer 2

集合和frozensets以与哈希表相同的方式实现.(为什么他们还需要实现它们的元素__hash__呢？)事实上,如果你看一下Objects/setobject.c,它们几乎可以共享所有代码.这意味着只要哈希冲突不会失控,查找和删除就是O(1)并且插入是分摊的O(1).

创建冻结集的常用方法是使用其他可迭代函数对其进行初始化.正如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

至于你的第一个问题，我实际上没有检查来源，但似乎可以安全地假设集合需要包含可哈希类型的对象，它是使用哈希表实现的，并且它的查找时间是，因此，O(1)。

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

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