len()函数的成本

Question

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

Answer 1

它是O(1)(恒定时间,不依赖于元素的实际长度 - 非常快)在你提到的每种类型,以及set其他类型如array.array.

Answer 2

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

TimeComplexity Python Wiki页面

Answer 3

所有这些对象都跟踪自己的长度.提取长度的时间很短(大O符号中的O(1))并且主要由[粗略描述,用Python术语编写,而不是C术语]组成:在字典中查找"len"并将其发送到built_in len函数,它将查找对象的__len__方法并调用它......所有它必须做的就是return self.length

Answer 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

Answer 5

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