Почему объединение потребляет больше памяти, если аргумент является набором?

Question

Я озадачен этим поведением выделения памяти set с:

>>> set(range(1000)).__sizeof__() 
32968 
>>> set(range(1000)).union(range(1000)).__sizeof__()  # expected, set doesn't change 
32968 
>>> set(range(1000)).union(list(range(1000))).__sizeof__() #expected, set doesn't change 
32968 
>>> set(range(1000)).union(set(range(1000))).__sizeof__() # not expected 
65736 

Почему используя set в качестве аргумента двойников объем памяти, используемый в результате set? Результат в обоих случаях идентична оригинальной set:

>>> set(range(1000)) == set(range(1000)).union(range(1000)) == set(range(1000)).union(set(range(1000))) 
True 

Обратите внимание, что то же самое происходит с помощью обычного итератора:

>>> set(range(1000)).union(iter(list(range(1000)))).__sizeof__() 
32968 

И с помощью метода update:

>>> a.update(range(1000)) 
>>> a.__sizeof__() 
32968 
>>> a.update(set(range(1000))) 
>>> a.__sizeof__() 
65736 

Сначала я подумал, что это происходит потому, что когда вызывается union, он видит, что размер другого set - 1000 и, таким образом, решает выделить достаточное количество памяти для всех элементов как set s, а затем использует только часть этой памяти, в то время как в итерационном случае это просто итераторы над ней и добавляет элементы по одному (что doesn 't потребляет больше памяти, поскольку все элементы уже находятся в set).

Но range также является последовательностью, а также list в первом примере.

>>> len(range(1000)) 
1000 
>>> range(1000)[100] 
100 

Так почему это не происходит с range и list, но только с set? Есть ли какое-либо дизайнерское решение за этим или это ошибка?

---

Протестировано на python 2.7.3 и python 3.2.3 на Linux 64 бит.

Answer 1

В Python 2.7.3, set.union() делегаты функции C, называемой set_update_internal(). Последний использует несколько разных реализаций в зависимости от типа аргумента Python. Эта множественность реализаций объясняет разницу в поведении между тестами, которые вы провели.

Реализация, которая используется, когда аргумент является set делает следующее предположение документированного в коде:

/* Do one big resize at the start, rather than 
* incrementally resizing as we insert new keys. Expect 
* that there will be no (or few) overlapping keys. 
*/ 

Очевидно, что предположение о каких-либо (или несколько) перекрывающихся ключей неверно в вашем конкретном случае. Это то, что приводит к окончательной памяти памяти set.

Я не уверен, что я бы назвал это ошибкой. Разработчик set выбрал то, что для меня выглядит как разумный компромисс, и вы просто оказались на неправильной стороне этого компромисса.

Достоинство компромисса в том, что во многих случаях результаты предварительного распределения в более высокой производительности:

In [20]: rhs = list(range(1000)) 

In [21]: %timeit set().union(rhs) 
10000 loops, best of 3: 30 us per loop 

In [22]: rhs = set(range(1000)) 

In [23]: %timeit set().union(rhs) 
100000 loops, best of 3: 14 us per loop 

Здесь версия set в два раза быстрее, по-видимому, потому что не раз перераспределить память как это добавление элементов из rhs.

Если общее назначение является разрывом сделки, существует множество способов обойти его, некоторые из которых вы уже обнаружили.