introduction

J'utilise beaucoup Qiita, mais c'est mon premier article! Ravi de vous rencontrer!

Il existe de nombreux articles utiles sur Python, mais j'ai l'impression qu'il n'y a pas beaucoup d'articles qui touchent à l'implémentation interne de Python, donc je suis motivé pour pouvoir expliquer différentes structures de données en conjonction avec l'implémentation interne. Cette fois, j'écrirai sur la liste Python.

À propos de cet article

Ceci est un article sur le fonctionnement de la liste de Python. Mais il est impossible d'écrire comment fonctionnent toutes les méthodes de la liste, donc principalement

―― Quel type de structure de données est une liste? N'est-ce pas un tableau?

Quelle est l'implémentation interne du type liste?
Qu'est-ce qu'un tableau de longueur variable? Quelles sont les règles pour changer la taille?

J'ai écrit un article qui peut résoudre de telles questions.

Environnement d'exécution Version Python: 3.8.0
"Python" dans cet article fait référence à "CPython".

Public cible

--Les personnes qui ont les questions ci-dessus --Les personnes qui veulent en savoir un peu plus en lisant des livres d'introduction et des tutoriels Python

Les personnes qui veulent en savoir plus mais qui en ont assez de lire les documents officiels et le code cpython

Structure de données

Voyons quel type de structure de données est le type de liste de Python.

la revue

Qu'est-ce qu'une liste?

>>> x = [1,2,3]
>>> x.append(4)
>>> x
[1, 2, 3, 4]

C'est celui qui est familier.

x.sort()
x.append(element)
x.clear()
x.extend(element)
x.index(element)
x.insert(element)
x.pop()
x.remove(element)
x.reverse()

Il existe de nombreuses méthodes comme celle-ci (diverses).

Liste et tableau concaténés

C'est une histoire basique, donc si vous la connaissez, sautez-la.

Le tableau est

Sécuriser une zone continue en mémoire et y mettre des éléments --Il faut O (1) pour accéder à l'élément et O (N) pour insérer ou supprimer l'élément.

Liste concaténée (unidirectionnelle)

--Un nœud a un élément et un pointeur vers l'élément suivant --Il faut O (N) pour accéder à l'élément et O (1) pour insérer ou supprimer l'élément.

Il y a une fonctionnalité.

Structure de données de la liste

list est une structure de données standard et est l'un des types de séquence. Puisqu'elle s'appelle une liste, certaines personnes peuvent penser qu'elle est implémentée en utilisant une liste concaténée, mais les listes Python sont implémentées sous forme de tableaux de longueur variable (tableaux dynamiques). Donc ** la liste Python est un tableau **. Le nom est déroutant. ..

Une liste est un tableau contigu avec des références à d'autres objets. La structure en haut de la liste (PyListObject) a un pointeur et une longueur vers ce tableau. En regardant le code cpython réel (ʻInclude / cpython / listobject.h`) (commentaire omis)

`listobject.h`


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

C'est défini comme ça. La liste est de type «PyListObject» et les éléments de la liste sont de type «PyObject» et sont représentés en interne. (PyObject est le type de base pour tous les types d'objets Python.) ʻOb_item est un tableau de pointeurs vers les éléments de la liste, et ʻallocated est la taille allouée.

Untitled Diagram (2).png

Des éléments de différents types de données peuvent être dans la même liste, tant qu'ils sont «PyObject».

x = [1,"a",[1,2,3]]

Tableau de longueur variable

J'ai parlé de la liste de Python comme étant un tableau de longueur variable. Les tableaux de longueur variable redimensionnent le tableau référencé à mesure que des éléments sont ajoutés ou supprimés. Cependant, il ne modifie pas la taille du tableau à chaque fois. Il est bon de décider quand augmenter la taille et sa taille.

Redimensionner

Le processus de redimensionnement du tableau pour ajouter un nouvel élément est le suivant.

S'il n'y a pas d'espace libre, réservez un nouvel espace, copiez tous les éléments actuels et ajoutez un nouvel élément.

growth factor La quantité à augmenter lorsque le tableau est plein dépend du ** facteur de croissance ** (environ combien de fois la taille du tableau existant est multipliée). ** facteur de croissance ** dépend de la langue. (Par exemple, Python vaut 1,125, C vaut 2.)

Par exemple, lorsque le facteur de croissance est 2, la taille (capacité) sera la suivante lorsque des éléments sont ajoutés dans l'ordre au tableau.

Lors de la suppression d'un élément, la réduction est similaire à l'agrandissement.

Montant du calcul

L'opération pour développer le tableau copie tous les éléments, donc lorsque le nombre actuel d'éléments est k, la quantité de calcul est O (k).

Considérons maintenant que la quantité de calcul pour list.append (element) est O (1). Conclusion Compte tenu de la quantité de calcul, c'est O (1).

Lors de l'ajout de n éléments à un tableau vide dans l'ordre, si le facteur de croissance est 2, la quantité de calcul sera

\begin{align}
O(n+2+2^2+2^3+\cdots+2^{logn}) \\
= O(n+2\times2^{logn})\\
= O(n)
\end{align}

Par conséquent, la quantité de calcul lors de l'ajout de n éléments est O (n). Par conséquent, la quantité de calcul pour «list.append (élément)» est O (1).

Voir l'implémentation

Le facteur de croissance de Python est de 1,125, mais voyons comment le développer concrètement. Les opérations liées à list sont décrites dans ʻObjects / listobject.c`. La partie importante de la fonction à redimensionner est la suivante.

`listobject.c`


static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
}

    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Il est difficile de comprendre le calcul du masque dans la seconde moitié, n'est-ce pas?

Bref, multipliez la taille actuelle par $ \ frac {9} {8} $ et ajoutez un peu. Le facteur de croissance est certainement de 1,125.

Résumé

La liste Python est un tableau --list est en interne de type PyListObject et a des pointeurs vers PyObjects.
Le facteur de croissance Python est de 1,125

Structure de données Python et implémentation interne ~ Liste ~