Python内置len()函数的代价是什么?(列表/元组/字符串/字典)
在这些数据类型上调用len()是CPython中的O(1), CPython是Python语言的官方和最常见的实现。这里有一个表的链接,它提供了CPython中许多不同函数的算法复杂度:
TimeComplexity Python Wiki页面
下面的测量结果证明,对于常用的数据结构,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
字典(Dictionary -comprehension在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
Set (Set -comprehension在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
所有这些对象都记录自己的长度。提取长度的时间很短(大O表示法中的O(1)),主要由[粗略描述,用Python术语编写,而不是C术语]组成:在字典中查找“len”并将其分派给内置len函数,该函数将查找对象的__len__方法并调用它…它所要做的就是返回self。length
len是O(1),因为在RAM中,列表存储为表(一系列连续的地址)。要知道表何时停止,计算机需要两个东西:长度和起点。这就是为什么len()是O(1),计算机存储值,所以它只需要查找它。
推荐文章
- Numpy Max vs amax vs maximum
- 我应该在.gitignore文件中添加Django迁移文件吗?
- 每n行有熊猫
- 实例属性attribute_name定义在__init__之外
- 使嵌套JavaScript对象平放/不平放的最快方法
- 如何获取在Python中捕获的异常的名称?
- 第一次出现的值大于现有值的Numpy
- 大的Ө符号到底代表什么?
- 如何从Python函数中返回两个值?
- 前一个月的Python日期
- Python中方括号括起来的列表和圆括号括起来的列表有什么区别?
- Python日志记录不输出任何东西
- 堆与二叉搜索树(BST)
- 每n秒运行特定代码
- 给定一个数字数组,返回所有其他数字的乘积的数组(不除法)