对 Python 实现数组循环左移的思考

Mar 1, 2019 22:30 · 1457 words · 3 minute read Python

前几天偶然被问了一个小问题：python 实现数组循环左移。当时脱口而出 for 循环，这符合绝大多数程序员甚至是普通人的思维，实现循环左移必然要遍历列表，而实现遍历最简单粗暴的语法就是 for 循环。

事实上 for 循环一定是一种可行的方法：

arr = list(range(10))
out = []

for i in range(10):
    out.append(arr[i-(10-n)]) # n bit

print(out)

但这是一个好方法吗？恐怕不是。

因为漏掉了一个前提，python。事实上 python 有很多其他语言不具备的语法，也就是语言特色。循环左移 n 位，也就是将左边 n 个元素截取下来拼接到数组末尾，也就是 python 的切片功能。

def main():
    arr = list(range(10))
    print(left_shift(3, arr))

def left_shift(n, arr):
    return arr[n:]+arr[:n]

if __name__ == "__main__":
    main()

这样看起来也蛮优雅的，起码摒弃了万年不变的 for 循环。

但我们不禁要问，这是一个好方法吗？不知道，因为完全是 python 自己帮我们搞定的，这要探索一下 python 切片的底层实现。

https://www.python.org/downloads/source/ 提供了所有发行版的源码，这里就看最新的 Python3.7.2。

Objects/listobject.c 实现了 Python 中的 List 结构和一堆方法，也就是列表（第一行注释就说了）。

先来看看列表是怎么实现的：

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

大概可以猜一下，要自己实现一个动态的列表，首先需要存放元素的空间，还要有个变量来指示已经存放了多少个元素。**ob_item 看着就是一片内存，而 allocated 就是那个指示标了。

这里的 PyObject_VAR_HEAD 是一个宏定义，在 object.h 中可以挖到：

/* PyObject_VAR_HEAD defines the initial segment of all variable-size
 * container objects.  These end with a declaration of an array with 1
 * element, but enough space is malloc'ed so that the array actually
 * has room for ob_size elements.  Note that ob_size is an element count,
 * not necessarily a byte count.
 */
#define PyObject_VAR_HEAD      PyVarObject ob_base;

但是看到注释里写了，ob_size 是元素的个数，那之前关于 allocated 的猜测很有可能是错的，继续往下挖：

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

很清楚了，ob_base.ob_size 是变量部分的数量。

我们知道 python 有个内置的 len() 方法来计算列表中元素的个数。那是否可以找到这个方法的真身来验证 ob_base.ob_size

static Py_ssize_t
list_length(PyListObject *a)
{
    return Py_SIZE(a);
}

Py_SIZE(a) 还是一段宏定义，代表了 (((PyVarObject*)(ob))->ob_size)，结论成立。除此之外我们还知道了，厉害的 C 代码中总是充满了各种各样的宏定义。。。

下面再来找找切片，也就是 Slice。语法把一个列表切片 arr[start, end, step]，在源码 listobject.c 中找和它相似的代码段：

static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    len = ihigh - ilow;
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;

    src = a->ob_item + ilow;
    dest = np->ob_item;
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
}

PyObject *
PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    if (!PyList_Check(a)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    return list_slice((PyListObject *)a, ilow, ihigh);
}

下面是源码中切片的定义：

typedef struct {
    PyObject_HEAD
    PyObject *start, *stop, *step;      /* not NULL */
} PySliceObject;

看到 start、stop 和 step 都是指针，这里就有疑问了，start 和 stop 还能理解，为什么连 step 都是指针，按照 arr[start:end:step] 来看应该是个数字。但能感觉到，在 Python 解释器中执行列表切片语句绝对还有一步以上过渡的操作。

将 :step] 作为关键字搜索源码，找到了

PyDoc_STRVAR(slice_doc,
"slice(stop)\n\
slice(start, stop[, step])\n\
\n\
Create a slice object.  This is used for extended slicing (e.g. a[0:10:2]).");

这个函数很有意思，看起来像是把文档转换对应的函数，而 PyDoc_STRVAR 显然是宏定义：

/* Define macros for inline documentation. */
#define PyDoc_VAR(name) static char name[]
#define PyDoc_STRVAR(name,str) PyDoc_VAR(name) = PyDoc_STR(str)
#ifdef WITH_DOC_STRINGS
#define PyDoc_STR(str) str
#else
#define PyDoc_STR(str) ""
#endif

那我手动来翻译一遍：

static char slice_doc[] = "slice(stop)\n\
slice(start, stop[, step])\n\
\n\
Create a slice object.  This is used for extended slicing (e.g. a[0:10:2]).");

呃，这真的只是一条写死的字符串，估计是用来输出帮助信息的。

但是刚才的全局搜索还找到了 functions.rst 文档中的一些信息：

.. class:: slice(stop)
           slice(start, stop[, step])

   .. index:: single: Numerical Python

   Return a :term:`slice` object representing the set of indices specified by
   ``range(start, stop, step)``.  The *start* and *step* arguments default to
   ``None``.  Slice objects have read-only data attributes :attr:`~slice.start`,
   :attr:`~slice.stop` and :attr:`~slice.step` which merely return the argument
   values (or their default).  They have no other explicit functionality;
   however they are used by Numerical Python and other third party extensions.
   Slice objects are also generated when extended indexing syntax is used.  For
   example: ``a[start:stop:step]`` or ``a[start:stop, i]``.  See
   :func:`itertools.islice` for an alternate version that returns an iterator.

而找到 a[start:stop:step] 的实现方法才是这次思考的意义所在。

查看更多