памяти: создание одной большой набор против слияния много небольших наборов

Question

Я использовал волшебную функцию %memit для измерения использования памяти:

In [1]: %memit n = pow(10, 7); range(n) 
peak memory: 568 MiB, increment: 272 MiB 

In [2]: %memit n = pow(10, 7); set(xrange(n)) 
peak memory: 824 MiB, increment: 447 MiB 

ОК, так что, как представляется, промежуточный этап, на котором xrange(n) конкретизируется в полный список , Но что, если я сокращу свой список на 10 подписок и объединил их один за другим? Это будет более эффективным с точки зрения памяти, верно?

In [3]: %memit n = pow(10, 7); reduce(set.union, (set(xrange(p, n, 10)) for p in range(10))) 
peak memory: 1260 MiB, increment: 897 MiB 

Ну, это не так, как ожидалось. Почему подход reduce потребляет больше памяти, чем set(xrange(n))?

Answer 1

Есть много неправильных представлений, которые необходимо очистить. Прежде всего, xrangeне превращен в список, прежде чем он превращается в set в set(xrange(n))!

пик память для reduce подхода исходит из того, что set.union возвращает значение нового, который представляет собой объединение 2 наборов результатов. И reduce внутренне хранит дополнительное значение, accum_value. Так что на последней итерации этого for цикла:

accum_value = function(accum_value, x) 

accum_value, который входит в функции содержит 90% 10⁷ элементов, x содержит 10% 10⁷ элементов, но возвращаемое значение будет нужно пространство для всех 10⁷ элементов , Пространство для всех этих нужно резервировать одновременно. Только после того, как возвращается function, выдается память для старых accum_value и x.

---

Однако это еще не конец. Память пиков показывает, сколько памяти было необходимо в процесс, но не сколько используется после операция завершена, если набор все еще существует.

Таким образом, другой тест необходим:

In [1]: %memit n = pow(10, 7); result = set(xrange(n)); 
peak memory: 522.22 MiB, increment: 498.93 MiB 
In [2]: %memit 42 
peak memory: 513.83 MiB, increment: 0.12 MiB 
In [3]: import sys 
In [4]: sys.getsizeof(result) 
Out[4]: 268435688 

и

In [1]: %memit n = pow(10, 7); result = reduce(set.union, (set(xrange(p, n, 10)) for p in range(10))); 
peak memory: 1063.20 MiB, increment: 1039.71 MiB 
In [2]: %memit 42 
peak memory: 779.77 MiB, increment: 0.00 MiB 
In [3]: import sys  
In [4]: sys.getsizeof(result) 
Out[4]: 536871144 
In [5]: 536871144.0/268435688 
Out[5]: 1.9999991357333977 

Так использование памяти для reduceкапли в 778 МиБ после исполнения; однако это еще больше, чем для более простого случая построения множества. И, как вы можете видеть, set(xrange(n)) не нуждается в большой внутренней памяти, так как использование памяти падает всего на 9 миллионов после того, как набор был сконструирован.

В частности, не только приближается подход reduce; итоговый набор потребляет вдвое больше памяти. Это связано с тем, что набор поддерживается хеш-таблицей, и он становится более крупным, когда считается, что он имеет слишком много конфликтов. Вы столкнулись с патологическим поведением, когда множество одинаковых значений приводит к тому, что в два раза больше памяти, чем в другом.

Answer 2

Per the docs, reduce примерно эквивалентно:

def reduce(function, iterable, initializer=None): 
    it = iter(iterable) 
    if initializer is None: 
     try: 
      initializer = next(it) 
     except StopIteration: 
      raise TypeError('reduce() of empty sequence with no initial value') 
    accum_value = initializer 
    for x in it: 
     accum_value = function(accum_value, x) 
    return accum_value 

Итерация над iterable, (set(xrange(p, n, 10)) for p in range(10)), требует около 447 MiB. Вы можете подумать, что поскольку этот итератором является выражением генератора вы будете экономить память, но целые числа saved in an internal free list:

«Для скорости», Python поддерживает внутренний список свободный для целых объектов. К сожалению, этот свободный список является бессмертным и неограниченным по размеру.

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

Возвращаемое значение accum_value также требует около 447 миллионов экземпляров. Вместе с тем для вызова reduce требуется примерно 447 + 447 = 894 Мбайт.