Cuando estaba aprendiendo a programar, las listas de Python me parecían totalmente mágicas. Me las imaginaba como implementadas por algún tipo de estructura de datos mágica que era en parte lista enlazada, en parte matriz que era perfecta para todo.

A medida que crecía como ingeniero, se me ocurrió que esto era poco probable. Adiviné (correctamente) que en lugar de algún tipo de implementación mágica, simplemente estaba respaldada por un array redimensionable. Decidí leer el código y averiguarlo.

Una de las cosas buenas de CPython es la implementación legible. Aunque el archivo en cuestión tiene más de 2000 líneas de C, se trata principalmente del algoritmo de ordenación, y de la plantilla para hacer que las funciones se puedan llamar desde el código de Python.1 Las operaciones principales de la lista son cortas y directas.

Aquí hay algunas cosas interesantes que encontré leyendo la implementación. Los fragmentos de código que aparecen a continuación provienen del código fuente de CPython con comentarios explicativos añadidos por mí.

Recalificación de listas

Si añades a una lista de Python y la matriz de respaldo no es lo suficientemente grande, la matriz de respaldo debe expandirse. Cuando esto ocurre, el array de respaldo crece aproximadamente un 12%. Personalmente, había asumido que este factor de crecimiento era mucho mayor. En Java ArrayList crece un 50% cuando se expande2 y en Ruby, Array crece un 100%.3

// essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

enlace al código de reasignación de CPython

Hice algunos experimentos de rendimiento – la preasignación de arrays con construcciones como *500 no parece hacer ninguna diferencia notable. En mi benchmark no científico de anexar a una lista 100 millones de veces, Python 3 fue mucho más lento que Python 2 que fue mucho más lento que Ruby, sin embargo, se requiere mucha más investigación para determinar el impacto (si lo hay) del factor de crecimiento en el rendimiento de inserción.

Insertar al principio de la lista

Insertar al principio de una lista lleva un tiempo lineal – esto no es tan sorprendente dado el resto de la implementación, pero es bueno saber que some_list.insert(0,value) rara vez es una buena idea. Un usuario de Reddit me recordó de Deques que el comercio de tiempo constante insertar y eliminar de ambos extremos a cambio de tiempo constante de indexación.

// First, shift all the values after our insertion point// over by onefor (i = n; --i >= where; ) items = items;// Increment the number of references to v (the value we're inserting)// for garbage collectionPy_INCREF(v);// insert our actual itemitems = v;return 0;

enlace a CPython código de inserción

Crear rebanadas de la lista

Tomando una rebanada de una lista eg. some_listtambién es una operación de tiempo lineal en el tamaño de la rebanada, así que de nuevo, no hay magia. Podrías imaginar optimizar esto con algún tipo de semántica de copia-en-escritura pero el código de CPython favorece la simplicidad:

for (i = 0; i < len; i++) { PyObject *v = src; Py_INCREF(v); dest = v;}

enlace al código de rebanadas de CPython

Asignación de rebanadas

¡Puedes asignar a una rebanada! Estoy seguro de que esto es comúnmente conocido entre los desarrolladores profesionales de Python, pero nunca me he topado con ello en varios años de programación en python.Sólo lo descubrí cuando me encontré con la función list_ass_slice(...) en el código. Sin embargo, ten cuidado con las listas grandes – necesita copiar todos los elementos eliminados de la lista original, lo que duplicará brevemente el uso de memoria.

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Ordenación

Las matrices de Python se ordenan con un algoritmo conocido como “timsort”. Es tremendamente complicado y se describe en detalle en un documento lateral en el árbol de fuentes. A grandes rasgos, construye series cada vez más largas de elementos secuenciales y los fusiona. A diferencia de la ordenación por fusión normal, comienza buscando secciones de la lista que ya están ordenadas (runs en el código). Esto le permite aprovechar los datos de entrada que ya están parcialmente ordenados: Para ordenar pequeñas matrices (o pequeñas secciones de una matriz mayor) de hasta 64 elementos4, timsort utiliza la “ordenación binaria”. Se trata básicamente de una ordenación por inserción, pero utilizando la búsqueda binaria para insertar el elemento en la ubicación correcta. En realidad es un algoritmo O(n^2). Un ejemplo interesante de rendimiento en el mundo real ganando sobre la complejidad algorítmica en la práctica. link

¿Me he perdido algo genial sobre las listas de CPython? Hágamelo saber en los comentarios.

Gracias a Leah Alpert por proporcionar sugerencias en este post.

¿Quieres recibir un correo electrónico acerca de las nuevas publicaciones en el blog?

Publico alrededor de una vez cada pocas semanas sobre temas como bases de datos, internos del lenguaje y algoritmos, y recientemente, el aprendizaje profundo.¿Quieres contratarme? Estoy disponible para compromisos desde 1 semana hasta varios meses. ¡Contrátame! ¡