Сложность преобразования набора в фрозенсет в Python - PullRequest
Новая
       48

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

0 голосов
/ 01 октября 2018

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

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

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

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

1 Ответ

0 голосов
/ 02 октября 2018

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