¿Qué causa que [* a] se sobreasigne?

Al parecer, list(a)¿no se sobreasigna, se [x for x in a]sobreasigna en algunos puntos y se [*a]sobreasigna todo el tiempo ?

Estos son los tamaños n de 0 a 12 y los tamaños resultantes en bytes para los tres métodos:

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

Calculado así, reproducible en repl.it , usando 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]))

¿Entonces, cómo funciona esto? ¿Cómo se [*a]sobreasigna? En realidad, ¿qué mecanismo utiliza para crear la lista de resultados a partir de la entrada dada? ¿Utiliza un iterador ay usa algo como list.append? ¿Dónde está el código fuente?

( Colab con datos y código que produjeron las imágenes).

Acercamiento a n menor:

Alejar a n mayor:

[*a] está haciendo internamente el equivalente en C de :

1. Hacer un nuevo, vacío list
2. Llamada newlist.extend(a)
3. Las devoluciones list.

Entonces, si expande su prueba a:

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))

Pruébalo en línea!

verá los resultados getsizeof([*a])y l = []; l.extend(a); getsizeof(l)son los mismos.

Esto suele ser lo correcto; cuando extendgeneralmente espera agregar más más tarde, y de manera similar para el desempaque generalizado, se supone que se agregarán varias cosas una tras otra. [*a]no es el caso normal; Python asume que hay múltiples elementos o iterables que se agregan a list( [*a, b, c, *d]), por lo que la sobreasignación ahorra trabajo en el caso común.

Por el contrario, un listconstruido a partir de un único iterativo preestablecido (con list()) puede no crecer o encogerse durante el uso, y la sobreasignación es prematura hasta que se demuestre lo contrario; Python recientemente corrigió un error que hacía que el constructor se sobreasignara incluso para entradas con un tamaño conocido .

En cuanto a las listcomprensiones, son efectivamente equivalentes a appends repetidas , por lo que está viendo el resultado final del patrón de crecimiento de sobreasignación normal al agregar un elemento a la vez.

Para ser claros, nada de esto es una garantía de idioma. Así es como CPython lo implementa. La especificación de lenguaje Python es generalmente despreocupado con patrones de crecimiento específicos en list(aparte de garantizar amortizado O(1) appends y popS desde el final). Como se señaló en los comentarios, la implementación específica cambia nuevamente en 3.9; Si bien no afectará [*a], podría afectar otros casos en los que lo que solía ser "construir un elemento temporal tuplede elementos individuales y luego extendcon el tuple" ahora se convierte en múltiples aplicaciones de LIST_APPEND, que pueden cambiar cuando se produce la sobreasignación y qué números entran en el cálculo.

Imagen completa de lo que sucede, basándose en las otras respuestas y comentarios (especialmente la respuesta de ShadowRanger , que también explica por qué se hace así).

Desmontaje muestra que BUILD_LIST_UNPACKse acostumbra:

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

Eso se maneja enceval.c , lo que construye una lista vacía y la extiende (con a):

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

_PyList_Extend usos list_extend :

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

Que llama list_resizecon la suma de los tamaños :

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

Y eso se sobreasigna de la siguiente manera:

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

Vamos a ver eso. Calcule el número esperado de puntos con la fórmula anterior y calcule el tamaño de byte esperado multiplicándolo con 8 (ya que estoy usando Python de 64 bits aquí) y agregando el tamaño de byte de una lista vacía (es decir, la sobrecarga constante de un objeto de lista) :

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)

Salida:

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

Coincide con excepción de n = 0, que en list_extendrealidad atajos , por lo que también coincide:

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

Estos serán detalles de implementación del intérprete de CPython y, por lo tanto, pueden no ser coherentes con otros intérpretes.

Dicho esto, puedes ver dónde list(a)entran aquí la comprensión y los comportamientos:

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

Específicamente para la comprensión:

 * 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);

Justo debajo de esas líneas, hay una list_preallocate_exactque se usa al llamar list(a).