数据结构和算法（代码执行时间测量模块timeit）

本文主要是介绍数据结构和算法（代码执行时间测量模块timeit），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考察python的执行效率，python在调用函数的时候，要考察其函数内部算法的效率，本文将利用python中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类型的秒数。

python列表类型不同操作的时间效率

python生成列表的常见形式有一下四种：

1. 两个列表的相加
2. 列表生成器
3. 可迭代对象转化为列表
4. 对空列表进行元素追加

对于以上四种形式，自定义四种函数实现

#对空列表进行元素追加
def test1():li = []for i in range(10000):li.append(i)
def test2():li = []for i in range(10000):li =li + [i]
def test3():li = [i for i in range(10000)]
def test4():li = list(range(10000))def test5():li = []for i in range(10000):li.extend([i])    

from timeit import Timertimer1 = Timer('test1()','from __main__ import test1')
print("append追加:",timer1.timeit(1000))timer2 = Timer('test2()','from __main__ import test2')
print("求和:",timer2.timeit(1000))timer3 = Timer('test3()','from __main__ import test3')
print("列表生成器:",timer3.timeit(1000))timer4 = Timer('test4()','from __main__ import test4')
print("可迭代对象转化:",timer4.timeit(1000))timer5 = Timer('test5()','from __main__ import test5')
print("extend:",timer5.timeit(1000))

结果

append追加: 0.6496986700076377
求和: 0.7470834940031637
列表生成器: 0.30637266401026864
可迭代对象转化: 0.14538886799709871
extend: 0.9688844589982182

元素追加（append和insert）

def t6():li = []for i in range(10000):li.append(i) #尾部添加def t7():li = []for i in range(10000):li.insert(0,i)#头部添加 

timer6 = Timer('t6()','from __main__ import t6')
print("append:",timer6.timeit(1000))timer7 = Timer('t7()','from __main__ import t7')
print("insert:",timer7.timeit(1000))

结果

append: 0.6802220060053514
insert: 28.873230566998245

结果来看尾部添加的效率明显优于头部添加，这与python的列表数据存储方式决定的，后续写数据结构时将对此进行解答

同理，pop删除元素方式，从队头删除的效率要远远低于从队尾删除元素的效率。

list内置函数的时间复杂度

Operation	Big-O Efficiency
index x[]	O(1)
index assignment	O(1)
append()	O(1)
pop()	O(1)
pop(i)	O(n)
insert	O(n)
del operator	O(n)
iteration	O(n)
contains(in)	O(n)
get slice[x:y]	O(k)
del slice	O(n)
set slice	O(n+k)
reverse	O(n)
concatename	O(k)
sort	O(nlogn)
multiply	O(nk)

dict内置函数的时间复杂度

Operation	Big-O Efficiency
copy	O(n)
get item	O(1)
set item	O(1)
delete item	O(1)
iteration	O(n)
contains(in)	O(1)

这篇关于数据结构和算法（代码执行时间测量模块timeit）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---