[TOC]
本章两个话题
- 渐近记法（asymptotic notation），主要关注的是运行时间的本质。
- 树(tree)、图(graph)这两种数据结构在python中的实现方式。
实证式算法评估
- 使用timeit模块来计时
mymodule.py
def myfunction():
sum1 = 0
for i in range(0,10000):
sum1 += i
return sum1
计时。关于timeit模块
python -m timeit -s"import mymodule as m" "m.myfunction()"
- -s S, --setup=S
执行时初始语句(默认是pass)
- 使用profile找出瓶颈
import cProfile
def main():
list1 = ['physics','chemistry',1990,1997,2000]
print(list1)
for i in list1:
print(i,end=' ')
def runMain():
cProfile.run('main()')
if __name__ == '__main__':
#main()
runMain()
result:
['physics', 'chemistry', 1990, 1997, 2000]
physics chemistry 1990 1997 2000 630 function calls in 0.043 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.043 0.043 <string>:1(<module>)
12 0.000 0.000 0.043 0.004 PyShell.py:1336(write)
91 0.000 0.000 0.000 0.000 rpc.py:150(debug)
13 0.000 0.000 0.043 0.003 rpc.py:213(remotecall)
13 0.000 0.000 0.002 0.000 rpc.py:223(asynccall)
13 0.000 0.000 0.041 0.003 rpc.py:243(asyncreturn)
13 0.000 0.000 0.000 0.000 rpc.py:249(decoderesponse)
13 0.000 0.000 0.041 0.003 rpc.py:287(getresponse)
13 0.000 0.000 0.000 0.000 rpc.py:295(_proxify)
13 0.000 0.000 0.041 0.003 rpc.py:303(_getresponse)
13 0.000 0.000 0.000 0.000 rpc.py:325(newseq)
13 0.000 0.000 0.001 0.000 rpc.py:329(putmessage)
12 0.000 0.000 0.001 0.000 rpc.py:551(__getattr__)
1 0.000 0.000 0.001 0.001 rpc.py:569(__getmethods)
13 0.000 0.000 0.000 0.000 rpc.py:57(dumps)
12 0.000 0.000 0.000 0.000 rpc.py:592(__init__)
12 0.000 0.000 0.041 0.003 rpc.py:597(__call__)
26 0.000 0.000 0.000 0.000 threading.py:1221(current_thread)
13 0.000 0.000 0.000 0.000 threading.py:210(__init__)
13 0.000 0.000 0.040 0.003 threading.py:258(wait)
13 0.000 0.000 0.000 0.000 threading.py:75(RLock)
1 0.000 0.000 0.043 0.043 timeit_test.py:2(main)
13 0.000 0.000 0.000 0.000 {built-in method allocate_lock}
1 0.000 0.000 0.043 0.043 {built-in method exec}
26 0.000 0.000 0.000 0.000 {built-in method get_ident}
26 0.000 0.000 0.000 0.000 {built-in method isinstance}
39 0.000 0.000 0.000 0.000 {built-in method len}
13 0.000 0.000 0.000 0.000 {built-in method pack}
6 0.000 0.000 0.043 0.007 {built-in method print}
13 0.000 0.000 0.000 0.000 {built-in method select}
13 0.000 0.000 0.000 0.000 {method '_acquire_restore' of '_thread.RLock' objects}
13 0.000 0.000 0.000 0.000 {method '_is_owned' of '_thread.RLock' objects}
13 0.000 0.000 0.000 0.000 {method '_release_save' of '_thread.RLock' objects}
13 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.RLock' objects}
26 0.040 0.002 0.040 0.002 {method 'acquire' of '_thread.lock' objects}
13 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
13 0.000 0.000 0.000 0.000 {method 'dump' of '_pickle.Pickler' objects}
12 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
13 0.000 0.000 0.000 0.000 {method 'getvalue' of '_io.BytesIO' objects}
13 0.000 0.000 0.000 0.000 {method 'release' of '_thread.RLock' objects}
13 0.001 0.000 0.001 0.000 {method 'send' of '_socket.socket' objects}
待续....
