Pregunta list () usa más memoria que lista de comprensión


Así que estaba jugando con list objetos y encontró una pequeña cosa extraña que si list se crea con list() usa más memoria, que lista de comprensión? Estoy usando Python 3.5.2

In [1]: import sys
In [2]: a = list(range(100))
In [3]: sys.getsizeof(a)
Out[3]: 1008
In [4]: b = [i for i in range(100)]
In [5]: sys.getsizeof(b)
Out[5]: 912
In [6]: type(a) == type(b)
Out[6]: True
In [7]: a == b
Out[7]: True
In [8]: sys.getsizeof(list(b))
Out[8]: 1008

Desde el documentos:

Las listas se pueden construir de varias maneras:

  • Usando un par de corchetes para indicar la lista vacía: []
  • Utilizando corchetes, separando elementos con comas: [a], [a, b, c]
  • Usando una lista de comprensión: [x for x in iterable]
  • Usando el constructor de tipo: list() o list(iterable)

Pero parece que usar list() usa más memoria.

Y tanto list es más grande, la brecha aumenta.

Difference in memory

¿Por qué sucede esto?

ACTUALIZACIÓN # 1

Prueba con Python 3.6.0b2:

Python 3.6.0b2 (default, Oct 11 2016, 11:52:53) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(range(100)))
1008
>>> sys.getsizeof([i for i in range(100)])
912

ACTUALIZACIÓN # 2

Prueba con Python 2.7.12:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(xrange(100)))
1016
>>> sys.getsizeof([i for i in xrange(100)])
920

75
2017-10-13 10:25


origen


Respuestas:


Creo que estás viendo patrones de asignación excesiva esto es muestra de la fuente:

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

Al imprimir los tamaños de las listas de comprensiones de longitudes 0-88, puede ver que el patrón coincide:

# create comprehensions for sizes 0-88
comprehensions = [sys.getsizeof([1 for _ in range(l)]) for l in range(90)]

# only take those that resulted in growth compared to previous length
steps = zip(comprehensions, comprehensions[1:])
growths = [x for x in list(enumerate(steps)) if x[1][0] != x[1][1]]

# print the results:
for growth in growths:
    print(growth)

Resultados (el formato es (list length, (old total size, new total size)))

(0, (64, 96)) 
(4, (96, 128))
(8, (128, 192))
(16, (192, 264))
(25, (264, 344))
(35, (344, 432))
(46, (432, 528))
(58, (528, 640))
(72, (640, 768))
(88, (768, 912))

La sobreasignación se realiza por razones de rendimiento, lo que permite que las listas crezcan sin asignar más memoria con cada crecimiento (mejor amortizado actuación).

Una razón probable de la diferencia con el uso de la lista de comprensión, es que la comprensión de la lista no puede calcular determinísticamente el tamaño de la lista generada, pero list() poder. Esto significa que las comprensiones crecerán continuamente en la lista a medida que la llene utilizando una asignación excesiva hasta que finalmente la complete.

Es posible que no se haga crecer el búfer de sobreasignación con nodos asignados no utilizados una vez hecho (de hecho, en la mayoría de los casos no lo hará, eso vencería el propósito de sobreasignación).

list()Sin embargo, puede agregar un búfer sin importar el tamaño de la lista, ya que conoce el tamaño de la lista final por adelantado.


Otra evidencia de respaldo, también de la fuente, es que vemos enumerar comprensiones invocando LIST_APPEND, que indica el uso de list.resize, lo que a su vez indica que consume el búfer de asignación previa sin saber cuánto se llenará. Esto es consistente con el comportamiento que estás viendo.


Para concluir, list() preasignará más nodos como una función del tamaño de la lista

>>> sys.getsizeof(list([1,2,3]))
60
>>> sys.getsizeof(list([1,2,3,4]))
64

La comprensión de la lista no conoce el tamaño de la lista, por lo que utiliza operaciones de adición a medida que crece, agotando el almacenamiento intermedio de asignación previa:

# one item before filling pre-allocation buffer completely
>>> sys.getsizeof([i for i in [1,2,3]]) 
52
# fills pre-allocation buffer completely
# note that size did not change, we still have buffered unused nodes
>>> sys.getsizeof([i for i in [1,2,3,4]]) 
52
# grows pre-allocation buffer
>>> sys.getsizeof([i for i in [1,2,3,4,5]])
68

55
2017-10-13 10:40



Gracias a todos por ayudarme a entender ese impresionante Python.

No quiero hacer una pregunta tan masiva (por eso estoy publicando respuesta), solo quiero mostrar y compartir mis pensamientos.

Como @ReutSharabani anotado correctamente: "list () determina determinísticamente el tamaño de la lista". Puedes verlo desde ese gráfico.

graph of sizes

Cuando tú append o al usar la lista de comprensión siempre tienes algún tipo de límites que se extienden cuando llegas a algún punto. Y con list() tienes casi los mismos límites, pero están flotando.

ACTUALIZAR

Así que gracias a @ReutSharabani, @tavo, @SvenFestersen

Para resumir: list() la memoria preasignada depende del tamaño de la lista, la comprensión de la lista no puede hacer eso (solicita más memoria cuando lo necesita, como .append()) Es por eso list() almacenar más memoria.

Un gráfico más, ese espectáculo list() preasigna memoria Así que la línea verde muestra list(range(830)) añadiendo elemento por elemento y durante un tiempo la memoria no cambia.

list() preallocates memory

ACTUALIZACIÓN 2

Como @Barmar señaló en los comentarios a continuación, list() me debe más rápido que la comprensión de la lista, así que corrí timeit() con number=1000 por la duración de list de 4**0 a 4**10 y los resultados son

time measurements


27
2017-10-13 11:37