从 Python 源码看切片实现

从 Python 源码看切片实现

s="abcde",则 s[6:2:-1] 输出啥?s[6:-2:-1]s[2:-6:-1] 等等呢?

因为从 OI 退役了,轻雨酱不得不面对一些机械性的考试,比如什么 Python 切片操作的细节,整得我云里雾里。

但还好编程不比有机合成,一台小小的电脑也能探究底层机理,于是,就趁课余时间偷偷看了下这玩意的底层实现,好歹算知其所以然了。

Warning!

本文的目标读者是新高考信息技术选考生,因此多少难免疏漏之处,欢迎在下方评论轻喷。

源码

此处以 CPython 为例,其先会将 bulitin 的 slice 对象转换为 C 对象。

一个 slice 对象只有三个参数 startstopstep,当需要对指定序列进行截取时,我们还会得到序列的长度 lengthpermalink

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
33
34
35
36
37
38
39
PyObject *
PySlice_New(PyObject *start, PyObject *stop, PyObject *step)
{
if (step == NULL) {
step = Py_None;
}
if (start == NULL) {
start = Py_None;
}
if (stop == NULL) {
stop = Py_None;
}

PyInterpreterState *interp = _PyInterpreterState_GET();
PySliceObject *obj;

// CPython 会缓存一个 slice 对象,避免反复 alloc
if (interp->slice_cache != NULL) {
obj = interp->slice_cache;
interp->slice_cache = NULL;
_Py_NewReference((PyObject *)obj);
}
else {
obj = PyObject_GC_New(PySliceObject, &PySlice_Type);
if (obj == NULL) {
return NULL;
}
}

Py_INCREF(step);
obj->step = step;
Py_INCREF(start);
obj->start = start;
Py_INCREF(stop);
obj->stop = stop;

_PyObject_GC_TRACK(obj);
return (PyObject *) obj;
}

因为 slice 的三个参数都可能是 $\texttt{None}$,需要对他们进行处理。

同时,对于不合法的情况,如 step 为 $0$,应抛出异常。permalink

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
33
34
35
36
37
38
39
40
int
PySlice_Unpack(PyObject *_r,
Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step)
{
PySliceObject *r = (PySliceObject*)_r;
Py_BUILD_ASSERT(PY_SSIZE_T_MIN + 1 <= -PY_SSIZE_T_MAX);

if (r->step == Py_None) {
*step = 1;
}
else {
if (!_PyEval_SliceIndex(r->step, step)) return -1;

if (*step == 0) {
PyErr_SetString(PyExc_ValueError,
"slice step cannot be zero");
return -1;
}

if (*step < -PY_SSIZE_T_MAX)
*step = -PY_SSIZE_T_MAX;
}

// 该处对 start 或 stop 为 Py_None 的处理可以理解为根据 step 设为正/负无限
if (r->start == Py_None) {
*start = *step < 0 ? PY_SSIZE_T_MAX : 0;
}
else {
if (!_PyEval_SliceIndex(r->start, start)) return -1;
}

if (r->stop == Py_None) {
*stop = *step < 0 ? PY_SSIZE_T_MIN : PY_SSIZE_T_MAX;
}
else {
if (!_PyEval_SliceIndex(r->stop, stop)) return -1;
}

return 0;
}

有了确切的 startstopstep,具体的切片操作因为需要提供不同的方法,核心部分会实现多次。

我们取内容最精简的 PySlice_AdjustIndices 理解其本质即可,其作用为给定序列长度 length 和 slice の三参数,获得截片长度。

正如其源码所言,this is harder to get right than you might think。permalink

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Py_ssize_t
PySlice_AdjustIndices(Py_ssize_t length,
Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t step)
{
/* this is harder to get right than you might think */

assert(step != 0);
assert(step >= -PY_SSIZE_T_MAX);

if (*start < 0) {
// 该段将 [-length, 0) 范围的下标移到 [0, length)
// 以解决形如 slice(-1,...,...) 的问题
*start += length;

// 如果此时 start < 0,说明我们的参数在合法的下标区间左侧,我们只需将其移到边界即可,需要注意我们的区间是左闭右开的
if (*start < 0) {
*start = (step < 0) ? -1 : 0;
}
}
else if (*start >= length) {
// 如果此时 start >= length,说明我们的参数在合法的下标区间右侧,那么同理
*start = (step < 0) ? length - 1 : length;
}

if (*stop < 0) {
*stop += length;
if (*stop < 0) {
*stop = (step < 0) ? -1 : 0;
}
}
else if (*stop >= length) {
*stop = (step < 0) ? length - 1 : length;
}

// 经过以上的处理,我们已经保证了区间的起始和结束位置(双闭)都在 [0, length) 范围内
// 通过简单的小学数学(校门口种树问题),可以直接计算
if (step < 0) {
if (*stop < *start) {
return (*start - *stop - 1) / (-step) + 1;
}
}
else {
if (*start < *stop) {
return (*stop - *start - 1) / step + 1;
}
}
return 0;
}

结论

简短总结一下怎么在纸上手玩:

  • Step 1:处理默认值,如果 startstop 为 $\texttt{None}$,设为正 / 负无穷大;如果 step 为 $\texttt{None}$,设为 $1$
  • Step 2:平移下标,Python 中 $[0, \texttt{length})$ 一段的下标等价于 $[-\texttt{length}, 0)$,注意这样的平移只有一次
  • Step 3:移动边界,如果 startstop 在边界 $[0, \texttt{length})$ 之外,则应移动到边界内,注意考虑区间左闭右开的细节
  • Step 4:简单统计,剩下就是从 start 开始步长为 step 数到 stop 的过程了,二年级小朋友都会数

理解这玩意儿就不怕被出题人恶心人了!另外,为了方便同学(指线下)理解,也参照着写了个 Python 的实现,可见此处:@github/senior-school-technology-lesson/my_slice