¿Por qué las tuplas ocupan menos espacio en la memoria que las listas?

105

A tupleocupa menos espacio de memoria en Python:

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

mientras que lists ocupa más espacio en la memoria:

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

¿Qué sucede internamente en la gestión de memoria de Python?

Jon
fuente
1
No estoy seguro de cómo funciona esto internamente, pero el objeto de lista al menos tiene más funciones como, por ejemplo, agregar que la tupla no tiene. Por lo tanto, tiene sentido que la tupla como un tipo de objeto más simple sea más pequeña
Metareven
Creo que también depende de una máquina a otra ... para mí, cuando verifico a = (1,2,3) toma 72 yb = [1,2,3] toma 88.
Amrit
6
Las tuplas de Python son inmutables. Los objetos mutables tienen una sobrecarga adicional para hacer frente a los cambios de tiempo de ejecución.
Lee Daniel Crocker
@Metareincluso la cantidad de métodos que tiene un tipo no afecta el espacio de memoria que ocupan las instancias. La lista de métodos y su código son manejados por el prototipo de objeto, pero las instancias almacenan solo datos y variables internas.
jjmontes

Respuestas:

144

Supongo que está usando CPython y con 64 bits (obtuve los mismos resultados en mi CPython 2.7 de 64 bits). Puede haber diferencias en otras implementaciones de Python o si tiene un Python de 32 bits.

Independientemente de la implementación, listlos mensajes de correo electrónico son de tamaño variable mientras quetuple s son de tamaño fijo.

Entonces tuple s pueden almacenar los elementos directamente dentro de la estructura, las listas, por otro lado, necesitan una capa de indirección (almacena un puntero a los elementos). Esta capa de indirección es un puntero, en sistemas de 64 bits que son 64 bits, por lo tanto, 8 bytes.

Pero hay otra cosa que listsí: sobreasignan. De list.appendlo contrario , sería una O(n)operación siempre : para que se amortice O(1)(¡mucho más rápido!), Se sobreasigna. Pero ahora tiene que realizar un seguimiento del tamaño asignado y el tamaño de relleno (tuple solo es necesario almacenar un tamaño, porque el tamaño asignado y el tamaño de relleno son siempre idénticos). Eso significa que cada lista tiene que almacenar otro "tamaño" que en los sistemas de 64 bits es un número entero de 64 bits, de nuevo 8 bytes.

Entonces, los lists necesitan al menos 16 bytes más de memoria que los tuples. ¿Por qué dije "al menos"? Debido a la sobreasignación. La sobreasignación significa que asigna más espacio del necesario. Sin embargo, la cantidad de sobreasignación depende de "cómo" crea la lista y el historial de anexos / eliminaciones:

>>> 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

Imagenes

Decidí crear algunas imágenes para acompañar la explicación anterior. Quizás estos sean útiles

Así es como (esquemáticamente) se almacena en la memoria en su ejemplo. Destaqué las diferencias con los ciclos rojos (a mano alzada):

ingrese la descripción de la imagen aquí

En realidad, eso es solo una aproximación porque los intobjetos también son objetos de Python y CPython incluso reutiliza números enteros pequeños, por lo que una representación probablemente más precisa (aunque no tan legible) de los objetos en la memoria sería:

ingrese la descripción de la imagen aquí

Enlaces útiles:

¡Tenga en cuenta que __sizeof__realmente no devuelve el tamaño "correcto"! Solo devuelve el tamaño de los valores almacenados. Sin embargo, cuando usa sys.getsizeofel resultado es diferente:

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

Hay 24 bytes "extra". Estos son reales , esa es la sobrecarga del recolector de basura que no se tiene en cuenta en el __sizeof__método. Esto se debe a que generalmente no se supone que use métodos mágicos directamente; use las funciones que saben cómo manejarlos, en este caso: sys.getsizeof(que en realidad agrega la sobrecarga de GC al valor devuelto __sizeof__).

MSeifert
fuente
Re " Entonces, las listas necesitan al menos 16 bytes más de memoria que las tuplas ", ¿no serían 8? Un tamaño para tuplas y dos tamaños para listas significa un tamaño adicional para listas.
ikegami
1
Sí, la lista tiene un "tamaño" extra (8 bytes) pero también almacena un puntero (8 bytes) a la "matriz de PyObject" en lugar de almacenarlos directamente en la estructura (lo que hace la tupla). 8 + 8 = 16.
MSeifert
2
Otro enlace útil sobre listla asignación de memoria stackoverflow.com/questions/40018398/…
vishes_shell
@vishes_shell Eso no está realmente relacionado con la pregunta porque el código en la pregunta no se sobreasigna en absoluto . Pero sí, es útil en caso de que desee saber más sobre la cantidad de sobreasignación al usar list()o una lista de comprensión.
MSeifert
1
@ user3349993 Las tuplas son inmutables, por lo que no se puede agregar a una tupla o eliminar un elemento de una tupla.
MSeifert
31

