Comment sont implémentées les listes Python ?

[rambc]

Bonjour,
tout est dans la question ou presque. Lors de la "compilation" d'un script Python, quel type C est utilisé pour les listes ?

Je pose la question pour mieux comprendre les différences de performance entre maListe.pop() et maListe.pop(0).

[wiztricks]

Salut,

Une liste Python n'existe pas en C "standard", c'est un objet Python implémenté dans listobject.c.

En gros, les items de cette liste sont rangés dans un tableau (ob_item).
Si c'est le dernier élément, il suffit de redimensionner la capacité du tableau.

Lorsqu'il s'agit d'un autre élément, il faut "avancer" les éléments suivants: c'est cette opération qui va coûter.
- W

[VV33D]

Il est conseillé d'utiliser collections.deque plutôt que List si on veut append/pop rapidement aux deux extrémités

[Sve@r]

Salut

A mon avis, le plus simple pour toi (qui a tant envie de comprendre) serait de refaire en C un ersatz de liste Python.

Et (désolé de contredire wiztricks qui est notre maitre à penser Python), au lieu de passer par un tableau je passerais par une liste chainée, un peu dans ce style...

Code c :

1
2
3
4
5
6
7
8
9
typedef struct s_elem {
    void *pt_data;
    struct s_elem *next;
} t_elem;
 
typedef struct {
    t_elem *first;
    size_t nb_elem;
} t_liste;

...ce qui simplifierait assez grandement les opérations append(), del() et pop()...

[fred1599]

Tout à fait Sve@r, je suis d'accord avec toi, c'est un équivalent d'une deque.

Mais en fait ce que Wiztrick veut dire est qu'on utilise l'API C avec un tableau (**ob_item) et les dérivés à PyObject. La librairie utilisée est Python.h

Donc une lib C oui, mais qui sort du standard C habituel, voilà pourquoi la réponse est difficile à donner si tu ne te connais pas un minimum dans l'API C...

[wiztricks]

Si rambc a posé cette question, c'est sans doute parce que sa liste est de très grande taille.

Faire du FIFO sur une structure adaptée pour du LIFO n'est pas "top" et si son cas d'utilisation est FIFO, collections.deque sera mieux.

Comme il n'a pas indiqué ce qu'il faisait avec, ce mieux côté FIFO ne sera pas forcément bien (dans son contexte).
- W

[dividee]

Je me suis justement intéressé à ce sujet récemment; je voulais implémenter une structure de donnée similaire au listes Python dans un autre langage et je voulais voir comment elles étaient implémentées.

Comme l'a dit wiztricks, les listes Python sont implémentées par des tableaux en C dans listobject.c
Si le tableau devient trop petit, il est redimensionné avec realloc, ce qui peut impliquer la copie complète du tableau. Pour amortir ce coût, une surallocation est faite: chaque fois qu'on doit agrandir le tableau, on alloue environ 12,5% de plus que la taille demandée (pour de grand tableaux; plus que ça quand le tableau est petit):

Code :

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); /* dans list_resize */

newsize est la taille demandée; new_allocated correspond à la surallocation. La taille finalement allouée est la somme des deux.

Si la taille demandée est inférieure à la moitié de la taille allouée, il y a aussi un realloc pour réduire la taille allouée.

Un pop(0) finira par exécuter le code suivant:

Code :

1
2
3
4
5
    if (d < 0) { /* Delete -d items */
        memmove(&item[ihigh+d], &item[ihigh],
            (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
        list_resize(a, Py_SIZE(a) + d);
        ...

a est un pointeur vers la structure qui représente la liste. item est a->ob_item, le tableau proprement dit. Pour un pop(0), on aura d = -1; ihigh=1. C'est ce memmove qui est coûteux pour un pop(0).

L'appel à list_resize ci-dessus ne fera la plupart du temps pas de réallocation, sauf si la taille de la liste descend au-dessous de la moitié de la taille actuellement allouée.

Pour un pop(), le memmove se ferait sur 0 éléments et retournerait donc immédiatement, mais, sans doute pour optimiser, ce code est même court-circuité:

Code :

1
2
3
4
5
   if (i == Py_SIZE(self) - 1) {
        status = list_resize(self, Py_SIZE(self) - 1);
        assert(status >= 0);
        return v;
    }

Si l'élément à supprimer est le dernier, il fait juste un appel à list_resize et c'est tout.

[rambc]

Bonssir,
désolé pour ce retard mais en ce moment c'est un méga rush... Je regarde vos messages et réponds ce weekend.

[rambc]

Envoyé par rambc

Bonssir,
désolé pour ce retard mais en ce moment c'est un méga rush... Je regarde vos messages et réponds ce weekend.

Disons plutôt pendant les vacances de Noël...