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

Por Kiko Correoso

Vamos a empezar con más preguntas que respuestas.

  <p>
    Como sabéis, las listas de Python son <em>arrays</em> dinámicos. Por otro lado, las tuplas son <em>arrays</em> estáticos.
  </p>

  <p>
    <strong>¿Qué implica que las listas sean <em>arrays</em> dinámicos?</strong>
  </p>

  <p>
    Al ser un array dinámico podemos modificar sus elementos así como extender el array (lista).
  </p>

  <p>
    <strong>¿Cómo funciona lo de extender el <em>array</em> (lista)?</strong>
  </p>

  <p>
    Cada vez que usamos el método <code>append</code> 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.
  </p>

  <p>
    <strong>¿Es esto último cierto?</strong>
  </p>

  <p>
    Más o menos.
  </p>

  <p>
    Todos estaréis conmigo que si cada vez que añadimos un nuevo elemento tenemos que crear una copia y luego eliminar el <em>array</em> original podríamos crear cierto coste/gasto de recursos (en memoria, principalmente, creando copias).
  </p>

  <p>
    Veamos un poco de código:
  </p>
</div>

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

    <div>
      <pre>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.

  <p>
    <strong>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?</strong>
  </p>

  <p>
    Veamos qué dice el código original de las listas en el repo de Python localizado en <a href="https://hg.python.org/releasing/3.5/file/tip/Objects/listobject.c#l42">Objects/listobject.c</a>.
  </p>

  <p>
    A partir de la línea 42 del código C podemos leer:
  </p>

      :::[]
/* 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 &gt;&gt; 3) + (newsize &lt; 9 ? 3 : 6);



  <p>
    La última línea traducida a Python sería algo así:
  </p>

      :::[]
new_allocated = (newsize &gt;&gt; 3) + (3 if newsize &lt; 9 else 6)



  <p>
    En el primer paréntesis tenemos el <a href="https://wiki.python.org/moin/BitwiseOperators">operador <em>bitwise right shift</em></a>, 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).
  </p>

  <p>
    <strong>¿Qué está pasando aquí?</strong>
  </p>

  <p>
    Los buenos de los <em>core developers</em> de CPython han pensado que si usas un <em>array</em> 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 <em>array</em> (lista) y, de esta forma, podemos ampliarlo sin necesidad de crear tantas copias.
  </p>

  <p>
    Veamos esto gráficamente:
  </p>
</div>

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$')

    <div>
      <pre>&lt;matplotlib.text.Text at 0x7f0655169c88&gt;</pre>
    </div>
  </div>

  <div>
    <div>
    </div>

    <div>
      <img src="http://new.pybonacci.org/images/2015/11/wpid-¿Cómo_funciona_el_método_append_de_una_lista_en_CPython1.png" alt="" />
    </div>
  </div>
</div>

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

    <div>
      <pre>&lt;matplotlib.text.Text at 0x7f06552ada20&gt;</pre>
    </div>
  </div>

  <div>
    <div>
    </div>

    <div>
      <img src="http://new.pybonacci.org/images/2015/11/wpid-¿Cómo_funciona_el_método_append_de_una_lista_en_CPython2.png" alt="" />
    </div>
  </div>
</div>

Curioso, ¿no?

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


photo

Kiko es doctor en ciencias físicas y esta especializado en física de la atmósfera, meteorología y climatología. Además de estar en las nubes es especialista en temas de energías renovables en Iberdrola. Ávido de seguir mejorando siempre está abierto a participar en nuevos proyectos y retos por lo que no dudes en contactarle si necesitas servicios especializados de Python o meteorología.