if we want to construct a list from a set, we can do
[k for k in set] This is O(n) operation, meanwhile:
dict.keys() is O(1) according to https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
Thus, as far as I know, dict is using set as its keys underlying data structure, is list(set) O(1)? And how is this implemented?
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.
Hmm, no not really. The opposite way around is a closer analogy: in the implementation, set is like a dict with all null values. The dict came first in Python, and set did not appear until Python 2.2 (July 2000) - see PEP 218.
Also worth mentioning that dict.keys() is O(1) since Python 3. In Python 2 it's O(n) and you should use dict.viewkeys() for the keys "view" (set-like interface).
is
list(set)O(1)?
No, it's O(n) - just the same as the list comprehension.
And how is this implemented?
Sets support the iterator protocol.
list(set)? Note thatdict.keys()returns a view, which is neither a list nor a set.dict.keys()is O(n) in Python 2.