list () использует немного больше памяти, чем понимание списка

79

Итак, я играл с listобъектами и обнаружил небольшую странную вещь, которая, если listсоздается с list()ее помощью, использует больше памяти, чем понимание списка? Я использую Python 3.5.2

In [1]: import sys
In [2]: a = list(range(100))
In [3]: sys.getsizeof(a)
Out[3]: 1008
In [4]: b = [i for i in range(100)]
In [5]: sys.getsizeof(b)
Out[5]: 912
In [6]: type(a) == type(b)
Out[6]: True
In [7]: a == b
Out[7]: True
In [8]: sys.getsizeof(list(b))
Out[8]: 1008

Из документов :

Списки могут быть составлены несколькими способами:

  • Использование пары квадратных скобок для обозначения пустого списка: []
  • Используя квадратные скобки, разделяя элементы запятыми: [a],[a, b, c]
  • Используя понимание списка: [x for x in iterable]
  • Использование конструктора типа: list()илиlist(iterable)

Но похоже, что при list()его использовании требуется больше памяти.

И чем listбольше, тем разрыв увеличивается.

Разница в памяти

Почему так происходит?

ОБНОВЛЕНИЕ # 1

Тест с Python 3.6.0b2:

Python 3.6.0b2 (default, Oct 11 2016, 11:52:53) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(range(100)))
1008
>>> sys.getsizeof([i for i in range(100)])
912

ОБНОВЛЕНИЕ # 2

Тест с Python 2.7.12:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(xrange(100)))
1016
>>> sys.getsizeof([i for i in xrange(100)])
920
vishes_shell
источник
3
Это очень интересный вопрос. Я могу воспроизвести это явление в Python 3.4.3. Еще интереснее: на Python 2.7.5 sys.getsizeof(list(range(100)))это 1016, getsizeof(range(100))872 и getsizeof([i for i in range(100)])920. Все имеют тип list.
Свен Фестерсен,
Интересно то, что эта разница есть и в Python 2.7.10 (хотя фактические числа отличаются от Python 3). Также есть в 3.5 и 3.6b.
cdarke
Я получаю те же числа для Python 2.7.6, что и @SvenFestersen, также при использовании xrange.
RemcoGerlich
2
Здесь есть возможное объяснение: stackoverflow.com/questions/7247298/size-of-list-in-memory . Если один из методов создает список с помощью append(), может произойти перераспределение памяти. Я думаю, единственный способ прояснить это - взглянуть на исходники Python.
Свен Фестерсен,
Только на 10% больше (нигде этого не скажешь). Я бы перефразировал название на «немного больше».
smci

Ответы:

61

Я думаю, вы видите шаблоны избыточного распределения, это образец из источника :


Распечатав размеры образов списков длиной 0-88, вы увидите совпадения с образцом:

# create comprehensions for sizes 0-88
comprehensions = [sys.getsizeof([1 for _ in range(l)]) for l in range(90)]

# only take those that resulted in growth compared to previous length
steps = zip(comprehensions, comprehensions[1:])
growths = [x for x in list(enumerate(steps)) if x[1][0] != x[1][1]]

# print the results:
for growth in growths:
    print(growth)

Результаты (формат (list length, (old total size, new total size))):

(0, (64, 96)) 
(4, (96, 128))
(8, (128, 192))
(16, (192, 264))
(25, (264, 344))
(35, (344, 432))
(46, (432, 528))
(58, (528, 640))
(72, (640, 768))
(88, (768, 912))

Избыточное выделение выполняется из соображений производительности, что позволяет спискам расти без выделения дополнительной памяти с каждым ростом (лучшая амортизированная производительность).

Вероятная причина разницы с использованием понимания списка состоит в том, что понимание списка не может детерминированно вычислить размер сгенерированного списка, но list()может. Это означает, что понимания будут постоянно увеличивать список по мере его заполнения с использованием избыточного выделения, пока он не заполнится окончательно.

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

list()однако, может добавить некоторый буфер независимо от размера списка, поскольку он заранее знает окончательный размер списка.


Еще одно подтверждающее свидетельство, также полученное из источника, заключается в том, что мы видим, как вызываются спискиLIST_APPEND , которые указывают на использование list.resize, что, в свою очередь, указывает на использование буфера предварительного распределения, не зная, сколько из него будет заполнено. Это согласуется с наблюдаемым вами поведением.


