51f4aacc6e13bcdaac76760f5e1bbbaa
Python 的数组实现

Python的数组实现

之前我们聊了许多关于Python固定对象,比如PyIntObjectPyFloatObject,这种类型的对象在创建完成之后属于不可变对象(当然引用计数等属性除外)。与之对应的,自然而然就有可变对象,今天我们就从Python自身的数组实现PyListObject来进行一番探讨。

PyListObject

老规矩,我们自然先来看一下其自身是如何定义的:

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

如果我们仔细对比上述数据结构和诸如PyIntObject的结构定义,会发现两者本质的不同点在于PyObject_VAR_HEADPyObject_HEAD,这也是不可变对象与可变对象的明显区分点。展开PyObject_VAR_HEAD我们会发现其包含了ob_size这个属性,代表当前数组(针对此文而言)容纳了多少PyObject *对象,而容纳的对象都是通过ob_item进行管理。此外,allocated这个属性代表了当前数组申请的空间个数,而ob_size代表实际个数。

PyListObject的遍历

在最早的文章中,我们提到过任何PyObject都具有三大类的方法簇:as_number, as_sequence, as_mappingPyListObject也不例外,在PyList_Type这个原型类中提供了对应的方法集合,如下所示:

PyTypeObject PyList_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    sizeof(PyListObject),
    0,
    (destructor)list_dealloc,                   /* tp_dealloc */
    (printfunc)list_print,                      /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_compare */
    (reprfunc)list_repr,                        /* tp_repr */
    0,                                          /* tp_as_number */
    &list_as_sequence,                          /* tp_as_sequence */
    &list_as_mapping,       
    ...
    // 迭代器访问
    (traverseproc)list_traverse,                /* tp_traverse */
    (inquiry)list_clear,                        /* tp_clear */
    list_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    list_iter,                                  /* tp_iter */

从中,我们不难看出,PyListObject并不支持as_number方法簇,因此无法将其作为数字对象进行操作。但是同样的,作为一种集合类对象,PyListObject比前文提到的整数、浮点数支持了对集合的访问as_sequence。我们就来分析下这块内容吧:

static PySequenceMethods list_as_sequence = {
    (lenfunc)list_length,                       /* sq_length */
    (binaryfunc)list_concat,                    /* sq_concat */
    (ssizeargfunc)list_repeat,                  /* sq_repeat */
    (ssizeargfunc)list_item,                    /* sq_item */
    (ssizessizeargfunc)list_slice,              /* sq_slice */
    (ssizeobjargproc)list_ass_item,             /* sq_ass_item */
    (ssizessizeobjargproc)list_ass_slice,       /* sq_ass_slice */
    (objobjproc)list_contains,                  /* sq_contains */
    (binaryfunc)list_inplace_concat,            /* sq_inplace_concat */
    (ssizeargfunc)list_inplace_repeat,          /* sq_inplace_repeat */
};

as_sequence中定义了集合操作需要的一些基本算子,包含求长度、合并、重复、赋值(区间赋值)等等,其中比较让我感兴趣的就是list_repeat函数,他的作用就是将当前的数组中的值重复N次,构造一个全新的数组:

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
    if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);
    if (np == NULL)
        return NULL;

    items = np->ob_item;
    if (Py_SIZE(a) == 1) {
        elem = a->ob_item[0];
        for (i = 0; i < n; i++) {
            items[i] = elem;
            Py_INCREF(elem);
        }
        return (PyObject *) np;
    }
    p = np->ob_item;
    items = a->ob_item;
    for (i = 0; i < n; i++) {
        for (j = 0; j < Py_SIZE(a); j++) {
            *p = items[j];
            Py_INCREF(*p);
            p++;
top Created with Sketch.