对于某个比较简单的算法,我们有时候确实能够精确地分析出算法的复杂度。

  比如算法复杂度为5n^2+10n+6,但是事实上并不需要这样,因为当n足够大时,可以忽略掉低阶项和最高次项的系数,因此就引出了“渐近复杂度”,并且用“渐近记号”来表示“渐近复杂度”。

  渐近记号包括:

符号含义
O渐进小于或等于
Ω渐进大于或等于
Θ渐进等于

  举例:

  如果a=x+x,b=x+5,则称a与b是相同等级的,且a渐进等于b;

  如果a=x+x,b=x+5,则称a与b不是相同等级的,且a渐进小于或等于b,b渐进大于或等于a。

  其中判断a和b是不是两个相同等级的,是依靠比较两个式子中自变量最高的次数,a=x+x 中自变量最高次数为2,b=x+5 中自变量最高次数为3。

  如果两个自变量的最高次数相同,则说明它们是相同等级的,即他们俩渐进相等,

  如果其中一个的次数比另一个高,则称次数低的一个式子渐进小于或等于次数高的式子,次数高的一个式子渐进大于或等于次数低的式子。

  注意不要关注他们的系数谁大谁小,现在用符号表示语言:

  a=x+x,b=x+5;   ====>    a=Θ(b);

  a=x+x,b=x+5;   ====>    a=O(b)  或者  b=Ω(a);

  其实,这个只要明白比较的是什么就能理解三个符号的含义及用法了。

  简记为:O表示上界,Ω表示下界,Θ表示平行。

 
性能测量工具

  Python自带了几个性能分析的模块:profile、cProfile和hotshot,使用方法基本都差不多,无非模块是纯Python还是用C写的。

cProfile的命令行用法

python -m cProfile XXX.py

输出到指定的文件:

python -m cProfile -o log.txt XXX.py

输出就被定向到了log.txt文件。

log.txt文件可以用VPT(http://visualpytune.googlecode.com)这样的图形工具打开。当log比较多的时候,可以很方便的进行过滤和时间的排序。

     2145 function calls (2058 primitive calls) in 0.301 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 _strptime.py:103(__calc_am_pm)
1 0.000 0.000 0.000 0.000 _strptime.py:115(__calc_date_time)
1 0.022 0.022 0.024 0.024 _strptime.py:12(<module>)
1 0.000 0.000 0.000 0.000 _strptime.py:160(__calc_timezone)
1 0.000 0.000 0.000 0.000 _strptime.py:176(TimeRE)
1 0.000 0.000 0.002 0.002 _strptime.py:179(__init__)
4 0.000 0.000 0.000 0.000 _strptime.py:212(<genexpr>)
6 0.000 0.000 0.000 0.000 _strptime.py:221(__seqToRE)
49 0.000 0.000 0.000 0.000 _strptime.py:236(<genexpr>)
4 0.000 0.000 0.001 0.000 _strptime.py:240(pattern)
1 0.000 0.000 0.001 0.001 _strptime.py:263(compile)

输出如上图,主要有:

  ncalls:函数被call的次数
  tottime:函数总的耗时,但是不包括其下的子函数的耗时
  percall:tottime平均到每次调用的耗时
  cumtime:函数总的耗时,包括了其子函数的耗时(递归函数也不例外)
  percall:cumtime平均到每次调用的耗时
  filename:lineno(function) :每个函数各自的信息

cProfile在Python代码中使用

import cProfile
cProfile.run('myfunction(arg1,arg2)', 'myfunction_prof')

使用以上的代码来引入cProfile, 并且使用其作为入口来调用待测函数。结果会放在myfunction_prof文件中。

这里再介绍一下结果文件在python下的阅读方法:

import pstats
p = pstats.Stats('myfunction_prof')
p.print_stats() # 可以设置排序方式,例如以花费时间多少排序
p.sort_stats('time').print_stats()

命令行中使用方法:

python -m pstats myfunction_prof

  

以上的内容,很容易在python的reference中找到,请参考:

http://docs.python.org/2/library/profile.html

05-11 22:39