Meilleure réponse
Contrairement à ce que leur nom lindique, les listes Python sont en fait des tableaux, un fait qui ne cesse de mennuyer (je ne « T comme les noms trompeurs). Plus précisément, ce sont des tableaux dynamiques avec une surallocation exponentielle, ce qui permet à un code comme celui-ci davoir une complexité linéaire:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Fait intéressant, la surallocation dans CPython est extrêmement conservateur, car il alloue 1,125 * new\_size + 6 (ou + 3 lorsque le tableau est inférieur à 9 éléments). Cette constante de 1,125 est plutôt rare, et comme je lai dit, elle est très conservatrice et semble donc supposer que la série de les appels dajout ne sont pas si courants. Les implémentations de tableaux dynamiques utilisent généralement des constantes telles que 2 ou 1.5 (je viens de vérifier limplémentation de std :: vector dans gcc / clang et il utilise 2, je semble me souvenir que limplémentation du compilateur Microsoft utilise 1.5 ). Je ne sais pas doù viennent les constantes + 3 et + 6, mais je suppose que celui qui a écrit cela a découvert que + 3 était la meilleure politique à adopter pour les tableaux minuscules, que + 6 était mieux pour les tableaux plutôt petits ( disons, moins de 100) et que cela n’a vraiment pas d’importance pour les grands tableaux, alors pourquoi ne pas le garder.
Des implémentations alternatives comme Jython et IronPython semblent utiliser la classe de tableau dynamique native sous-jacente (respectivement Java et C #) fournit, donc ils ont les mêmes caractéristiques de performance (les classes sous-jacentes précises semblent être ArrayList pour Jython et C # List pour IronPython).
Quelquun a demandé dans les commentaires comment cétait possible davoir des tableaux déléments de types hétérogènes ([1, « bonjour »] est une liste valide en Python). La réponse à cette question est que les tableaux stockent techniquement des pointeurs plutôt que les objets eux-mêmes, ce qui permet au tableau de ne contenir que des éléments dune taille spécifique. Avoir des pointeurs partout dans limplémentation sous-jacente est une caractéristique commune des langages à typage dynamique, et en fait de tout langage qui essaie de prétendre quil na pas de pointeurs.
Réponse
Comme le dit Adrien Lucas Ecoffet, les listes python ne sont rien dautre que des tableaux de longueur variable. Je fouille dans le code source de cpython, et en développant la macro, la structure de base est définie comme:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Jai élagué les commentaires ici, reportez-vous à loriginal code ici. 6c2e2de5ab8e Inclure / listobject.h
PyObject\_VAR\_HEAD contient un nombre de références et un identifiant de type. Donc, cest « un vecteur / tableau qui sur alloue. Le code permettant de redimensionner un tel tableau lorsquil est plein se trouve dans listobject.c . Il suralloue de la mémoire pour éviter dappeler list\_resize trop souvent. Le modèle de croissance de la liste est: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…
arguments: list object, new size
returns: 0 if OK, -1 if not
list\_resize:
new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
new\_allocated += newsize
resize ob\_item (list of pointers) to size new\_allocated
return 0
Pour voir toutes les méthodes répertoriées de mise en œuvre des listes Python list, y compris ajouter, insérer, supprimer, étendre et autres, veuillez consulter cet excellent article de blog.