Почему кортежи занимают меньше места в памяти, чем списки?

A tupleзанимает меньше места в памяти в Python:

>>> a = (1,2,3)
>>> a.__sizeof__()
48

тогда как lists занимает больше места в памяти:

>>> b = [1,2,3]
>>> b.__sizeof__()
64

Что происходит внутри управления памятью Python?

Я предполагаю, что вы используете CPython и 64-битную версию (я получил те же результаты на моем 64-битном CPython 2.7). Могут быть различия в других реализациях Python или если у вас 32-битный Python.

Независимо от реализации, lists имеют переменный размер, а tuples - фиксированный.

Таким образом, tuples может хранить элементы непосредственно внутри структуры, с другой стороны, спискам нужен уровень косвенности (он хранит указатель на элементы). Этот уровень косвенного обращения представляет собой указатель, в 64-битных системах это 64-битный, следовательно, 8 байт.

Но есть еще одна вещь, которую можно listсделать: они перераспределяют ресурсы. В противном случае list.appendэто была бы O(n)операция всегда - чтобы амортизировать O(1)(намного быстрее !!!), он перераспределяет. Но теперь он должен отслеживать выделенный размер и заполненный размер ( tupleнужно хранить только один размер, потому что выделенный и заполненный размер всегда идентичны). Это означает, что каждый список должен хранить другой «размер», который в 64-битных системах представляет собой 64-битное целое число, опять же 8 байтов.

Таким образом, lists требуется как минимум на 16 байт памяти больше, чем tuples. Почему я сказал «хотя бы»? Из-за перераспределения. Избыточное выделение означает, что он выделяет больше места, чем необходимо. Однако величина перераспределения зависит от того, «как» вы создаете список и историю добавления / удаления:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers re-allocation (with over-allocation), because the original list is full
>>> l.__sizeof__()
96

>>> l = []
>>> l.__sizeof__()
40
>>> l.append(1)  # re-allocation with over-allocation
>>> l.__sizeof__()
72
>>> l.append(2)  # no re-alloc
>>> l.append(3)  # no re-alloc
>>> l.__sizeof__()
72
>>> l.append(4)  # still has room, so no over-allocation needed (yet)
>>> l.__sizeof__()
72

Изображений

Я решил создать несколько изображений, чтобы дополнить объяснение выше. Может быть, это полезно

Вот как он (схематично) хранится в памяти в вашем примере. Я выделил различия красными (произвольными) циклами:

На самом деле это всего лишь приближение, потому что intобъекты также являются объектами Python, а CPython даже повторно использует небольшие целые числа, поэтому, вероятно, более точное представление (хотя и не столь читаемое) объектов в памяти будет:

Полезные ссылки:

• tuple struct в репозитории CPython для Python 2.7
• list struct в репозитории CPython для Python 2.7
• int struct в репозитории CPython для Python 2.7

Обратите внимание, что на __sizeof__самом деле не возвращается "правильный" размер! Он возвращает только размер сохраненных значений. Однако при использовании sys.getsizeofрезультат будет другим:

>>> import sys
>>> l = [1,2,3]
>>> t = (1, 2, 3)
>>> sys.getsizeof(l)
88
>>> sys.getsizeof(t)
72

Есть 24 «лишних» байта. Это настоящие накладные расходы сборщика мусора, которые не учитываются в __sizeof__методе. Это потому, что обычно вы не должны использовать магические методы напрямую - используйте функции, которые знают, как их обрабатывать, в этом случае: sys.getsizeof(что фактически добавляет накладные расходы GC к значению, возвращаемому из __sizeof__).

Я углублюсь в кодовую базу CPython, чтобы мы могли увидеть, как на самом деле рассчитываются размеры. Не в вашем конкретном примере , не более-распределения были выполнены, поэтому я не буду касаться что .

Я собираюсь использовать здесь 64-битные значения, как и вы.

Размер lists рассчитывается по следующей функции list_sizeof:

static PyObject *
list_sizeof(PyListObject *self)
{
    Py_ssize_t res;

    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
    return PyInt_FromSsize_t(res);
}

Вот Py_TYPE(self)макрос , который захватывает ob_typeиз self(возвращение PyList_Type) в то время как _PyObject_SIZEеще один макрос , который захватывает tp_basicsizeот этого типа. tp_basicsizeвычисляется как sizeof(PyListObject)где PyListObjectнаходится структура экземпляра.

В PyListObjectструктуре есть три поля:

PyObject_VAR_HEAD     # 24 bytes 
PyObject **ob_item;   #  8 bytes
Py_ssize_t allocated; #  8 bytes

у них есть комментарии (которые я обрезал), объясняющие, что они собой представляют, перейдите по ссылке выше, чтобы прочитать их. PyObject_VAR_HEADрасширяется в три 8-байтовых поля ( ob_refcount, ob_typeи ob_size), так что 24байтовый вклад.

Итак, resпока:

sizeof(PyListObject) + self->allocated * sizeof(void*)

или:

40 + self->allocated * sizeof(void*)

Если в экземпляре списка есть выделенные элементы. вторая часть подсчитывает их вклад. self->allocated, как следует из названия, содержит количество выделенных элементов.

Без каких-либо элементов размер списков рассчитывается следующим образом:

>>> [].__sizeof__()
40

т.е. размер структуры экземпляра.

tupleобъекты не определяют tuple_sizeofфункцию. Вместо этого они используют object_sizeofдля расчета своего размера:

static PyObject *
object_sizeof(PyObject *self, PyObject *args)
{
    Py_ssize_t res, isize;

    res = 0;
    isize = self->ob_type->tp_itemsize;
    if (isize > 0)
        res = Py_SIZE(self) * isize;
    res += self->ob_type->tp_basicsize;

    return PyInt_FromSsize_t(res);
}

Это, как и lists, захватывает tp_basicsizeи, если объект имеет ненулевое tp_itemsizeзначение (что означает, что у него есть экземпляры переменной длины), он умножает количество элементов в кортеже (которые он получает через Py_SIZE) tp_itemsize.

tp_basicsizeснова использует, sizeof(PyTupleObject)где PyTupleObjectструктура содержит :

PyObject_VAR_HEAD       # 24 bytes 
PyObject *ob_item[1];   # 8  bytes

Итак, без каких-либо элементов (то есть Py_SIZEвозвратов 0) размер пустых кортежей равен sizeof(PyTupleObject):

>>> ().__sizeof__()
24

а? Что ж, вот странность, объяснения которой я не нашел, на самом деле tp_basicsizeof tuples вычисляется следующим образом:

sizeof(PyTupleObject) - sizeof(PyObject *)

почему 8удаляются дополнительные байты, tp_basicsizeмне не удалось выяснить. (См. Комментарий MSeifert для возможного объяснения)

Но это в основном разница в вашем конкретном примере . lists также поддерживает некоторое количество выделенных элементов, что помогает определить, когда снова следует перераспределить.

Теперь, когда добавляются дополнительные элементы, списки действительно выполняют это избыточное выделение для достижения O (1) добавлений. Это приводит к большим размерам, поскольку MSeifert прекрасно покрывает свой ответ.

Ответ MSeifert охватывает это широко; для простоты вы можете подумать о:

tupleнеизменен. Как только он установлен, вы не можете его изменить. Таким образом, вы заранее знаете, сколько памяти вам нужно выделить для этого объекта.

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

Бесплатного питания нет - за эти возможности приходится платить. Отсюда накладные расходы на память для списков.

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