Alors que j’apprenais à programmer, les listes Python me semblaient totalement magiques. Je les imaginais comme étant implémentées par une sorte de structure de données magique qui était en partie linked-list, en partie array et qui était parfaite pour tout.

A mesure que je grandissais en tant qu’ingénieur, il m’est apparu que c’était peu probable. J’ai deviné (correctement) que plutôt qu’une sorte d’implémentation magique, il était juste soutenu par un tableau redimensionnable. J’ai décidé de lire le code et de le découvrir.

Une des belles choses de CPython est l’implémentation lisible. Bien que le fichier pertinent soit de plus de 2000 lignes de C, il s’agit principalement de l’algorithme de tri, et du boilerplate pour rendre les fonctions appelables à partir du code Python.1 Les opérations de liste de base sont courtes et directes.

Voici quelques choses intéressantes que j’ai trouvées en lisant l’implémentation. Les extraits de code ci-dessous proviennent de la source CPython avec des commentaires explicatifs ajoutés par moi.

Redimensionnement de liste

Si vous ajoutez à une liste Python et que le tableau de support n’est pas assez grand, le tableau de support doit être étendu. Lorsque cela se produit, le tableau d’appui est agrandi d’environ 12 %. Personnellement, j’avais supposé que ce facteur de croissance était beaucoup plus important. En Java, ArrayList croît de 50% lorsqu’il est étendu2 et en Ruby, Array croît de 100%.3

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

lien vers le code de réallocation CPython

J’ai fait quelques expériences de performance – la pré-allocation des tableaux avec des constructions comme *500 ne semble pas faire de différence notable. Dans mon benchmark non scientifique consistant à annexer à une liste 100 millions de fois, Python 3 était beaucoup plus lent que Python 2 qui était beaucoup plus lent que Ruby, cependant, beaucoup plus de recherches sont nécessaires pour déterminer l’impact (s’il y en a un) du facteur de croissance sur les performances d’insertion.

Insérer au début de la liste

Insérer au début d’une liste prend un temps linéaire – ce n’est pas si surprenant étant donné le reste de l’implémentation, mais il est bon de savoir que some_list.insert(0,value) est rarement une bonne idée. Un utilisateur de Reddit m’a rappelé les Deques qui échangent l’insertion et la suppression en temps constant des deux extrémités en échange d’une indexation en temps constant.

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

lien vers le code d’insertion CPython

Création de tranches de liste

Prendre une tranche d’une liste ex. some_listest également une opération de temps linéaire dans la taille de la tranche, donc encore une fois, pas de magie. On pourrait imaginer d’optimiser cela avec une sorte de sémantique de copie sur écriture mais le code CPython privilégie la simplicité :

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

lien vers le code CPython des tranches

Slice Assignment

Vous pouvez assigner à une tranche ! Je suis sûr que cela est communément connu parmi les développeurs professionnels Python, mais je n’ai jamais rencontré cela en plusieurs années de programmation python.Je ne l’ai découvert que lorsque je suis tombé sur la fonction list_ass_slice(...) dans le code. Cependant, attention aux grandes listes – elle doit copier tous les éléments supprimés de la liste originale, ce qui doublera brièvement l’utilisation de la mémoire.

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

Tri

Les tableaux Python sont triés avec un algorithme connu sous le nom de “timsort”. C’est sauvagement compliqué et décrit en détail dans un document annexe dans l’arbre des sources. En gros, il construit des séries de plus en plus longues d’éléments séquentiels et les fusionne. Contrairement au tri par fusion normal, il commence par rechercher les sections de la liste qui sont déjà triées (runs dans le code). Cela lui permet de tirer parti de données d’entrée qui sont déjà partiellement triées.Un détail intéressant : Pour trier les petits tableaux (ou les petites sections d’un tableau plus grand) jusqu’à 64 éléments4, timsort utilise le “tri binaire”. Il s’agit essentiellement d’un tri par insertion, mais qui utilise la recherche binaire pour insérer l’élément au bon endroit. Il s’agit en fait d’un algorithme O(n^2) ! Un exemple intéressant de performance du monde réel gagnant sur la complexité algorithmique en pratique. link

Ai-je manqué quelque chose de cool à propos des listes CPython ? Faites-le moi savoir dans les commentaires.

Merci à Leah Alpert pour avoir fourni des suggestions sur cet article.

Vous voulez être informé par courriel des nouveaux articles du blog ?

Je publie environ une fois toutes les quelques semaines sur des sujets comme les bases de données, les internes et les algorithmes de langage, et récemment, l’apprentissage profond.Voulez-vous m’embaucher ? Je suis disponible pour des engagements de 1 semaine à quelques mois. Engagez-moi !

.