Profundizaré en el código base de CPython para que podamos ver cómo se calculan realmente los tamaños. En su ejemplo específico , no se han realizado sobreasignaciones, así que no tocaré eso .

Voy a usar valores de 64 bits aquí, como tú.


El tamaño de lists se calcula a partir de la siguiente función,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);
}

Aquí Py_TYPE(self)hay una macro que toma el ob_typede self(regresando PyList_Type) mientras que _PyObject_SIZEes otra macro que toma tp_basicsizede ese tipo. tp_basicsizese calcula como sizeof(PyListObject)dónde PyListObjectestá la estructura de la instancia.

La PyListObjectestructura tiene tres campos:

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

estos tienen comentarios (que recorté) que explican qué son, siga el enlace de arriba para leerlos. PyObject_VAR_HEADse expande en tres campos de 8 bytes ( ob_refcount, ob_typey ob_size) por lo que es una 24contribución de bytes.

Entonces por ahora reses:

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

o:

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

Si la instancia de la lista tiene elementos asignados. la segunda parte calcula su contribución. self->allocated, como su nombre lo indica, contiene el número de elementos asignados.

Sin ningún elemento, el tamaño de las listas se calcula como:

>>> [].__sizeof__()
40

es decir, el tamaño de la estructura de la instancia.


tuplelos objetos no definen una tuple_sizeoffunción. En cambio, usan object_sizeofpara calcular su tamaño:

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

Esto, en cuanto a lists, toma el tp_basicsizey, si el objeto tiene un valor distinto de cero tp_itemsize(lo que significa que tiene instancias de longitud variable), multiplica el número de elementos en la tupla (que obtiene a través de Py_SIZE) contp_itemsize .

tp_basicsizenuevamente usa sizeof(PyTupleObject)donde la PyTupleObjectestructura contiene :

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

Entonces, sin ningún elemento (es decir, Py_SIZEdevoluciones 0), el tamaño de las tuplas vacías es igual a sizeof(PyTupleObject):

>>> ().__sizeof__()
24

eh Bueno, aquí hay una rareza para la que no he encontrado una explicación, la tp_basicsizede tuples se calcula de la siguiente manera:

sizeof(PyTupleObject) - sizeof(PyObject *)

por qué 8se eliminan bytes adicionales tp_basicsizees algo que no he podido averiguar. (Ver el comentario de MSeifert para una posible explicación)


Pero, esta es básicamente la diferencia en su ejemplo específico . lists también mantienen una serie de elementos asignados que ayuda a determinar cuándo sobreasignar nuevamente.

Ahora, cuando se agregan elementos adicionales, las listas sí realizan esta sobreasignación para lograr agregados O (1). Esto da como resultado tamaños más grandes, ya que MSeifert cubre muy bien en su respuesta.

Dimitris Fasarakis Hilliard
fuente
Creo que ob_item[1]es principalmente un marcador de posición (por lo que tiene sentido que se reste del tamaño básico). El tuplese asigna usando PyObject_NewVar. No he descubierto los detalles, así que es solo una suposición
informada
@MSeifert Lo siento, arreglado :-). Realmente no lo sé, recuerdo haberlo encontrado en el pasado en algún momento, pero nunca le
presté
29

La respuesta de MSeifert lo cubre ampliamente; para hacerlo simple, puede pensar en:

tuplees inmutable. Una vez configurado, no puede cambiarlo. Entonces, sabe de antemano cuánta memoria necesita asignar para ese objeto.

listes mutable. Puede agregar o quitar elementos de él. Tiene que saber su tamaño (para impl. Interna). Cambia de tamaño según sea necesario.

No hay comidas gratis ; estas capacidades tienen un costo. De ahí la sobrecarga en la memoria para las listas.

Chen A.
fuente
3

El tamaño de la tupla tiene un prefijo, lo que significa que en la inicialización de la tupla el intérprete asigna suficiente espacio para los datos contenidos, y ese es el final, lo que le da inmutable (no se puede modificar), mientras que una lista es un objeto mutable, por lo tanto, implica dinámica asignación de memoria, por lo que para evitar asignar espacio cada vez que agrega o modifica la lista (asigne suficiente espacio para contener los datos cambiados y copie los datos), asigna espacio adicional para futuras adiciones, modificaciones, ... eso prácticamente lo resume.

rachid el kedmiri
fuente