len()函数的代价

Python内置函数的len()函数的成本是多less? (列表/元组/串/字典)

它是O(1) (恒定的时间,不取决于元素的实际长度 – 非常快),在你提到的每一个types,加上set和其他的如array.array

在这些数据types上调用len()是CPython中的 O(1),这是Python语言最常用的实现。 下面是一个表格的链接,它提供了CPython中许多不同function的algorithm复杂性:

TimeComplexity Python维基页面

下面的测量结果为经常使用的数据结构提供了证据len()为O(1)。

有关timeit的注释:当使用-s标志并将两个string传递给timeit ,第一个string仅执行一次,而不是定时的。

列表:

 $ 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 

所有这些物体都logging着它们自己的长度。 提取长度的时间很短(O(1)用大O符号表示),主要由粗略描述,用Python语言编写而不是C语言组成:在字典中查找“len”并将其分配给built_in len函数,它将查找对象的__len__方法并调用它…所需要做的就是return self.length