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

136

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

Размеры до n = 100

Вот размеры 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 = 40

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

Размеры до n = 1000

Стефан Почманн
источник
1
Между тем, при расширении ваших тестовых случаев может показаться, что понимание списка ведет себя как написание цикла и добавление каждого элемента в список, тогда как, по- [*a]видимому, ведет себя как использование extendв пустом списке.
jdehesa
4
Это может помочь посмотреть на байт-код, сгенерированный для каждого. list(a)работает полностью в C; он может распределять внутренний буферный узел по узлам, когда он повторяется a. [x for x in a]просто использует LIST_APPENDмного, поэтому он следует обычному шаблону «немного перераспределить, перераспределить при необходимости» обычного списка. [*a]использует BUILD_LIST_UNPACK, что ... я не знаю, что это делает, за исключением, по-видимому, чрезмерного распределения все время :)
chepner
2
Кроме того, в Python 3.7 кажется, что list(a)и [*a]они идентичны, и оба слишком распределены по сравнению с [x for x in a], так что ... sys.getsizeofвозможно, это не тот инструмент, который можно использовать здесь.
Чепнер
7
@chepner Я думаю, что sys.getsizeofэто правильный инструмент, он просто показывает, что list(a)раньше перераспределять. Фактически, что нового в Python 3.8 упоминает это: «Конструктор списка не перераспределяет [...]» .
Стефан Почманн
5
@chepner: это ошибка, исправленная в 3.8 ; конструктор не должен перераспределять.
ShadowRanger

Ответы:

81

[*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)одинаковы.

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

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

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

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

ShadowRanger
источник
4
@StefanPochmann: я читал код раньше (вот почему я это уже знал). Это обработчик байтового кодаBUILD_LIST_UNPACK , он использует _PyList_Extendкак эквивалент вызова C extend(просто напрямую, а не путем поиска метода). Они соединили его с дорожками для сборки tupleс распаковкой; tupleНе нужно перераспределять красиво для частичной сборки, поэтому они всегда распаковываются в list(чтобы извлечь выгоду из перераспределения) и конвертируются tupleв конец, когда это то, что было запрошено.
ShadowRanger
4
Обратите внимание , что это , по- видимому изменение в 3.9 , где строительство делаются с отдельными байткодами ( BUILD_LIST, LIST_EXTENDдля каждой вещи распаковывать, LIST_APPENDдля отдельных элементов), вместо загрузки всего на стеке перед сборкой все listс одной командой байт - коды (это позволяет компилятор для выполнения оптимизаций , что команда все-в-одном не позволяет, как осуществление , [*a, b, *c]как LIST_EXTEND, LIST_APPEND, LIST_EXTENDж / о необходимости завернуть bв одно , tupleчтобы соответствовать требованиям BUILD_LIST_UNPACK).
ShadowRanger
18

Полная картина того, что происходит, основываясь на других ответах и ​​комментариях (особенно ответ 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) {
Стефан Почманн
источник
8

Они будут деталями реализации интерпретатора 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).

похотливый
источник
1
[*a]не добавляет отдельные элементы по одному. У него есть собственный выделенный байт-код, который выполняет массовую вставку через extend.
ShadowRanger
Попался - я думаю, я не слишком много копал в этом. Удален раздел[*a]
Рэнди