如果我们想从一个集合构造一个列表,我们可以这样做
[k for k in set]
这是 O(n) 操作,同时:
dict.keys()
是 O(1) 根据 https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
因此,据我所知,dict是使用set作为底层数据结构的key,是list(set) O(1)吗?这是如何实现的?
a = set(range(n))
s = list(a) # is this operation O(1)?
请您参考如下方法:
Thus, as far as I know, dict is using set as its keys underlying data structure.
嗯,不,不是真的。相反的方法是一个更接近的类比:在实现中,set 就像一个包含所有空值的 dict。 dict 首先出现在 Python 中,set 直到 Python 2.2(2000 年 7 月)才出现 - 参见 PEP 218 .
另外值得一提的是 dict.keys() 自 Python 3 以来是 O(1)。在 Python 2 中它是 O(n),你应该使用 dict.viewkeys() 用于键“ View ”(类似设置的界面)。
is
list(set)O(1)?
不,它是 O(n) - 与列表理解相同。
And how is this implemented?
设置支持the iterator protocol .
