La liste Python n'est pas une liste

Python est populaire, n'est-ce pas? L'une des forces de Python est la «liste». C'est une liste généreuse qui ne choisit pas le type d'objet à mettre à l'intérieur, mais comme le titre l'indique, ce n'est pas exactement une ** liste **. Cette fois, j'expliquerai cela avec le code source CPython.

• Dans cet article, nous ferons référence au code source de CPython, mais comme nous inclurons des explications à chaque fois, nous n'avons pas besoin d'avoir cette connaissance détaillée du langage C. Peut-être.

Tout d'abord, qu'est-ce qu'une liste?

[Liste](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%82%B9%E3%83%88_(%E6%8A%BD%E8%B1%A1%E3%] 83% 87% E3% 83% BC% E3% 82% BF% E5% 9E% 8B))) est un "conteneur de données ordonnées". En termes simples, les données sont classées et regroupées.

Je pense que la plupart des lecteurs de cet article sont Pythonista, donc j'aimerais l'implémenter en Python, mais comme Python ne peut pas implémenter une liste stricte, j'écrirai un programme de liste minimale en C ++. Je ne veux pas parler de C ++, donc je n'utilise pas de modèles et je fais une liste d'entiers.

class List {
private:
    int base;  //Maintenir la valeur
    int *next; //Adresse de la valeur suivante
public:
    /*
     *diverses méthodes telles que l'ajout
     */
}

Seulement ça. C'est facile? Il s'agit d'une ** liste unidirectionnelle **, et comme son nom l'indique, c'est une liste dont la référence est ** unidirectionnelle **. D'autre part, ** liste bidirectionnelle ** est une liste qui a l'adresse de la valeur précédente et peut être référencée en arrière. Si vous voulez faire référence à la valeur suivante, référez-vous simplement aux données à la position «suivante». En d'autres termes, cela peut être un peu différent de la liste que vous imaginez, mais ** les données ne sont pas dans une ligne en mémoire **.

Alors qu'est-ce qu'un tableau?

J'espère que vous avez trouvé la liste dans le chapitre précédent. Alors, qu'est-ce que array? La réponse simple est ** juste une chaîne de données **. Je vais vous l'expliquer car c'est un peu trompeur et imprécis.

Comme expliqué dans le chapitre précédent, la liste était ** une colonne de données contenant l'adresse des données suivantes **. Les tableaux, en revanche, sont des ** données disposées en mémoire **.

Laissez-moi vous donner un exemple simple. Supposons que vous ayez un tableau d'alphabets commençant par les données ʻA` à l'adresse 0 en mémoire. (La taille des données est de 1 pour plus de simplicité) Ensuite, il devrait y avoir «B» à côté de l'adresse 1 en mémoire, c'est-à-dire «A». À côté se trouve «C», à côté de lui «D», et ainsi de suite, le tableau contient ** toutes les données en ligne droite en mémoire sans exception **.

C'est la différence entre une liste et un tableau. Et à partir de là, regardons l'implémentation de Python list.

Enfin lire CPython

