翻译 - Python切片的实现原理

[TOC]

原文链接: How is slicing implemented in python? 来自 Quora 作者: Vladislav Zorov 翻译理由: 作者在分析切片的原理的同时, 也很详细的说明了如何去看源码, 虽然只有27个赞…

问题: Python 是怎么实现切片的?

答案:

查看源码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


In [13]: from dis import dis

In [14]: dis("lst[::-1]")
  1           0 LOAD_NAME                0 (lst)
              3 LOAD_CONST               0 (None)
              6 LOAD_CONST               0 (None)
              9 LOAD_CONST               2 (-1)
             12 BUILD_SLICE              3
             15 BINARY_SUBSCR
             16 RETURN_VALUE

dis 模块支持通过反汇编分析CPython bytecode。反汇编字节码的意思就是接收这一系列的字节，然后打印出我们能够理解的字符(opcodes)。

dis.dis(x=None, *, file=None) 拆卸 x 对象。 x 可以表示模块，类，方法，函数，生成器，代码对象，源代码字符串或原始字节码的字节序列。对于模块，它会拆散所有函数。对于一个类，它反汇编所有的方法（包括类和静态方法）。对于代码对象或原始字节码序列，每个字节码指令打印一行。字符串首先被编译为使用 compile() 内置函数代码对象，然后被反汇编。如果没有提供对象，则此函数将反汇编最后一个回溯。

LOAD_NAME 和 LOAD_CONST 只不过是将一些常量压栈, 有意思的操作码(opcodes)是BUILD_SLICE 和 BINARY_SUBSCR

我们去 CPython 在 GitHub 的镜像库上搜索关键字 BUILD_SLICE python/cpython - 发现 “compile.c” 和 “ceval.c” 比较因吹思艇; “compile.c” 中是声明, “ceval.c” 中是执行, 我们要看就是后者

我们发现在TARGET(BUILD_SLICE)里调用了PySlice_New, 再次返回之前的搜索页面搜索它, 于是我们在 sliceobject.c中找到这货, 不过有点意思的是, 看起来只是一个 “helper class” 来处理索引, 检查 stop 参数是否超出最大值, 切片长度非负等等

所以我们再看看BINARY_SUBSCR, 这个看起来是由下标a[n]触发, 下标为栈最顶值, 用于栈次顶值, 所以切片对象是通过下标组成列表对象(BINARY_SUBSCR 将会 pop 3 个LOAD_CONST, 代码位于 “ceval.c”)

回到之前的 “sliceobject.c”, listobject.c-别被代码量吓着了, 其实挺容易找到这个函数

1
2


static PyObject *
list_subscript(PyListObject* self, PyObject* item)

在这个函数里边, 有正常的索引获取, 也有我们要找的: 切片

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


else if (PySlice_Check(item)) {
    Py_ssize_t start, stop, step, slicelength, cur, i;
    PyObject* result;
    PyObject* it;
    PyObject **src, **dest;

    if (PySlice_GetIndicesEx(item, Py_SIZE(self),
        &start, &stop, &step, &slicelength) < 0) {
        return NULL;
    }

    if (slicelength <= 0) {
        return PyList_New(0);
    }
    else if (step == 1) {
        return list_slice(self, start, stop);
    }
    else {
        result = PyList_New(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;
        }

        return result;
    }
}

当步长为 1 (step=1)时的循环, 就很像我们要找的了

so, 别的先不说, 切片列表其实就是个循环. 不过是用 C 循环的, 切片速度比你自己用 Python list.append 循环快多了

对于其他类型可以支持下标切片的对象, 可能原理会有所不同; 例如 range 与 list 就有很大的区别

1
2
3
4
5
6
7
8


>>> list(range(5))
[0, 1, 2, 3, 4]
>>> list(range(5))[::-1]
[4, 3, 2, 1, 0]
>>> range(5)
range(0, 5)
>>> range(5)[::-1]
range(4, -1, -1)

range 像是重新计算了起始位置, 步长, 终止位置(start, step, end), 但是啥都没干, 因为已经切过了…(注: Python3 的 range, 2 里边是 xrange)

补充拓展

caval.c 中的 BINARY_SUBSCR, POP() 就是 LOAD_CONST 的那个栈 pop, PyObject_GetItem(dic, key)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


 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();
 }

实现一个 python3 里的 range

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


 class Myrange:
     def __init__(self, num):
         self.i = 0
         self.num = num
    
     def __iter__(self):
         return self
    
     def __next__(self):
         if self.i < self.num:
             i = self.i
             self.i += 1
             return i
         else:
             raise StopIteration() 

有个缺陷就是Myrange是一个迭代器, 而Python3 的range不是, 只是一个惰性的可迭代对象

1
2
3
4
5
6
7
8
9


In [20]: import collections
In [22]: isinstance(Myrange, collections.Iterator)
Out[22]: False

In [24]: isinstance(Myrange(5), collections.Iterator)
Out[24]: True

In [31]: iter(range(5))
Out[31]: <range_iterator at 0x10440f030>

使用 next 无法调用 range

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


In [36]: a = Myrange(5)
In [37]: next(a)
Out[37]: 0

In [38]: next(a)
Out[38]: 1

In [39]: next(a)
Out[39]: 2

In [40]: next(range)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-40-cae19a709515> in <module>()
----> 1 next(range)

TypeError: 'type' object is not an iterator

range 是序列(列表，元组和字符串)，但并不包含任何内存中的内容

1
2
3
4


In [41]: from collections import Sequence

In [42]: isinstance(range(5), Sequence)
Out[42]: True

Contents

问题: Python 是怎么实现切片的?

答案:

补充拓展