What is the cost of len() function for Python built-ins? (list/tuple/string/dictionary)

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

优秀答案推荐

It's O(1) (constant time, not depending of actual length of the element - very fast) on every type you've mentioned, plus set and others such as array.array.

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

Calling len() on those data types is O(1) in CPython, the official and most common implementation of the Python language. Here's a link to a table that provides the algorithmic complexity of many different functions in CPython:

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

TimeComplexity Python Wiki Page

TimeComplexity Python维基页面

All those objects keep track of their own length. The time to extract the length is small (O(1) in big-O notation) and mostly consists of [rough description, written in Python terms, not C terms]: look up "len" in a dictionary and dispatch it to the built_in len function which will look up the object's __len__ method and call that ... all it has to do is return self.length

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

The below measurements provide evidence that len() is O(1) for oft-used data structures.

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

A note regarding timeit: When the -s flag is used and two strings are passed to timeit the first string is executed only once and is not timed.

关于timeit的一点注意：当使用-s标志并向timeit传递两个字符串时，第一个字符串只执行一次，并且不计时。

List:

$ 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

Tuple:

$ 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

String:

$ 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

Dictionary (dictionary-comprehension available in 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

Array:

$ 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

Set (set-comprehension available in 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

Deque:

$ 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

len is an O(1) because in your RAM, lists are stored as tables (series of contiguous addresses). To know when the table stops the computer needs two things : length and start point. That is why len() is a O(1), the computer stores the value, so it just needs to look it up.

LEN是一个O(1)，因为在您的RAM中，列表存储为表(一系列连续的地址)。要知道表何时停止，计算机需要两件事：长度和起始点。这就是为什么len()是O(1)，计算机存储这个值，所以它只需要查找它。

It is O(1) in CPython because length is derived from the size attribute on the Pyobject representing the list. See [1], [2] and [3] in that order:

在CPython中，它是O(1)，因为长度是从表示列表的PyObject上的Size属性派生出来的。按该顺序参见[1]、[2]和[3]：

[1]:

[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]:

[2]：

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

[3]

[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

[1]listiter_len

[2] PyList_GET_SIZE

[2]PyList_Get_Size

[3] Py_SIZE

[3]Py_Size