len() 函数的成本

Question

len() 的成本是多少Python 内置函数？ （列表/元组/字符串/字典）

Answer 1

对于您提到的每种类型，加上 set 和其他例如 <代码>数组.数组。

Answer 2

在 CPython 中，对这些数据类型调用 len() 的时间复杂度为 O(1) ，Python 语言的官方且最常见的实现。 以下是一个表的链接，该表提供了 CPython 中许多不同函数的算法复杂性：

TimeComplexity Python Wiki 页面

Answer 3

所有这些物体都会记录自己的长度。 提取长度的时间很小（大 O 表示法中的 O(1)），并且主要由 [粗略描述，用 Python 术语编写，而不是 C 术语] 组成：在字典中查找“len”并将其分派到内置 len 函数将查找对象的 __len__ 方法并调用该方法...它所要做的就是返回 self.length

Answer 4

以下测量结果证明，对于常用的数据结构，len() 的复杂度为 O(1)。

关于 timeit 的注意事项：当使用 -s 标志并将两个字符串传递给 timeit 时，第一个字符串仅执行一次，并且不会执行定时的。

列表：

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

元组：

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

字符串：

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

字典（字典理解在 2.7+ 中可用）：

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

数组：

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

集合（集合理解在 2.7+ 中可用）：

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

双端队列：

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

Answer 5

len 的复杂度为 O(1)，因为在 RAM 中，列表存储为表格（一系列连续的地址）。 要知道桌子何时停止，计算机需要两件事：长度和起点。 这就是为什么 len() 的时间复杂度为 O(1)，计算机存储该值，因此只需要查找它即可。

Answer 6

在 CPython 中，它的复杂度为 O(1)，因为长度是从表示列表的 Pyobject 上的大小属性派生的。 按顺序参见 [1]、[2] 和 [3]：

[1]:

static PyObject *
listiter_len(_PyListIterObject *it, PyObject *Py_UNUSED(ignored))
{
    Py_ssize_t len;
    if (it->it_seq) {
        len = PyList_GET_SIZE(it->it_seq) - it->it_index;
        if (len >= 0)
            return PyLong_FromSsize_t(len);
    }
    return PyLong_FromLong(0);
}

[2]:

static inline Py_ssize_t PyList_GET_SIZE(PyObject *op) {
    PyListObject *list = _PyList_CAST(op);
    return Py_SIZE(list);
}

[3]

static inline Py_ssize_t Py_SIZE(PyObject *ob) {
    assert(ob->ob_type != &PyLong_Type);
    assert(ob->ob_type != &PyBool_Type);
    PyVarObject *var_ob = _PyVarObject_CAST(ob);
    return var_ob->ob_size;
}

[1] listiter_len

[2] PyList_GET_SIZE

[3] Py_SIZE