Сложность конвертации набора в фрозенсет в Python

Question

Какова вычислительная сложность "замораживания" набора в Python?

Например, вторая строка в

a = {1,2,3}
b = frozenset(a)

требуется время O(n)? Или это просто "представление", созданное в постоянное время?

Answer 1

b это не вид a, Вы можете проверить это через id:

a = {1, 2, 3}
b = a

id(a) == id(b)  # True

b = frozenset({1, 2, 3})

id(a) == id(b)  # False

Отсюда и изменение b не будет отражено в a, Вы можете, конечно, проверить это самостоятельно. поскольку frozenset принимает в качестве аргумента итерацию, она должна проходить итерацию по каждому аргументу. Это O (n) процесс.

Кроме того, в этом нет ничего особенного frozenset даже создавая set из set имеет O (n) временную сложность:

for i in [10**5, 10**6, 10**7]:
    a = set(range(i))
    %timeit set(a)

100 loops, best of 3: 3.33 ms per loop
10 loops, best of 3: 30.2 ms per loop
1 loop, best of 3: 421 ms per loop