浏览量: 61 次浏览

Python内置类型性能分析

2020年1月18日 0 作者 Nie Hen

分析常用的list dict 内置操作的复杂度

测试算法运行时间

使用 timeit模块
timeit模块可以用来测试一小段Python代码的执行速度。

class timeit.Timer(stmt=’pass’, setup=’pass’, timer= < timer function>)

  1. Timer是测量小段代码执行速度的类。
  2. stmt参数是要测试的代码语句(statment);
  3. setup参数是运行代码时需要的设置;
  4. timer参数是一个定时器函数,与平台有关。

timeit.Timer.timeit(number=1000000)
Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数,默认为1000000次。方法返回执行代码的平均耗时,一个float类型的秒数。

示例代码

生成一个list的四种方式测试

def test1():
   l = []
   for i in range(1000):
      l = l + [i]
def test2():
   l = []
   for i in range(1000):
      l.append(i)
def test3():
   l = [i for i in range(1000)]
def test4():
   l = list(range(1000))

from timeit import Timer

t1 = Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "seconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "seconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "seconds")

# ('concat ', 1.7890608310699463, 'seconds')
# ('append ', 0.13796091079711914, 'seconds')
# ('comprehension ', 0.05671119689941406, 'seconds')
# ('list range ', 0.014147043228149414, 'seconds')

可以看到第一种方式生成list 使用的时间最长

最后一种直接生成的用时最短

list 在头部插入和尾部插入

from timeit import Timer
x = list(range(2000000))
pop_zero = Timer("x.append(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
x = list(range(2000000))
pop_end = Timer("x.insert(0,0)","from __main__ import x")
print("pop_end ",pop_end.timeit(number=1000), "seconds")

#pop_zero  0.0001515 seconds
#pop_end  2.8141455 seconds

list内置操作的时间复杂度

enter description here
操作 |作用 |用法 | 最坏时间复杂度
| — | — | — | — |
index |从列表中找出某个值第一个匹配项的索引位置 | list.index(obj) | O(1)
apend | 在列表末尾添加新的对象| list.append(obj) | O(1)
pop | 移除列表中的默认最后一个元素),并且返回该元素的值 | list.pop([index=-1]) | O(1)
pop | 移除列表中的一个元素 并且返回该元素的值 | list.pop([index]) | O(n)
insert | 将对象插入列表 | list.insert(index, obj) | O(n)
get slise | 获取指定范围的list[m:n]从位置m开始,截止到位置n(不包括n) | list[m:n] |O(k)
del slise | 将切片删除 | del list[m:n] | O(n)
reserve | 反向列表中元素 | list.reverse() | O(n)
sort | 对原列表进行排序 、 list.sort(cmp=None, key=None, reverse=False) |O(nlogn)

dict内置操作的时间复杂度

enter description here