367

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

4

5 回答 5

444

您提到的每种类型以及其他类型（set例如array.array.

于 2009-07-12T04:40:31.413 回答
158

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

时间复杂度 Python Wiki 页面

于 2009-07-12T04:59:44.900 回答
120

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

于 2009-07-12T06:17:13.090 回答
86

下面的测量为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
于 2009-07-12T05:34:28.293 回答
37

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

于 2018-09-02T07:02:29.810 回答