Qu'est-ce qui fait que [* a] sur-utilise?

Apparemment, list(a)ne sur-utilise pas, sur- [x for x in a]utilise à certains moments et sur- [*a]utilise tout le temps ?

Voici les tailles n de 0 à 12 et les tailles résultantes en octets pour les trois méthodes:

0 56 56 56
1 64 88 88
2 72 88 96
3 80 88 104
4 88 88 112
5 96 120 120
6 104 120 128
7 112 120 136
8 120 120 152
9 128 184 184
10 136 184 192
11 144 184 200
12 152 184 208

Calculé comme ceci, reproductible sur repl.it , en utilisant Python 3. 8 :

from sys import getsizeof

for n in range(13):
    a = [None] * n
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]))

Donc comment ça fonctionne? Comment [*a]surutilisation? En fait, quel mécanisme utilise-t-il pour créer la liste des résultats à partir de l'entrée donnée? Utilise-t-il un itérateur aet utilise-t-il quelque chose comme list.append? Où est le code source?

( Colab avec les données et le code qui ont produit les images.)

Zoom avant sur n plus petit:

Zoom arrière sur un n plus grand:

[*a] fait en interne l'équivalent C de :

1. Faire un nouveau vide list
2. Appel newlist.extend(a)
3. Retours list.

Donc, si vous étendez votre test à:

from sys import getsizeof

for n in range(13):
    a = [None] * n
    l = []
    l.extend(a)
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]),
             getsizeof(l))

Essayez-le en ligne!

vous verrez les résultats pour getsizeof([*a])et l = []; l.extend(a); getsizeof(l)sont les mêmes.

C'est généralement la bonne chose à faire; lorsque extendvous vous attendez généralement à en ajouter plus tard, et de même pour le déballage généralisé, il est supposé que plusieurs éléments seront ajoutés les uns après les autres. [*a]n'est pas le cas normal; Python suppose qu'il y a plusieurs éléments ou itérables ajoutés au list( [*a, b, c, *d]), donc la surutilisation économise du travail dans le cas commun.

En revanche, un listconstruit à partir d'un seul, itérable prédéfini (avec list()) peut ne pas croître ou rétrécir pendant l'utilisation, et la surutilisation est prématurée jusqu'à preuve du contraire; Python a récemment corrigé un bogue qui faisait que le constructeur surutilisait même pour les entrées de taille connue .

En ce qui concerne les listcompréhensions, elles sont effectivement équivalentes à des appends répétés , vous voyez donc le résultat final du modèle de croissance de surutilisation normal lors de l'ajout d'un élément à la fois.

Pour être clair, rien de tout cela n'est une garantie de langue. C'est juste comment CPython l'implémente. La spécification du langage Python n'est généralement pas concernée par les schémas de croissance spécifiques de list(en plus de garantir les O(1) appends et pops amortis de la fin). Comme indiqué dans les commentaires, la mise en œuvre spécifique change à nouveau en 3.9; bien que cela n'affecte pas [*a], cela pourrait affecter d'autres cas où ce qui était "créer un temporaire tupled'éléments individuels puis extendavec le tuple" devient maintenant plusieurs applications de LIST_APPEND, qui peuvent changer lorsque la surutilisation se produit et quels nombres entrent dans le calcul.

Image complète de ce qui se passe, en s'appuyant sur les autres réponses et commentaires (en particulier la réponse de ShadowRanger , qui explique également pourquoi c'est fait comme ça).

Démontage montre qui BUILD_LIST_UNPACKs'utilise:

>>> import dis
>>> dis.dis('[*a]')
  1           0 LOAD_NAME                0 (a)
              2 BUILD_LIST_UNPACK        1
              4 RETURN_VALUE

Cela est géré dansceval.c , qui crée une liste vide et l'étend (avec a):

        case TARGET(BUILD_LIST_UNPACK): {
            ...
            PyObject *sum = PyList_New(0);
              ...
                none_val = _PyList_Extend((PyListObject *)sum, PEEK(i));

_PyList_Extend utilise list_extend :

_PyList_Extend(PyListObject *self, PyObject *iterable)
{
    return list_extend(self, iterable);
}

Qui appelle list_resizeavec la somme des tailles :

list_extend(PyListObject *self, PyObject *iterable)
    ...
        n = PySequence_Fast_GET_SIZE(iterable);
        ...
        m = Py_SIZE(self);
        ...
        if (list_resize(self, m + n) < 0) {

Et cela sur- utilise comme suit:

list_resize(PyListObject *self, Py_ssize_t newsize)
{
  ...
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Vérifions cela. Calculez le nombre attendu de spots avec la formule ci-dessus et calculez la taille d'octet attendue en le multipliant par 8 (comme j'utilise ici Python 64 bits) et en ajoutant la taille d'octet d'une liste vide (c'est-à-dire la surcharge constante d'un objet de liste) :

from sys import getsizeof
for n in range(13):
    a = [None] * n
    expected_spots = n + (n >> 3) + (3 if n < 9 else 6)
    expected_bytesize = getsizeof([]) + expected_spots * 8
    real_bytesize = getsizeof([*a])
    print(n,
          expected_bytesize,
          real_bytesize,
          real_bytesize == expected_bytesize)

Production:

0 80 56 False
1 88 88 True
2 96 96 True
3 104 104 True
4 112 112 True
5 120 120 True
6 128 128 True
7 136 136 True
8 152 152 True
9 184 184 True
10 192 192 True
11 200 200 True
12 208 208 True

Correspond à l'exception de n = 0, qui en list_extendfait des raccourcis , donc en fait cela correspond aussi:

        if (n == 0) {
            ...
            Py_RETURN_NONE;
        }
        ...
        if (list_resize(self, m + n) < 0) {

Ce seront des détails d'implémentation de l'interpréteur CPython, et peuvent donc ne pas être cohérents entre les autres interprètes.

Cela dit, vous pouvez voir où la compréhension et les list(a)comportements entrent en jeu ici:

https://github.com/python/cpython/blob/master/Objects/listobject.c#L36

Spécifiquement pour la compréhension:

 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
...

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

Juste en dessous de ces lignes, il y en a list_preallocate_exactqui est utilisé lors de l'appel list(a).