len() 函数的成本

问题描述：

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

解决方案 1：

对于您提到的每种类型，它都是O(1)（恒定时间，不依赖于元素的实际长度 - 非常快），再加上set其他类型，例如array.array。

解决方案 2：

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

时间复杂度 Python Wiki 页面

解决方案 3：

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

解决方案 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

解决方案 5：

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

解决方案 6：

它存在O(1)于 CPython 中，因为长度是从表示列表的 Pyobject 上的 size 属性派生出来的。请按顺序参阅 [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]列表长度

[2] PyList_GET_SIZE

[3]尺寸