Comme vous le savez, CPython est le système de traitement officiel de Python implémenté en langage C. Le code source est actuellement (2020/04/10) dernier. (Mais le code source intégré ne change pas souvent, il n'est donc pas nécessaire de le faire correspondre étroitement.)

Où est la mise en œuvre de la liste

En regardant le code source de CPython, je pense que beaucoup de gens sont submergés par les différents répertoires. La définition d'objet de base se trouve dans ʻInclude / cpython / xxxobject.h`, alors jetons un œil là-bas. Ensuite, je pense qu'il y a une telle définition.

Include/cpython/listobject.h

typedef struct {
    PyObject_VAR_HEAD
    /* 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
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

Vous devez connaître PyObject pour lire le code source Python. Un PyObject est l'objet sous-jacent de tous les objets et tous les objets Python sont fournis en tant qu'extensions de cet objet. Donc ce code

• Définition de la structure PyListObject avec le tableau d'adresses de PyObject ʻob_item et la taille de mémoire acquise ʻallocated * Ce sera.

"Hmm? Je dis une liste, mais je n'ai pas l'adresse pour l'élément suivant!" C'est vrai.

** Les listes Python sont des tableaux. ** ** Répète ** Les listes Python sont des tableaux. ** **

"Mais qu'est-ce qui rend les séquences et les listes si heureuses et tristes?" Donc, à partir de là, je n'expliquerai pas la différence technique mais comment elle va changer concrètement.

Vitesse d'accès aléatoire

L'accès aléatoire, comme son nom l'indique, signifie accéder à des emplacements aléatoires dans une structure de données. Ici, nous allons présenter les différences d'accès aléatoire entre les tableaux et les listes.

Accès aléatoire au tableau

Si vous souhaitez effectuer un accès aléatoire sur un tableau, ajoutez simplement la position du début de l'élément auquel vous souhaitez accéder à l'adresse de début. Dans l'exemple précédent de l'alphabet, il y a «A» à l'adresse 0, donc pour accéder au 6ème «G», ajoutez simplement «6» à la position de «A», c'est-à-dire «0». Etant donné que le nom du tableau alphabétique est alphabet, un tel accès peut être écrit en langage C comme suit.

char *alphabet = {'A', 'B', 'C', ... , 'X', 'Y', 'Z'};
char a = *(alphabet + 0); //Une position est 0
char g = *(alphabet + 6); //La position G est 6

Et cela peut également être écrit en langage C.

char a = alphabet[0];
char g = alphabet[6];

N'est-ce pas une forme familière? Oui, c'est le même accès en indice que Python. La forme name [i] signifie ** obtenir l'élément avant ** name ʻi` **.

Que fait l'intérieur de Python lors d'un accès aléatoire? Jetons à nouveau un coup d'œil au code source de CPython. Jetons un coup d'œil à Include / cpython / listobject.h, qui est le même qu'avant.

Include/cpython/listobject.h

/* Cast argument to PyTupleObject* type. */
#define _PyList_CAST(op) (assert(PyList_Check(op)), (PyListObject *)(op))

#define PyList_GET_ITEM(op, i) (_PyList_CAST(op)->ob_item[i])
#define PyList_SET_ITEM(op, i, v) (_PyList_CAST(op)->ob_item[i] = (v))
#define PyList_GET_SIZE(op)    Py_SIZE(_PyList_CAST(op))
#define _PyList_ITEMS(op)      (_PyList_CAST(op)->ob_item)

La quatrième ligne définit une macro appelée PyList_GET_ITEM. En regardant le contenu, (_PyList_CAST (op) -> ob_item [i]) était! Accès abonné! Il s'est avéré qu'il est également accessible par des indices dans Python. À propos, une ligne ci-dessous est une macro qui attribue une valeur à la position spécifiée, mais l'accès se fait également avec des indices ici également.

Accès aléatoire à la liste

Alors, que se passe-t-il lorsque vous accédez au hasard à une liste? La liste n'a pas d'éléments dans une ligne, vous devez donc suivre les adresses des éléments suivants un par un. Répétez 6 fois pour «B» après «A», «C» après «B», et ainsi de suite, et vous atteindrez «G». C'est moins efficace qu'un tableau par tous les moyens.

Comme vous pouvez le voir, les ** listes ne sont pas bonnes pour l'accès aléatoire, les tableaux sont de bonnes structures de données ** et les tableaux sont adoptés en Python. (Je ne sais pas pourquoi je l'ai nommé liste)

finalement

J'espère que vous avez appris que l'implémentation interne de la list de Python est en fait un tableau, et ce qui en est reconnaissant. Si vous avez des questions, des questions ou des suggestions d'erreurs, n'hésitez pas à commenter. Si vous avez des questions, vous pouvez vous rendre sur Twitter. Merci beaucoup