Почему два одинаковых списка имеют разный объем памяти?

155

Я создал два списка l1и l2, но каждый со своим методом создания:

import sys

l1 = [None] * 10
l2 = [None for _ in range(10)]

print('Size of l1 =', sys.getsizeof(l1))
print('Size of l2 =', sys.getsizeof(l2))

Но результат меня удивил:

Size of l1 = 144
Size of l2 = 192

Список, созданный с пониманием списка, имеет больший размер в памяти, но оба списка в Python идентичны.

Это почему? Это какая-то внутренняя часть CPython или какое-то другое объяснение?

Андрей Кесели
источник
2
Возможно, оператор повторения вызовет некоторую функцию, которая точно измеряет размер базового массива. Обратите внимание, что 144 == sys.getsizeof([]) + 8*10)где 8 - размер указателя.
juanpa.arrivillaga
1
Обратите внимание, что если вы измените 10на 11, [None] * 11список будет иметь размер 152, но понимание списка по-прежнему будет иметь размер 192. Ранее связанный вопрос не является точным дубликатом, но он важен для понимания, почему это происходит.
Патрик Хау

Ответы:

162

Когда вы пишете [None] * 10, Python знает, что ему потребуется список из ровно 10 объектов, поэтому он выделяет именно это.

Когда вы используете понимание списка, Python не знает, сколько ему понадобится. Таким образом, список постепенно увеличивается по мере добавления элементов. Для каждого перераспределения он выделяет больше места, чем необходимо, так что ему не нужно перераспределять для каждого элемента. Результирующий список, вероятно, будет несколько больше, чем нужно.

Вы можете увидеть это поведение при сравнении списков, созданных с одинаковыми размерами:

>>> sys.getsizeof([None]*15)
184
>>> sys.getsizeof([None]*16)
192
>>> sys.getsizeof([None for _ in range(15)])
192
>>> sys.getsizeof([None for _ in range(16)])
192
>>> sys.getsizeof([None for _ in range(17)])
264

Вы можете видеть, что первый метод выделяет только то, что нужно, а второй периодически увеличивается. В этом примере он выделяет достаточно для 16 элементов, и пришлось перераспределить при достижении 17-го.

interjay
источник
1
Да, это имеет смысл. Вероятно, лучше создавать списки, *когда я знаю размер впереди.
Андрей Кеселый
27
@AndrejKesely Используйте только [x] * nс неизменным xв вашем списке. Результирующий список будет содержать ссылки на идентичный объект.
schwobaseggl
5
@schwobaseggl хорошо, это может быть то, что вы хотите, но это хорошо понимать.
juanpa.arrivillaga
19
@ juanpa.arrivillaga Правда, это может быть. Но обычно это не так, и особенно ТАК полон плакатов,
задающихся
50

Как уже отмечалось в этом вопросе, понимание списка используется list.appendпод капотом, поэтому он вызовет метод list-resize, который перераспределяется.

Чтобы продемонстрировать это себе, вы можете использовать disdisasembler:

>>> code = compile('[x for x in iterable]', '', 'eval')
>>> import dis
>>> dis.dis(code)
  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x10560b810, file "", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (iterable)
              8 GET_ITER
             10 CALL_FUNCTION            1
             12 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x10560b810, file "", line 1>:
  1           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 8 (to 14)
              6 STORE_FAST               1 (x)
              8 LOAD_FAST                1 (x)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            4
        >>   14 RETURN_VALUE
>>>

Обратите внимание на LIST_APPENDкод операции при разборке <listcomp>объекта кода. Из документов :

LIST_APPEND (я)

Звонки list.append(TOS[-i], TOS). Используется для реализации списочных представлений.

Теперь, для операции повторения списка, у нас есть подсказка о том, что происходит, если мы рассмотрим:

>>> import sys
>>> sys.getsizeof([])
64
>>> 8*10
80
>>> 64 + 80
144
>>> sys.getsizeof([None]*10)
144

Так что, похоже, можно точно выделить размер. Глядя на исходный код , мы видим, что именно это и происходит:

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
    if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);

А именно здесь size = Py_SIZE(a) * n;. Остальные функции просто заполняют массив.

