len()函数的成本

它是 O(1) (持续时间,不取决于元素的实际长度-非常快)针对您提到的每种类型,加上 set 以及其他如 array.array .

在这些数据类型上调用len()是 CPython 最常见的Python语言实现。下面是一个指向一个表的链接,该表提供了cpython中许多不同函数的算法复杂性:

TimeComplexity Python Wiki Page

以下测量结果证明 len() 对于经常使用的数据结构是O(1)。

关于 timeit 当 -s 使用标志并将两个字符串传递给 时计 第一个字符串只执行一次,不计时。

名单:

$ 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

字符串:

$ 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

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

所有这些物体都有自己的长度。提取长度的时间很短(o(1)用大o符号表示),主要由[粗略描述,用python术语写,而不是c术语]:在字典中查找“len”,然后将其发送到内置的“len”函数,该函数将查找对象的 __len__ 方法并调用它…它所要做的就是 return self.length

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