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

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

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

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

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

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

Источник

4 ответа

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

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

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

Но есть еще одна вещь, которая list S делают: они переизбыток. Иначе 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 даже многократно использует маленькие целые числа, поэтому, вероятно, более точное представление (хотя и не столь удобочитаемое) объектов в памяти:

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

Обратите внимание, что __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-битные значения, как и вы.

Размер для list s рассчитывается по следующей функции, 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);
}

Это, как для list s, хватает 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_basicsize из tuple S фактически рассчитывается следующим образом:

sizeof(PyTupleObject) - sizeof(PyObject *)

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

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

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

Источник

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

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

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

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

Источник

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

Источник
Другие вопросы по тегам