juanpa.arrivillaga
источник
«Как отмечено в этом вопросе, для понимания списка используется list.append изнутри». Я думаю, что точнее будет сказать, что он использует .extend().
накопление
@ Накопление почему ты так веришь?
juanpa.arrivillaga
Потому что он не добавляет элементы один за другим. Когда вы добавляете элементы в список, вы действительно создаете новый список с новым распределением памяти и помещаете список в это новое распределение памяти. С другой стороны, списочные представления помещают большинство новых элементов в память, которая уже была выделена, и, когда им не хватает выделенной памяти, они выделяют еще один фрагмент памяти, которого недостаточно для нового элемента.
накопление
7
@ Накопление Это неверно. list.appendявляется амортизированной операцией с постоянным временем, потому что при изменении размера списка он перераспределяется. Поэтому не каждая операция добавления приводит к появлению вновь выделенного массива. В любом случае вопрос о том , что я связан показывает вам в исходном коде , что на самом деле, списочные сделать использование list.append,. LIST_APPEND
Через
3

Ни один из них не является блоком памяти, но это не предопределенный размер. В дополнение к этому в массиве есть некоторый дополнительный интервал между элементами массива. Вы можете увидеть это сами, запустив:

for ele in l2:
    print(sys.getsizeof(ele))

>>>>16
16
16
16
16
16
16
16
16
16

Который не составляет размер l2, а скорее меньше.

print(sys.getsizeof([None]))
72

И это намного больше, чем одна десятая размера l1.

Ваши номера должны отличаться в зависимости от деталей вашей операционной системы и сведений о текущем использовании памяти в вашей операционной системе. Размер [None] никогда не может быть больше доступной смежной памяти, в которой переменная установлена ​​для хранения, и переменная может быть перемещена, если впоследствии она динамически распределяется, чтобы быть больше.

StevenJD
источник
1
Noneна самом деле не хранится в базовом массиве, хранится только PyObjectуказатель (8 байт). Все объекты Python расположены в куче. Noneявляется одноэлементным, поэтому наличие списка с множеством нон просто создаст массив указателей PyObject на один и тот же Noneобъект в куче (и не будет использовать дополнительную память в процессе для каждого дополнительного None). Я не уверен, что вы подразумеваете под "Ни один не имеет заранее заданный размер", но это не звучит правильно. Наконец, ваш цикл с getsizeofкаждым элементом не демонстрирует то, что вы думаете, что он демонстрирует.
juanpa.arrivillaga
Если, как вы говорите, значение true, размер [Нет] * 10 должен совпадать с размером [Нет]. Но ясно, что это не так - было добавлено дополнительное хранилище. Фактически, размер [Нет], повторенный десять раз (160), также меньше, чем размер [Нет], умноженный на десять. Как вы указали, очевидно, что размер указателя на [None] меньше размера самого [None] (16 байт, а не 72 байт). Однако 160 + 32 - это 192. Я не думаю, что предыдущий ответ также решает проблему полностью. Понятно, что выделяется некоторый дополнительный небольшой объем памяти (возможно, зависящий от состояния машины).
StevenJD
«Если, как вы говорите, правда, размер [Нет] * 10 должен быть таким же, как размер [Нет]», что я могу сказать, что это может означать? Опять же, вы, кажется, концентрируетесь на том факте, что базовый буфер перераспределен, или что размер списка включает в себя больше, чем размер базового буфера (это, конечно, так), но это не главное этот вопрос. Опять же, использование вами gestsizeofкаждого eleиз l2них вводит в заблуждение, поскольку getsizeof(l2) не учитывает размер элементов внутри контейнера .
juanpa.arrivillaga
Чтобы доказать себе это последнее утверждение, сделайте l1 = [None]; l2 = [None]*100; l3 = [l2]тогда print(sys.getsizeof(l1), sys.getsizeof(l2), sys.getsizeof(l3)). вы получите результат , как: 72 864 72. То есть, соответственно, 64 + 1*8, 64 + 100*8, и 64 + 1*8, опять же , предполагая систему 64 - битной с 8 байт размера указателя.
juanpa.arrivillaga
1
Как я уже говорил, sys.getsizeof* не учитывает размер элементов в контейнере. Из документов : « Учитывается только потребление памяти, непосредственно относящееся к объекту, а не потребление памяти объектами, на которые он ссылается ... См. Рецепт рекурсивного sizeof для примера рекурсивного использования getsizeof () для определения размера контейнеров и все их содержимое. "
juanpa.arrivillaga