python - python中的list(set)操作是O(1)吗？

Question

如果我们想从一个集合构造一个列表，我们可以这样做

[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)?

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