Python 源码阅读: list 中的 _len_() 和 in

本文内容为博主阅读源码和官方文档以及其他相关文章后自己的理解, 不保证正确性。

昨天做 leetcode 的时候, 一道 K-Sum 的题目, 同样是 O(n²) 的复杂度, Java 能过, Python 超时, 我想可能是我调用了两次 _len_() 和加了一个 if not in 的判断的原因(最后发现是后者)。

阅读了一下 Python 的源码, list 的 __len__() 和 in 实现如下:

_len_()

有关 list 定义源码位置在 Python 目录下的 include/listobject.h 内, 代码如下:

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 是指向列表元素的指针数组, list[0] 即 ob_item[0], allocated 是列表的空间大小。在 PyObject_VAR_HEAD 中, 拥有一个 ob_size 变量。

下面是 Python 目录下的 include/object.h 中的相关代码:

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

ob_size 变量存储的就是对象的长度, 所以每次调用 _len_() 方法的时候, 返回的是一个已经存储好了的变量, 并没有对列表进行遍历操作, 时间复杂度是 O(1)。

这个不是造成题目超时的原因。但是从代码规范来讲的话, len(xxx) 这个变量我使用超过了两次, 应该先赋值给一个变量代替的, 只是刷题的时候没讲究这么多, 这也是题外话了。

in

既然 _len_() 方法复杂度是 O(1), 那么问题就应该出在 if xxx in xxx 时调用的 _contains_() 方法里了:

查看官方 CPython 源码, 在 cpython/Object/listobject.c 中有这几行代码:

static int
list_contains(PyListObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}

其中, Py_ssize_t 可在 PEP 353 中看到, 它是一个有符号的整形, 它所占字节数与编译器的 size_t 类型相同。

在 cpython/Object/object.c 可找到 PyObject_RichCompareBool 的定义代码:

int
PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
{
    PyObject *res;
    int ok;

    /* Quick result when objects are the same.
       Guarantees that identity implies equality. */
    if (v == w) {
        if (op == Py_EQ)
            return 1;
        else if (op == Py_NE)
            return 0;
    }

    res = PyObject_RichCompare(v, w, op);
    if (res == NULL)
        return -1;
    if (PyBool_Check(res))
        ok = (res == Py_True);
    else
        ok = PyObject_IsTrue(res);
    Py_DECREF(res);
    return ok;
}

PyObject_RichCompareBool 比较传入的 v 和 w 的值, 具体比较内容由 op 决定, op 必须是 Py_LT, Py_LE, Py_EQ, Py_NE, Py_GT, 或者 Py_GE 的其中一个, 分别对应 <, <=, ==, !=, >, 和 >=。在 list_contains(PyListObject *a, PyObject *el) 的 for 循环中, 传入的是 PyEQ, 也就是判断是否相等。整个函数的步骤如下:

如果 v 和 w 相等的话, 就根据 '==' 和 '!=' 返回相应的值; 否则调用 PyObject_RichCompare(PyObject *o1, PyObject *o2, int opid)。

PyObject_RichCompare 的源码同样在 cpython/Object/object.c 中:

PyObject *
PyObject_RichCompare(PyObject *v, PyObject *w, int op)
{
    PyObject *res;

    assert(Py_LT <= op && op <= Py_GE);
    if (v == NULL || w == NULL) {
        if (!PyErr_Occurred())
            PyErr_BadInternalCall();
        return NULL;
    }
    if (Py_EnterRecursiveCall(" in comparison"))
        return NULL;
    res = do_richcompare(v, w, op);
    Py_LeaveRecursiveCall();
    return res;
}

这个函数也是根据第 3 个参数比较传入的值, 成功时返回比较值, 失败则返回 NULL。

PyObject_RichCompare 执行完后调用 PyBool_Check 来验证 res 是否是一个 PyBool_Type 类型, 是的话判断布尔值是否为 Py_True, 否则调用 PyObject_IsTrue() 判断 res 对象是否为真, 为真返回 1 否则返回 0。

最后调用 Py_DECREF(res) 来减少 res 的 reference counts, 当 reference counts 减到 0 时将对象释放。这里要注意的是, 它并不会直接调用 free(), 而是通过 PyObject 中的对象 ob_type 的函数指针来调用 free()。

这样一来 if xxx in list 的过程就明了了, 它会使用线性查找, 遍历整个列表来判断值是否存在于列表中。时间复杂度为 O(n)。

虽然只是 O(n) 的复杂度, 但是在 K-sum 的题目中如果存入的单个解是一个数组的话, 每次调用 PyObject_RichCompareBool() 所耗的时间会更多, 这大概就是超时的原因吧。