В заключение, list()предварительно выделим больше узлов в зависимости от размера списка.

>>> sys.getsizeof(list([1,2,3]))
60
>>> sys.getsizeof(list([1,2,3,4]))
64

Понимание списка не знает размер списка, поэтому он использует операции добавления по мере его роста, истощая буфер предварительного распределения:

# one item before filling pre-allocation buffer completely
>>> sys.getsizeof([i for i in [1,2,3]]) 
52
# fills pre-allocation buffer completely
# note that size did not change, we still have buffered unused nodes
>>> sys.getsizeof([i for i in [1,2,3,4]]) 
52
# grows pre-allocation buffer
>>> sys.getsizeof([i for i in [1,2,3,4,5]])
68
Реут Шарабани
источник
4
Но почему перераспределение может произойти с одним, а не с другим?
cdarke
Это конкретно от list.resize. Я не эксперт в навигации по источнику, но если один вызывает изменение размера, а другой нет - это может объяснить разницу.
Реут Шарабани
6
Python 3.5.2 здесь. Попробуйте печатать списки размеров от 0 до 35 в цикле. Список вижу 64, 96, 104, 112, 120, 128, 136, 144, 160, 192, 200, 208, 216, 224, 232, 240, 256, 264, 272, 280, 288, 296, 304, 312, 328, 336, 344, 352, 360, 368, 376, 384, 400, 408, 416и для понимания 64, 96, 96, 96, 96, 128, 128, 128, 128, 192, 192, 192, 192, 192, 192, 192, 192, 264, 264, 264, 264, 264, 264, 264, 264, 264, 344, 344, 344, 344, 344, 344, 344, 344, 344. Я бы исключил это понимание того, кто, кажется, заранее выделяет память как алгоритм, который использует больше оперативной памяти для определенных размеров.
tavo
Я ожидал того же. Я скоро смогу изучить это подробнее. Хорошие комментарии.
Реут Шарабани
4
фактически list()детерминированно определяет размер списка, чего не может сделать понимание списка. Это говорит о том, что понимание списка не всегда «запускает» «последний» рост списка. Может иметь смысл.
Реут Шарабани
30

Спасибо всем за то, что помогли мне понять этот потрясающий Python.

Я не хочу делать такой массовый вопрос (вот почему я публикую ответ), просто хочу показать и поделиться своими мыслями.

Как правильно заметил @ReutSharabani : «list () детерминистически определяет размер списка». Вы можете увидеть это на графике.

график размеров

Когда вы appendили используете понимание списка, у вас всегда есть какие-то границы, которые расширяются, когда вы достигаете определенной точки. И с list()вами границы почти такие же, но они плывут.

ОБНОВИТЬ

Итак, спасибо @ReutSharabani , @tavo , @SvenFestersen

Подводить итоги: list() предварительное выделение памяти зависит от размера списка, понимание списка не может этого сделать (он запрашивает больше памяти, когда это необходимо, например .append()). Вот почему list()храните больше памяти.

Еще один график, показывающий list()предварительное выделение памяти. Таким образом, зеленая линия показывает list(range(830))добавление элемента за элементом и некоторое время память не изменяется.

list () предварительно выделяет память

ОБНОВЛЕНИЕ 2

Как отметил @Barmar в комментариях ниже, я list()должен быстрее, чем понимание списка, поэтому я работал timeit()с number=1000длиной listот 4**0до, 4**10и результаты

измерения времени

vishes_shell
источник
1
Ответ, почему красная линия выше синей, заключается в том, что когда listконструктор может определить размер нового списка из своего аргумента, он все равно будет предварительно выделять такое же количество места, как если бы последний элемент только что попал туда и для него не было достаточно места. По крайней мере, для меня это имеет смысл.
tavo
@tavo мне кажется то же самое, через какой-то момент я хочу показать это на графике.
vishes_shell
2
Таким образом, хотя понимание списков использует меньше памяти, оно, вероятно, значительно медленнее из-за всех происходящих изменений размеров. Им часто приходится копировать основу списка в новую область памяти.
Barmar
@Barmar на самом деле я могу провести некоторые измерения времени с rangeобъектом (это может быть весело).
vishes_shell
И это сделает ваши графики еще красивее. :)
Бармар