python之在 python 中查找 List 长度的 O(1) 背后的原因

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

提前致谢

请您参考如下方法:

TL;DR 列表跟踪它们的长度。

在 CPython 中，调用 len([]) 会调用 Py_SIZE C 宏，它只返回 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)