Как найти реализацию [::-1] (список обращений в Python) в исходном коде CPython

Question

Я пытался перевернуть список в Python. Есть много методов там и [::-1] кажется отличным! Но мне любопытно, как [::-1] готово? Какова временная сложность этого?

Я искал репозиторий CPython в github, но не смог найти никакой подсказки. Моя стратегия поиска заключалась в том, что я искал ключевое слово: :: в репо CPython. Так как есть :: в синтаксисе python, т.е. [::-1], может быть :: в исходном коде CPython, так что [::-1] может сослаться на это и делает задним ходом. Имеет ли это смысл?

Answer 1

list[...] использует индексацию или более точный синтаксис подписки, и [start:stop:step] это нарезка. Python 3 проходит slice() возражать против подписки звонка для таких случаев нет :: в исходном коде CPython, поскольку это не то, как синтаксический анализатор языка будет угрожать этой части. Нарезка нотации позволяет по умолчанию, пустой слот между в start:stop:step Части означает, что выбрано значение по умолчанию, и list[::-1] листья start а также stop по умолчанию (представлен None и значение шага установлено в -1,

Все это просто означает, что вы должны помнить, чтобы отделить синтаксис от операций. Вы можете проанализировать синтаксис, проанализировав его в абстрактном синтаксическом дереве или разобрав сгенерированный для него байт-код. Когда вы генерируете абстрактное синтаксическое дерево для list[::-1] вы увидите, что парсер отделяет часть слайса:

>>> import ast
>>> ast.dump(ast.parse('list[::-1]', '', 'eval').body)  # expression body only
"Subscript(value=Name(id='list', ctx=Load()), slice=Slice(lower=None, upper=None, step=UnaryOp(op=USub(), operand=Num(n=1))), ctx=Load())"

Итак Subscript() Синтаксический узел работает на имя list Проходя в ломтик.

Создание разборки для этой операции показывает используемый байт-код:

>>> dis.dis('list[::-1]')
  1           0 LOAD_NAME                0 (list)
              2 LOAD_CONST               0 (None)
              4 LOAD_CONST               0 (None)
              6 LOAD_CONST               1 (-1)
              8 BUILD_SLICE              3
             10 BINARY_SUBSCR
             12 RETURN_VALUE

Здесь BUILD_SLICE() Операция байт-кода берет три верхних элемента из стека LOAD_CONST операции с индексами 2, 4 и 6) для построения slice() объект, который затем передается list объект (следующий в стеке) с BINARY_SUBSCR, Этот последний байт-код является Subscript() операция в AST, и байт-коды 2-8 являются Slice() Объект в АСТ.

Имея байт-код в руках, вы можете перейти к циклу оценки байт-кода Python, чтобы увидеть, что на самом деле делают эти байт-коды. Я пропущу BUILD_SLICE Это просто создание простого slice() объект для хранения start, stop а также step ценности.

Сосредоточение на BINARY_SUBSCR код операции, мы находим:

TARGET(BINARY_SUBSCR) {
    PyObject *sub = POP();
    PyObject *container = TOP();
    PyObject *res = PyObject_GetItem(container, sub);
    Py_DECREF(container);
    Py_DECREF(sub);
    SET_TOP(res);
    if (res == NULL)
        goto error;
    DISPATCH();
}

Таким образом, Python берет вершину стека и помещает это в sub (это slice() объект здесь), и помещает list ссылка на container, а затем звонит PyObject_GetItem(container, sub), Вот и все. Следующий шаг - найти PyObject_GetItem(), Это определено в abstract.c и первое, что он делает, это проверяет, является ли объект типом отображения:

m = o->ob_type->tp_as_mapping;
if (m && m->mp_subscript) {
    PyObject *item = m->mp_subscript(o, key);
    assert((item != NULL) ^ (PyErr_Occurred() != NULL));
    return item;
}

->ob_type класс объекта (type(object) делает то же самое), и ->tp_as_mapping устанавливается, когда поддерживается протокол сопоставления. Если протокол сопоставления поддерживается, то m->mp_subscript(o, key); называется с o будучи объектом списка, и m быть определением поддержки отображения списка.

Списки поддерживают этот протокол, потому что только этот протокол поддерживает объекты среза (он также реализует протокол последовательности, но он принимает только целые числа и гораздо более старую, более ограниченную форму среза только с двумя индексами). Мы это видим list реализует протокол, ища tp_as_mapping запись в PyTypeObject PyList_Type определение типа:

PyTypeObject PyList_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    sizeof(PyListObject),
    0,
    // ...
    &list_as_mapping, /* tp_as_mapping */
    // ...
};

что указывает на list_as_mapping который определяется как

static PyMappingMethods list_as_mapping = {
    (lenfunc)list_length,
    (binaryfunc)list_subscript,
    (objobjargproc)list_ass_subscript
};

Итак, теперь мы знаем, где найти фактическую реализацию операции индексирования; эта реализация обрабатывается list_subscript() функция, которая использует PySlice_Check() проверить на slice() объекты, а затем просто создает новый объект списка и копирует индексы:

if (slicelength <= 0) {
    return PyList_New(0);
}
else if (step == 1) {
    return list_slice(self, start, stop);
}
else {
    result = list_new_prealloc(slicelength);
    if (!result) return NULL;


    src = self->ob_item;
    dest = ((PyListObject *)result)->ob_item;
    for (cur = start, i = 0; i < slicelength;
         cur += (size_t)step, i++) {
        it = src[cur];
        Py_INCREF(it);
        dest[i] = it;
    }
    Py_SIZE(result) = slicelength;
    return result;
}

Для непустого среза с размером шага -1, else ветка берется, где list_new_prealloc() создает новый, предварительно выделенный список для размещения всех индексов срезов, а затем for цикл, который использует cur += (size_t)step используется для создания индекса для копирования в новый список.

Для тебя list[::-1] срез, list объект передается в slice(None, None, -1) объект и list_subscript использует PySlice_Unpack() а также PySlice_AdjustIndices() функции, чтобы превратить это в бетон slicelength, start, stop а также step ценности; для негатива step а также start а также stop оба настроены на None конечный результат заключается в том, что slicelength установлен в len(list), start установлен в len(list) - 1, а также stop в -1,

Таким образом, влияние на вышеуказанное for цикл состоит в том, что все элементы, начиная с индекса len(list) - 1 и итерации до индекса 0, копируются в новый объект списка.

Так обращаясь с list[::-1] является операцией O(N) для длины N списка (это включает в себя предварительное распределение, которое занимает до O(N) времени, чтобы выделить память для ссылок на список нового списка).