Comment la liste de Python est-elle mise en œuvre ?

Question

Est-ce une liste liée, un tableau ? J'ai cherché partout et je n'ai trouvé que des gens qui devinaient. Mes connaissances en C ne sont pas assez bonnes pour regarder le code source.

Answer 1

Le code C est assez simple, en fait. En augmentant une macro et en supprimant quelques commentaires non pertinents, la structure de base est la suivante listobject.h qui définit une liste comme suit :

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEAD contient un nombre de références et un identifiant de type. Donc, c'est un vecteur/rayon qui sur-alloue. Le code pour redimensionner un tel tableau quand il est plein est dans listobject.c . Il ne double pas réellement le tableau, mais le fait croître en allouant

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

à la capacité à chaque fois, où newsize est la taille demandée (pas nécessairement allocated + 1 parce que vous pouvez extend par un nombre arbitraire d'éléments au lieu de append en les prenant un par un).

Voir aussi le FAQ Python .

Answer 2

C'est un réseau dynamique . Preuve pratique : L'indexation prend (bien sûr avec des différences extrêmement faibles (0,0013 µsecs !)) le même temps quel que soit l'index :

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

Je serais stupéfait si IronPython ou Jython utilisaient des listes liées - ils ruineraient les performances de nombreuses bibliothèques largement utilisées, construites sur l'hypothèse que les listes sont des tableaux dynamiques.

Answer 3

Cela dépend de l'implémentation, mais IIRC :

• CPython utilise un tableau de pointeurs
• Jython utilise un ArrayList
• IronPython utilise apparemment aussi un tableau. Vous pouvez parcourir le code source pour le découvrir.

Ils ont donc tous un accès aléatoire O(1).

Answer 4

En CPython, les listes sont des tableaux de pointeurs. D'autres implémentations de Python peuvent choisir de les stocker de manière différente.

Answer 5

Selon le documentation ,

Les listes de Python sont en fait des tableaux de longueur variable, et non des listes liées de type Lisp.