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

Ответ 1

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

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

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

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

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

>>> 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 "лишних" байта. Это real, что служебные данные сборщика мусора, которые не учитываются в методе __sizeof__. Это потому, что вы, как правило, не должны использовать магические методы напрямую - используйте функции, которые знают, как обращаться с ними, в этом случае: sys.getsizeof (который на самом деле добавляет накладные расходы GC к значению, возвращенному из __sizeof__).

Ответ 2

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

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

Размер для list рассчитывается по следующей функции: 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 of 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 byte.

Итак, теперь res:

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

или

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

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

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

>>> [].__sizeof__()
40

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

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);
}

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

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

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

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

>>> ().__sizeof__()
24

а? Ну, вот странность, которую я не нашел объяснения, tp_basicsize of tuple фактически вычисляется следующим образом:

sizeof(PyTupleObject) - sizeof(PyObject *)

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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