Что вызывает [* a] перераспределение?

Question

Очевидно, list(a) не перераспределяет, [x for x in a] перераспределяет в некоторых точках, а [*a] перераспределяет все время ?

Здесь приведены размеры n от 0 до 12 и результирующие размеры в байтах для трех методов:

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

Рассчитано так, воспроизводится в repl.it , используя 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]))

Итак: Как это работает? Как [*a] перераспределяется? На самом деле, какой механизм он использует для создания списка результатов из заданного ввода? Использует ли он итератор для a и использует что-то вроде list.append? Где находится исходный код?

( Colab с данными и кодом , который создал изображения.)

Увеличение до меньшего n:

Уменьшение до большего n:

Answer 1

[*a] внутренне выполняет C эквивалент :

1. Создать новый, пустой list
2. Вызов newlist.extend(a)
3. Возвращает list.

Так что если вы расширите свой тест до:

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

Попробуйте онлайн!

вы увидите, что результаты для getsizeof([*a]) и l = []; l.extend(a); getsizeof(l) одинаковы.

Обычно это правильно; когда вы обычно ожидаете добавить больше позже, и аналогично для обобщенной распаковки, предполагается, что несколько вещей будут добавлены одна за другой. [*a] не нормальный случай; Python предполагает, что к list ([*a, b, c, *d]) добавляется несколько элементов или итераций, поэтому перераспределение сохраняет работу в общем случае.

В отличие от list, построенного из одного, повторяемое значение (с list()) может не расти или уменьшаться во время использования, а перераспределение является преждевременным, пока не доказано обратное; Python недавно исправил ошибку, из-за которой конструктор перераспределялся даже для входов с известным размером .

Что касается list пониманий, то они фактически эквивалентны повторным append с, таким образом, вы видите конечный результат нормальной схемы роста перераспределения при добавлении элемента за один раз.

Для ясности, ни одно из этого не является языковой гарантией. Просто CPython это реализует. Язык Python spe c, как правило, не имеет отношения к конкретным c моделям роста в list (кроме гарантии амортизированных O(1) append s и pop s с конца). Как отмечено в комментариях, реализация спецификации c снова меняется в 3.9; хотя это не повлияет на [*a], это может повлиять на другие случаи, когда то, что раньше было «созданием временного tuple отдельных элементов, а затем extend с tuple», теперь становится несколькими приложениями LIST_APPEND, который может измениться, когда происходит перераспределение и какие цифры go в расчете.

Answer 2

Полная картина того, что происходит , основанная на других ответах и ​​комментариях (особенно ответ ShadowRanger , который также объясняет , почему так сделано).

Разборка показывает, что BUILD_LIST_UNPACK используется:

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

Это обработано в ceval.c, который создает пустой список и расширяет его (с помощью a) :

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

_PyList_Extend использует list_extend:

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

Который вызывает list_resize с суммой размеров :

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

И это перераспределяет следующим образом:

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

Давайте проверим это. Вычислите ожидаемое количество пятен с помощью приведенной выше формулы и рассчитайте ожидаемый размер байта, умножив его на 8 (как я использую здесь 64-битный Python) и добавив размер байта пустого списка (то есть константу объекта списка накладные расходы):

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)

Вывод:

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

Совпадения, кроме n = 0, которые list_extend на самом деле ярлыки , так что на самом деле это тоже совпадает:

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

Answer 3

Это будут детали реализации интерпретатора CPython, и поэтому могут быть непоследовательными для других интерпретаторов.

Тем не менее, вы можете увидеть, откуда приходит понимание и list(a) поведение здесь:

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

Специально для понимания:

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

Чуть ниже этих строк находится list_preallocate_exact, который используется при вызове list(a).