python中查找列表长度的O（1）背后的原因

Question

我正在用python浏览https://wiki.python.org/moin/TimeComplexity个列表。我知道python列表在内部是一个数组。但是列表的内部长度是O(1)。因为它需要遍历到列表的末尾，然后递增计数器并返回它。你知道吗

提前谢谢

Answer 1

TL；DR列表记录它们的长度。你知道吗

在CPython中，调用len([])调用Py_SIZEC宏，它只返回ob_size属性的值。你知道吗

https://github.com/python/cpython/blob/cda73a5af2ff064ca82140342b3158851d43868f/Objects/listobject.c#L438-L442

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

https://github.com/python/cpython/blob/9bdd2de84c1af55fbc006d3f892313623bd0195c/Include/object.h#L128

#define Py_SIZE(ob) (_PyVarObject_CAST(ob)->ob_size)