如何在 CPython 源代码中找到 [::-1] 的实现（python 中的反转列表）

Question

我试图反转 python 中的列表。那里有很多方法，[::-1] 似乎是一个很棒的方法！不过很好奇[::-1]是怎么做到的？它的时间复杂度是多少？

我在 github 中搜索了 CPython 存储库，但找不到任何线索。我的搜索策略是在 CPython 存储库中搜索关键字：::。由于python语法中有::，即[::-1]，所以CPython源代码中可能有::，以便[::-1]可以引用它并做逆转。这有意义吗？

Answer 1

list[...] 正在使用索引，或更准确地说 subscription syntax, and [start:stop:step] is a slicing。 Python 3 在这种情况下将 slice() 对象传递给订阅调用，CPython 源代码中没有 ::，因为这不是语言解析器威胁的方式部分。切片表示法允许默认值，start:stop:step 部分之间的空槽表示选择了默认值，list[::-1] 将 start 和 stop 保留为默认值（由 [= 表示） 25=]，步长值设置为-1.

所有这些只是意味着您需要记住将语法与操作分开。您可以通过将其解析为抽象语法树或通过反汇编为其生成的字节码来分析语法。当你 generate an abstract syntax tree for 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进行操作，传入一个切片。

Producing a disassembly这个操作显示使用的字节码：

>>> 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() bytecode operation 从堆栈中取出前三个元素（通过 LOAD_CONST 操作放在索引 2、4 和 6 处）来构建一个 slice() 对象，它然后使用 BINARY_SUBSCR 传递给 list 对象（堆栈中的下一个对象）。最后一个字节码是 AST 中的 Subscript() 操作，字节码 2-8 是 AST 中的 Slice() 对象。

有了字节码，您就可以前往 Python bytecode evaluation loop 查看这些字节码实际上 做什么 。我将跳过 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 是对象 class（type(object) 也一样），->tp_as_mapping is set when the mapping protocol is supported。如果支持映射协议，则调用 m->mp_subscript(o, key);，o 是列表对象，m 是列表映射支持定义。

列表支持这个协议，因为只有这个协议支持切片对象（它实现了sequence protocol as well, but that only accepts integers and a much older, more limited form of slicing with just two indices). We can see that list implements the protocol by looking for a tp_as_mapping entry in the PyTypeObject PyList_Type type definition:

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() function 处理，它使用 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() 创建一个新的预分配列表以容纳所有切片索引，然后使用 cur += (size_t)step 的 for 循环用于生成要复制到新列表中的索引。

对于您的 list[::-1] 切片，list 对象在 slice(None, None, -1) 对象中传递，并且 list_subscript 使用 PySlice_Unpack() and PySlice_AdjustIndices() functions 将其转化为具体slicelength、start、stop 和 step 值；对于负 step 和 start 和 stop 都设置为 None 最终结果是 slicelength 设置为 len(list), start设置为len(list) - 1，stop设置为-1。

因此，对上述 for 循环的影响是 all 个元素，从索引 len(list) - 1 开始并迭代到索引 0, 被复制到新的列表对象中。

所以用 list[::-1] 反转是一个 O(N) 操作，对于列表的长度 N（这包括预分配，它最多需要 O(N) 时间来为列表引用分配内存新列表）。

如何在 CPython 源代码中找到 [::-1] 的实现（python 中的反转列表）

how to find the implementation of [::-1] ( reversing list in python ) in CPython source code

python

cpython

list

python-internals