Saltar al contenido

¿Cómo funciona el método append de una lista en CPython?

Vamos a empezar con más preguntas que respuestas.
Como sabéis, las listas de Python son arrays dinámicos. Por otro lado, las tuplas son arrays estáticos.
¿Qué implica que las listas sean arrays dinámicos?
Al ser un array dinámico podemos modificar sus elementos así como extender el array (lista).
¿Cómo funciona lo de extender el array (lista)?
Cada vez que usamos el método append de las listas se crea una copia de la lista original y se añade un elemento a esa copia para luego borrar el array original.
¿Es esto último cierto?
Más o menos.
Todos estaréis conmigo que si cada vez que añadimos un nuevo elemento tenemos que crear una copia y luego eliminar el array original podríamos crear cierto coste/gasto de recursos (en memoria, principalmente, creando copias).
Veamos un poco de código:

import sys 
lista = []
for i in range(100):
    lista.append(i)
    txt = 'número de elementos = {0:>3} , tamaño de la lista = {1:>4}'
    print(txt.format(i + 1, sys.getsizeof(lista)))
número de elementos =   1 , tamaño de la lista =   96
número de elementos =   2 , tamaño de la lista =   96
número de elementos =   3 , tamaño de la lista =   96
número de elementos =   4 , tamaño de la lista =   96
número de elementos =   5 , tamaño de la lista =  128
número de elementos =   6 , tamaño de la lista =  128
número de elementos =   7 , tamaño de la lista =  128
número de elementos =   8 , tamaño de la lista =  128
número de elementos =   9 , tamaño de la lista =  192
número de elementos =  10 , tamaño de la lista =  192
número de elementos =  11 , tamaño de la lista =  192
número de elementos =  12 , tamaño de la lista =  192
número de elementos =  13 , tamaño de la lista =  192
número de elementos =  14 , tamaño de la lista =  192
número de elementos =  15 , tamaño de la lista =  192
número de elementos =  16 , tamaño de la lista =  192
número de elementos =  17 , tamaño de la lista =  264
número de elementos =  18 , tamaño de la lista =  264
número de elementos =  19 , tamaño de la lista =  264
número de elementos =  20 , tamaño de la lista =  264
número de elementos =  21 , tamaño de la lista =  264
número de elementos =  22 , tamaño de la lista =  264
número de elementos =  23 , tamaño de la lista =  264
número de elementos =  24 , tamaño de la lista =  264
número de elementos =  25 , tamaño de la lista =  264
número de elementos =  26 , tamaño de la lista =  344
número de elementos =  27 , tamaño de la lista =  344
número de elementos =  28 , tamaño de la lista =  344
número de elementos =  29 , tamaño de la lista =  344
número de elementos =  30 , tamaño de la lista =  344
número de elementos =  31 , tamaño de la lista =  344
número de elementos =  32 , tamaño de la lista =  344
número de elementos =  33 , tamaño de la lista =  344
número de elementos =  34 , tamaño de la lista =  344
número de elementos =  35 , tamaño de la lista =  344
número de elementos =  36 , tamaño de la lista =  432
número de elementos =  37 , tamaño de la lista =  432
número de elementos =  38 , tamaño de la lista =  432
número de elementos =  39 , tamaño de la lista =  432
número de elementos =  40 , tamaño de la lista =  432
número de elementos =  41 , tamaño de la lista =  432
número de elementos =  42 , tamaño de la lista =  432
número de elementos =  43 , tamaño de la lista =  432
número de elementos =  44 , tamaño de la lista =  432
número de elementos =  45 , tamaño de la lista =  432
número de elementos =  46 , tamaño de la lista =  432
número de elementos =  47 , tamaño de la lista =  528
número de elementos =  48 , tamaño de la lista =  528
número de elementos =  49 , tamaño de la lista =  528
número de elementos =  50 , tamaño de la lista =  528
número de elementos =  51 , tamaño de la lista =  528
número de elementos =  52 , tamaño de la lista =  528
número de elementos =  53 , tamaño de la lista =  528
número de elementos =  54 , tamaño de la lista =  528
número de elementos =  55 , tamaño de la lista =  528
número de elementos =  56 , tamaño de la lista =  528
número de elementos =  57 , tamaño de la lista =  528
número de elementos =  58 , tamaño de la lista =  528
número de elementos =  59 , tamaño de la lista =  640
número de elementos =  60 , tamaño de la lista =  640
número de elementos =  61 , tamaño de la lista =  640
número de elementos =  62 , tamaño de la lista =  640
número de elementos =  63 , tamaño de la lista =  640
número de elementos =  64 , tamaño de la lista =  640
número de elementos =  65 , tamaño de la lista =  640
número de elementos =  66 , tamaño de la lista =  640
número de elementos =  67 , tamaño de la lista =  640
número de elementos =  68 , tamaño de la lista =  640
número de elementos =  69 , tamaño de la lista =  640
número de elementos =  70 , tamaño de la lista =  640
número de elementos =  71 , tamaño de la lista =  640
número de elementos =  72 , tamaño de la lista =  640
número de elementos =  73 , tamaño de la lista =  768
número de elementos =  74 , tamaño de la lista =  768
número de elementos =  75 , tamaño de la lista =  768
número de elementos =  76 , tamaño de la lista =  768
número de elementos =  77 , tamaño de la lista =  768
número de elementos =  78 , tamaño de la lista =  768
número de elementos =  79 , tamaño de la lista =  768
número de elementos =  80 , tamaño de la lista =  768
número de elementos =  81 , tamaño de la lista =  768
número de elementos =  82 , tamaño de la lista =  768
número de elementos =  83 , tamaño de la lista =  768
número de elementos =  84 , tamaño de la lista =  768
número de elementos =  85 , tamaño de la lista =  768
número de elementos =  86 , tamaño de la lista =  768
número de elementos =  87 , tamaño de la lista =  768
número de elementos =  88 , tamaño de la lista =  768
número de elementos =  89 , tamaño de la lista =  912
número de elementos =  90 , tamaño de la lista =  912
número de elementos =  91 , tamaño de la lista =  912
número de elementos =  92 , tamaño de la lista =  912
número de elementos =  93 , tamaño de la lista =  912
número de elementos =  94 , tamaño de la lista =  912
número de elementos =  95 , tamaño de la lista =  912
número de elementos =  96 , tamaño de la lista =  912
número de elementos =  97 , tamaño de la lista =  912
número de elementos =  98 , tamaño de la lista =  912
número de elementos =  99 , tamaño de la lista =  912
número de elementos = 100 , tamaño de la lista =  912

