Comment la liste de Python est-elle implémentée?

Est-ce une liste chaîné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.

C'est un tableau 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'indice:

...>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 étonné si IronPython ou Jython utilisaient des listes chaînées - elles ruineraient les performances de nombreuses bibliothèques largement utilisées construites sur l'hypothèse que les listes sont des tableaux dynamiques.

Le code C est assez simple, en fait. En développant une macro et en élaguant certains commentaires non pertinents, la structure de base est dans listobject.h, qui définit une liste comme:

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_HEADcontient un nombre de références et un identificateur de type. Donc, c'est un vecteur / tableau qui surutilisent. Le code pour redimensionner un tel tableau lorsqu'il est plein est dans listobject.c. Il ne double pas réellement le tableau, mais augmente en allouant

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

à la capacité à chaque fois, où newsizeest la taille demandée (pas nécessairement allocated + 1parce que vous pouvez extendpar un nombre arbitraire d'éléments au lieu deappend 'inger un par un).

Voir aussi la FAQ Python .

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

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

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

Ainsi, ils ont tous un accès aléatoire O (1).

Je suggérerais l'article de Laurent Luce "Implémentation de liste Python" . Cela m'a vraiment été utile car l'auteur explique comment la liste est implémentée en CPython et utilise d'excellents diagrammes à cet effet.

Structure de l'objet C de liste

Un objet de liste en CPython est représenté par la structure C suivante. ob_itemest une liste de pointeurs vers les éléments de la liste. alloué est le nombre d'emplacements alloués en mémoire.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Il est important de noter la différence entre les emplacements alloués et la taille de la liste. La taille d'une liste est la même que len(l). Le nombre d'emplacements alloués correspond à ce qui a été alloué en mémoire. Souvent, vous verrez que la taille allouée peut être supérieure à la taille. Cela évite d'avoir à appeler reallocchaque fois qu'un nouvel élément est ajouté à la liste.

...

Ajouter

Nous ajoutons un entier à la liste: l.append(1). Ce qui se produit?

Nous continuons en ajoutant un élément de plus: l.append(2). list_resizeest appelée avec n + 1 = 2 mais comme la taille allouée est 4, il n'est pas nécessaire d'allouer plus de mémoire. La même chose se produit lorsque nous ajoutons 2 entiers supplémentaires: l.append(3), l.append(4). Le diagramme suivant montre ce que nous avons jusqu'à présent.

...

Insérer

Insérons un nouvel entier (5) à la position 1: l.insert(1,5)et regardons ce qui se passe en interne.

...

Pop

Quand vous ouvrez le dernier élément: l.pop(), listpop()est appelé. list_resizeest appelée à l'intérieur listpop()et si la nouvelle taille est inférieure à la moitié de la taille allouée, la liste est réduite.

Vous pouvez observer que l'emplacement 4 pointe toujours vers l'entier, mais l'important est la taille de la liste qui est maintenant de 4. Explorons un élément de plus. Dans list_resize(), size - 1 = 4 - 1 = 3 est inférieur à la moitié des emplacements alloués, donc la liste est réduite à 6 emplacements et la nouvelle taille de la liste est maintenant de 3.

Vous pouvez observer que les emplacements 3 et 4 pointent toujours vers des nombres entiers mais l'important est la taille de la liste qui est maintenant 3.

...

Retirer objet de liste Python a une méthode pour supprimer un élément spécifique: l.remove(5).

Selon la documentation ,

Les listes de Python sont en fait des tableaux de longueur variable, pas des listes liées de style Lisp.

Comme d'autres l'ont indiqué ci-dessus, les listes (lorsqu'elles sont sensiblement grandes) sont mises en œuvre en allouant une quantité fixe d'espace et, si cet espace doit se remplir, en allouant une plus grande quantité d'espace et en copiant les éléments.

Pour comprendre pourquoi la méthode est O (1) amortie, sans perte de généralité, supposons que nous ayons inséré a = 2 ^ n éléments, et nous devons maintenant doubler notre tableau à 2 ^ (n + 1). Cela signifie que nous faisons actuellement 2 ^ (n + 1) opérations. Dernière copie, nous avons fait 2 ^ n opérations. Avant cela, nous avons fait 2 ^ (n-1) ... jusqu'à 8,4,2,1. Maintenant, si nous additionnons ces derniers, nous obtenons 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O (a) insertions totales (c'est-à-dire O (1) temps amorti). De plus, il convient de noter que si la table permet les suppressions, la réduction de la table doit être effectuée à un facteur différent (par exemple 3x)

Une liste en Python est quelque chose comme un tableau, dans lequel vous pouvez stocker plusieurs valeurs. La liste est modifiable, ce qui signifie que vous pouvez la modifier. La chose la plus importante que vous devez savoir, lorsque nous créons une liste, Python crée automatiquement un reference_id pour cette variable de liste. Si vous le modifiez en affectant d'autres variables, la liste principale sera modifiée. Essayons avec un exemple:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

Nous ajoutons my_listmais notre liste principale a changé. La liste de ce moyen n'a pas été assignée comme une liste de copie assignée comme référence.

Dans CPython, la liste est implémentée en tant que tableau dynamique, et par conséquent, lorsque nous ajoutons à ce moment-là, non seulement une macro est ajoutée, mais un peu plus d'espace est alloué afin que chaque fois un nouvel espace ne soit pas ajouté.