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

Question

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

так я играл с 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

С docs:

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

используя пару квадратных скобок для обозначения пустого списка:[]

используя квадратные скобки, отделяя детали с запятые: [a],[a, b, c]

используя понимание списка:[x for x in iterable]

С помощью конструктора типа: list() или list(iterable)

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

и как много list больше этот разрыв увеличивается.

почему это происходит?

обновление #1

2 76

python python-internals list list-comprehension cpython

2 ответа:

спасибо всем, кто помог мне понять, что удивительный питон.

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

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

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

обновление

спасибо @ReutSharabani, @tavo, @SvenFestersen

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

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

обновление 2

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

27

Reut Sharabani · Accepted Answer · 2017-12-04 02:31:56

Я думаю, что вы видите чрезмерное распределение паттернов это пример из источника:
/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
печать размеров списка понимания длин 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