En el anterior código hemos creado una lista vacía y le hemos ido añadiendo elementos y hemos obtenido el tamaño de la lista usando la función getsizeof que nos indica el tamaño del objeto en bytes. Luego hemos mostrado en pantalla el número de elementos que tiene la lista y el tamaño que ocupa.
Pero, ¿qué ocurre?, ¿por qué aumentando el número de elementos, a veces, no aumenta el tamaño del objeto?, ¿por qué luego cambia?, ¿por qué a medida que hay más elementos en la lista tarda más en cambiar el tamaño de la misma?
Veamos qué dice el código original de las listas en el repo de Python localizado en Objects/listobject.c.
A partir de la línea 42 del código C podemos leer:

/* 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);

La última línea traducida a Python sería algo así:

new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)

En el primer paréntesis tenemos el operador bitwise right shift, similar a la versión en C (no hay que olvidar que CPython está escrito en C) mientras que en el segundo paréntesis tenemos el operador ternario (sin duda, un poco más legible que la versión en C).
¿Qué está pasando aquí?
Los buenos de los core developers de CPython han pensado que si usas un array dinámico será porque quieres hacer 'perrerías' con él, como ampliarlo. Y si lo amplías una vez es probable que lo amplíes varias veces. Es por ello que, normalmente, se usa un un tamaño un poco mayor, basado en el tamaño y siquiendo la regla mostrada más arriba, para el array (lista) y, de esta forma, podemos ampliarlo sin necesidad de crear tantas copias.
Veamos esto gráficamente:

Importamos matplotlib para poder crear los gráficos.

import matplotlib.pyplot as plt
plt.style.use('ggplot')
%matplotlib inline

Creamos nuestra lista y otra lista que almacenará los tamaños en bytes, sizes.

lista = list([1])
sizes = [sys.getsizeof(lista)]

for i in range(2, 100000):
    lista.append(i)
    sizes.append(sys.getsizeof(lista))

Y ahora dibujamos los tamaños en función del número de elementos dentro de la lista:

plt.figure(figsize = (10,10)) plt.plot(lista, sizes) plt.xlabel('Número de elementos en la lista') plt.ylabel('Tamaño en bytes para la lista de tamaño $N$')
<matplotlib.text.Text at 0x7f0655169c88>

Vemos como los "escalones" en el tamaño de la lista con N elementos va aumentando y el escalón cada vez es más largo a medida que aumenta el tamaño de la lista.

Veamos como es el valor del tamaño dividido por el número de elementos de la lista a medida que va aumentando el mismo (los ejes de la gráfica tienen escala logarítmica):

increment = [s/l for s, l in zip(sizes, lista)]

plt.figure(figsize = (10,10))
plt.yscale('log') plt.xscale('log')
plt.ylim(7, max(increment))
plt.plot(lista, increment)
plt.xlabel('Número de elementos en la lista')
plt.ylabel('Bytes por número de elementos')
<matplotlib.text.Text at 0x7f06552ada20>

Curioso, ¿no?

Espero que hayáis aprendido tanto como he aprendido yo elaborando esta entrada.

8 comentarios en «¿Cómo funciona el método append de una lista en CPython?»

  1. Muy muy bueno este post, muchas gracias por escribirlo. Ya que esclarece a los usuarios más noveles como funcionan los arrays dinámicos y cual es su principal problema, el coste computacional.
    Puede que la pregunta que vaya a hacer no tenga sentido porque llevo poco tiempo usando Python (días), pero esta deseando llegar a la parte a la que se mostraban las figuras de los resultados con CPython así como la comparativa en tiempos de ejecución del programa y… RESULTA QUE NO ESTÁ! No se si es porque es muy difícil o porque se hacía muy largo el post, pero me hubiese encantado seguir leyendo sobre los resultados ahora con CPython y agradecería que se incluyesen en un futuro, bien en este post o en una parte II de él.
    Muchas gracias, un saludo!

    1. Hola, me alegro que te haya gustado la entrada y que hayas aprendido algo. ¡De eso se trata!
      Respecto al segundo párrafo, no entiendo muy bien qué es lo que pides. En la entrada no hablamos en ningún momento sobre tiempos de ejecución. Hablamos de uso de memoria. ¿Qué es lo que quieres que midamos en tiempos de ejecución?
      Saludos.

  2. Hola, he tenido una duda que no he podido solucionar.
    Resulta que tengo unos datos con extension .dat ordenados en columnas y lo que quiero es leer cada linea del archivo y guardarla como un array dentro de un array. Bueno esto se hace por si solo al abrir el archivo con np.loadtxt, pero aquí está mi problema: son mas de un archivo con el mismo formato los que quiero integrar al array principal, pero con la funcion append me los integra como datos suelto, no como array(listas) como yo quiero.
    Agradecería si me pudiesen ayudar con alguna funcion que esté predeterminada o algun hint de cómo crear una.
    Saludos

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

− four = two

Pybonacci