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

Question

我试图在python中反转列表.那里有很多方法,[::-1]看起来很棒!但我很好奇怎么[::-1]办？它的时间复杂度是多少？

我在github中搜索了CPython repo,但我找不到任何线索.我的搜索策略是我搜索了关键词:::CPython repo.由于存在::python语法,即CPython源代码中[::-1]可能存在::,因此[::-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()AST 中的对象.

有了字节码,您就可以转到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) - 10

因此list[::-1],对于列表的长度N,对O(N)操作进行反转(这包括预分配,其花费O(N)时间来为新列表的列表引用分配存储器).