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

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

>>> 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, но потом он использует только часть этой памяти, тогда как в случае итератора он просто выполняет итераторы над ним и добавляет элементы один за другим (что не потребляет больше памяти, поскольку все элементы уже находятся в set).

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

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

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

Протестировано на python 2.7.3 и python 3.2.3 на 64-разрядном Linux.

Ответы

Ответ 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.

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