我在此链接上检查了 set 是可变的https://docs.python.org/3/library/stdtypes.html#frozenset而frozenset 是不可变的，因此是可散列的。那么在python中set是如何实现的，元素查找时间是多少呢？实际上我有一个元组列表 [(1,2),(3,4),(2,1)] ，其中元组中的每个条目都是一个 id，我想从这个列表中创建一个集合/冻结集。在这种情况下，集合应包含 (1,2,3,4) 作为元素。我可以使用frozenset从元组列表中一个一个地插入元素还是只能使用一个集合？
问问题
9403 次
3 回答
7
您可以从生成器表达式或其他可迭代对象中实例化frozenset。在完成实例化之前，它不是不可变的。
>>> L = [(1,2),(3,4),(2,1)]
>>> from itertools import chain
>>> frozenset(chain.from_iterable(L))
frozenset([1, 2, 3, 4])
Python3.3 也有一个优化，当用作运算符的右侧时，将诸如 {1, 2, 3, 4} 之类的集合文字转换为预先计算的冻结集in。
于 2013-07-15T03:31:59.170 回答
5
Sets 和 freezesets 的实现方式与哈希表相同。（否则他们为什么需要他们的元素来实现__hash__？）事实上，如果你看一下Objects/setobject.c，他们几乎共享所有的代码。这意味着只要哈希冲突没有失控，查找和删除是 O(1)，插入是分期 O(1)。
创建frozenset 的常用方法是用其他一些可迭代对象对其进行初始化。正如 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])
于 2013-07-15T03:43:28.337 回答
-2
至于你的第一个问题，我实际上并没有检查源，但从集合需要包含可散列类型的对象这一事实来看，它是使用散列表实现的，并且它的查找时间似乎是安全的，因此，O(1)。
至于您的第二个问题，您不能将元素一个frozenset一个地插入（显然，因为它是不可变的），但是没有理由使用集合来代替；只需从组成值的列表（或其他可迭代）中构造它，例如：
data = [(1, 2), (3, 4), (2, 1)]
result = frozenset(reduce(list.__add__, [list(x) for x in data], []))
于 2013-07-15T03:31:57.977 回答