Python列表类型性能测试以及内置字典操作的时间复杂度分析

timeit模块

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

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

Timer是测量小段代码执行速度的类。
stmt参数是要测试的代码语句（statment）；
setup参数是运行代码时需要的设置；
timer参数是一个定时器函数，与平台有关。

timeit.Timer.timeit(number=1000000)

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

List的操作测试

import timeitdeftest1():'''
		通过append方法添加数据
	'''
    li=[]for iinrange(10000):
        li.append(i)deftest5():'''
		通过insert方法添加数据
	'''
    li=[]for iinrange(10000):
        li.insert(0,i)deftest2():'''
		通过列表相加添加数据
	'''
    li=[]for iinrange(10000):
        li= li+[i]deftest3():'''
		通过推导式添加数据
	'''
    li=[ifor iinrange(10000)]deftest4():'''
		通过list方法添加数据
	'''
    li=list(range(10000))'''
    因为timeit测试是另外开一个模块测试，所以第二参数中，需要导入要测试函数
    当前模块的模块名称为= __main__
'''
timer1= timeit.Timer('test1()','from __main__ import test1')
timer5= timeit.Timer('test5()','from __main__ import test5')
timer2= timeit.Timer('test2()','from __main__ import test2')
timer3= timeit.Timer('test3()','from __main__ import test3')
timer4= timeit.Timer('test4()','from __main__ import test4')# 测试100次print('append :%f'%timer1.timeit(number=100))print('insert :%f'%timer5.timeit(number=100))print('[]+[] :%f'%timer2.timeit(number=100))print('[i for] :%f'%timer3.timeit(number=100))print('list() :%f'%timer4.timeit(number=100))''' 输出
append :0.171303
insert :2.461631
[]+[] :15.466849
[i for] :0.049168
list() :0.029723
'''

输出结果：

append:0.171303
insert:2.461631[]+[]:15.466849[ifor]:0.049168list():0.029723

结论

来个列表相加[] + []操作是非常耗费时间
insert操作比较耗费时间

pop测试

x=range(2000000)
pop_zero= Timer("x.pop(0)","from __main__ import x")print("pop_zero ",pop_zero.timeit(number=1000),"seconds")
x=range(2000000)
pop_end= Timer("x.pop()","from __main__ import x")print("pop_end ",pop_end.timeit(number=1000),"seconds")# ('pop_zero ', 1.9101738929748535, 'seconds')# ('pop_end ', 0.00023603439331054688, 'seconds')

测试pop操作：从结果可以看出，pop最后一个元素的效率远远高于pop第一个元素

list内置操作的时间复杂度

dict内置操作的时间复杂度