代码优化能够让程序运行更快,它是在不改变程序运行结果的情况下使得程序的运行效率更高,根据80/20原则,实现程序的重构、优化、扩展以及文档相关的事情通常需要消耗80%的工作量。优化通常包含两方面的内容:减小代码的体积,提高代码的运行效率。
改进算法,选择合适的数据结构
一个良好的算法能够对性能起到关键作用,因此性能改进的首要点是对算法的改进。在算法的时间复杂度排序上依次是:
O(1) -> O(lg n) -> O(n lg n) -> O(n^2) -> O(n^3) -> O(n^k) -> O(k^n) -> O(n!)
因此如果能够在时间复杂度上对算法进行一定的改进,对性能的提高不言而喻。但对具体算法的改进不属于本文讨论的范围,读者可以自行参考这方面资料。下面的内容将集中讨论数据结构的选择。
- 字典(dictionary)与列表(list)
Python字典中使用了hash table,因此查找操作的复杂度为O(1),而list实际是个数组,在list中,查找需要遍历整个list,其复杂度为O(n),因此对成员的查找访问等操作字典要比list更快。
清单1.代码dict.py
- from time import time
- t = time()
- list = ['a','b','is','python','jason','hello','hill','with','phone','test',
- 'dfdf','apple','pddf','ind','basic','none','baecr','var','bana','dd','wrd']
- #list = dict.fromkeys(list,True)
- print list
- filter = []
- for i in range (1000000):
- for find in ['is','hat','new','list','old','.']:
- if find not in list:
- filter.append(find)
- print "total run time:"
- print time()-t
上述代码运行大概需要16.09seconds。如果去掉行#list=dict.fromkeys(list,True)的注释,将list转换为字典之后再运行,时间大约为8.375 seconds,效率大概提高了一半。因此在需要多数据成员进行频繁的查找或者访问的时候,使用dict而不是list是一个较好的选择。
- 集合(set)与列表(list)
set的union,intersection,difference操作要比list的迭代要快。因此如果涉及到求list交集,并集或者差的问题可以转换为set来操作。
清单2.求list的交集:
- from time import time
- t = time()
- lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44]
- listb=[2,4,6,9,23]
- intersection=[]
- for i in range (1000000):
- for a in lista:
- for b in listb:
- if a == b:
- intersection.append(a)
- print "total run time:"
- print time()-t
上述程序的运行时间大概为:
total run time:
38.4070000648 |
清单3. 使用set求交集
- from time import time
- t = time()
- lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44]
- listb=[2,4,6,9,23]
- intersection=[]
- for i in range (1000000):
- list(set(lista)&set(listb))
- print "total run time:"
- print time()-t
改为set后程序的运行时间缩减为8.75,提高了4倍多,运行时间大大缩短。读者可以自行使用表1其他的操作进行测试。
表1.set常见用法
语法 操作 说明
set(list1)|set(list2) union 包含list1和list2所有数据的新集合
set(list1)&set(list2) intersection 包含list1和list2*同元素的新集合
set(list1)–set(list2) difference 在list1中出现但不在list2中出现的元素的集合
对循环的优化
对循环的优化所遵循的原则是尽量减少循环过程中的计算量,有多重循环的尽量将内层的计算提到上一层。 下面通过实例来对比循环优化后所带来的性能的提高。程序清单4中,如果不进行循环优化,其大概的运行时间约为132.375。
清单4.为进行循环优化前
- from time import time
- t = time()
- lista = [1,2,3,4,5,6,7,8,9,10]
- listb =[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01]
- for i in range (1000000):
- for a in range(len(lista)):
- for b in range(len(listb)):
- x=lista[a]+listb[b]
- print "total run time:"
- print time()-t
现在进行如下优化,将长度计算提到循环外,range用xrange代替,同时将第三层的计算lista[a]提到循环的第二层。
清单5.循环优化后
- from time import time
- t = time()
- lista = [1,2,3,4,5,6,7,8,9,10]
- listb =[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01]
- lenlen1=len(lista)
- lenlen2=len(listb)
- for i in xrange (1000000):
- for a in xrange(len1):
- temp=lista[a]
- for b in xrange(len2):
- x=temp+listb[b]
- print "total run time:"
- print time()-t
上述优化后的程序其运行时间缩短为102.171999931。在清单4中lista[a] 被计算的次数为1000000*10*10,而在优化后的代码中被计算的次数为1000000*10,计算次数大幅度缩短,因此性能有所提升。
充分利用Lazy if-evaluation的特性
Python中条件表达式是lazy evaluation的,也就是说如果存在条件表达式if x and y,在x为false的情况下y表达式的值将不再计算。因此可以利用该特性在一定程度上提高程序效率。
清单6.利用Lazy if-evaluation的特性
- from time import time
- t = time()
- abbreviations = ['cf.', 'e.g.', 'ex.', 'etc.', 'fig.', 'i.e.', 'Mr.', 'vs.']
- for i in range (1000000):
- for w in ('Mr.', 'Hat', 'is', 'chasing', 'the', 'black', 'cat', '.'):
- if w in abbreviations:
- #if w[-1] == '.' and w in abbreviations:
- pass
- print "total run time:"
- print time()-t
在未进行优化之前程序的运行时间大概为8.84,如果使用注释行代替第一个if,运行的时间大概为6.17。
字符串的优化
Python中的字符串对象是不可改变的,因此对任何字符串的操作如拼接,修改等都将产生一个新的字符串对象,而不是基于原字符串,因此这种持续的copy会在一定程度上影响Python的性能。对字符串的优化也是改善性能的一个重要的方面,特别是在处理文本较多的情况下。字符串的优化主要集中在以下几个方面:
1、在字符串连接的使用尽量使用join()而不是+:在代码清单7中使用+进行字符串连接大概需要0.125s,而使用join缩短为0.016s。因此在字符的操作上join比+要快,因此要尽量使用join而不是+。
清单7.使用join而不是+连接字符串
- from time import time
- t = time()
- s = ""
- list = ['a','b','b','d','e','f','g','h','i','j','k','l','m','n']
- for i in range (10000):
- for substr in list:
- s+= substr
- print "total run time:"
- print time()-t
同时要避免:
- s = ""
- for x in list:
- s += func(x)
而是要使用:
- slist = [func(elt) for elt in somelist]
- s = "".join(slist)
2、当对字符串可以使用正则表达式或者内置函数来处理的时候,选择内置函数。如str.isalpha(),str.isdigit(),str.startswith((‘x’, ‘yz’)),str.endswith((‘x’, ‘yz’))
3、对字符进行格式化比直接串联读取要快,因此要使用
- out = "%s%s%s%s" % (head, prologue, query, tail)
而避免
- out = "" + head + prologue + query + tail + ""
使用列表解析(list comprehension)和生成器表达式(generator expression)
列表解析要比在循环中重新构建一个新的list更为高效,因此我们可以利用这一特性来提高运行的效率。
- from time import time
- t = time()
- list = ['a','b','is','python','jason','hello','hill','with','phone','test',
- 'dfdf','apple','pddf','ind','basic','none','baecr','var','bana','dd','wrd']
- total=[]
- for i in range (1000000):
- for w in list:
- total.append(w)
- print "total run time:"
- print time()-t
使用列表解析:
- for i in range (1000000):
- a = [w for w in list]
上述代码直接运行大概需要17s,而改为使用列表解析后,运行时间缩短为9.29s。将近提高了一半。生成器表达式则是在2.4中引入的新内容,语法和列表解析类似,但是在大数据量处理时,生成器表达式的优势较为明显,它并不创建一个列表,只是返回一个生成器,因此效率较高。在上述例子上中代码a =[w for w in list]修改为a=(w for w in list),运行时间进一步减少,缩短约为2.98s。
其他优化技巧
1、如果需要交换两个变量的值使用a,b=b,a而不是借助中间变量t=a;a=b;b=t;
- >>> from timeit import Timer
- >>> Timer("t=a;a=b;b=t","a=1;b=2").timeit()
- 0.25154118749729365
- >>> Timer("a,bb=b,a","a=1;b=2").timeit()
- 0.17156677734181258
- >>
- >
2、在循环的时候使用xrange而不是range;使用xrange可以节省大量的系统内存,因为xrange()在序列中每次调用只产生一个整数元素。而range()將直接返回完整的元素列表,用于循环时会有不必要的开销。在Python3中xrange不再存在,里面range提供一个可以遍历任意长度的范围的iterator。
3、使用局部变量,避免“global”关键字。Python访问局部变量会比全局变量要快得多,因此可以利用这一特性提升性能。
4、if done is not None比语句if done!=None更快,读者可以自行验证;
5、在耗时较多的循环中,可以把函数的调用改为内联的方式;
6、使用级联比较 “x < y < z”而不是“x < y and y < z”;
7、while 1要比while True更快(当然后者的可读性更好);
8、build in函数通常较快,add(a,b)要优于a+b。
定位程序性能瓶颈
对代码优化的前提是需要了解性能瓶颈在什么地方,程序运行的主要时间是消耗在哪里,对于比较复杂的代码可以借助一些工具来定位,Python内置了丰富的性能分析工具,如profile,cProfile与hotshot等。其中Profiler是python自带的一组程序,能够描述程序运行时候的性能,并提供各种统计帮助用户定位程序的性能瓶颈。Python标准模块提供三种profilers:cProfile,profile以及hotshot。
profile的使用非常简单,只需要在使用之前进行import即可。具体实例如下:
清单8.使用profile进行性能分析
- import profile
- def profileTest():
- Total =1;
- for i in range(10):
- TotalTotal=Total*(i+1)
- print Total
- return Total
- if __name__ == "__main__":
- profile.run("profileTest()")
程序的运行结果如下:
图 1. 性能分析结果
其中输出每列的具体解释如下:
- ncalls:表示函数调用的次数;
- tottime:表示指定函数的总的运行时间,除掉函数中调用子函数的运行时间;
- percall:(第一个percall)等于tottime/ncalls;
- cumtime:表示该函数及其所有子函数的调用运行的时间,即函数开始调用到返回的时间;
- percall:(第二个percall)即函数运行一次的平均时间,等于cumtime/ncalls;
- filename:lineno(function):每个函数调用的具体信息;
如果需要将输出以日志的形式保存,只需要在调用的时候加入另外一个参数。如profile.run(“profileTest()”,”testprof”)。
对于profile的剖析数据,如果以二进制文件的时候保存结果的时候,可以通过pstats模块进行文本报表分析,它支持多种形式的报表输出,是文本界面下一个较为实用的工具。使用非常简单:
- import pstats
- p = pstats.Stats('testprof')
- p.sort_stats("name").print_stats()
其中sort_stats()方法能够对剖分数据进行排序,可以接受多个排序字段,如sort_stats(‘name’, ‘file’)将首先按照函数名称进行排序,然后再按照文件名进行排序。常见的排序字段有calls(被调用的次数),time(函数内部运行时间),cumulative(运行的总时间)等。此外pstats也提供了命令行交互工具,执行 python–m pstats后可以通过help了解更多使用方式。
对于大型应用程序,如果能够将性能分析的结果以图形的方式呈现,将会非常实用和直观,常见的可视化工具有Gprof2Dot,visualpytune,KCacheGrind等,读者可以自行查阅相关官网,本文不做详细讨论。
Python性能优化工具
Python性能优化除了改进算法,选用合适的数据结构之外,还有几种关键的技术,比如将关键Python代码部分重写成C扩展模块,或者选用在性能上更为优化的解释器等,这些在本文中统称为优化工具。Python有很多自带的优化工具,如Psyco,Pypy,Cython,Pyrex等,这些优化工具各有千秋,本节选择几种进行介绍。
Psyco
Psyco是一个just-in-time的编译器,它能够在不改变源代码的情况下提高一定的性能,Psyco将操作编译成有点优化的机器码,其操作分成三个不同的级别,有”运行时”、”编译时”和”虚拟时”变量。并根据需要提高和降低变量的级别。运行时变量只是常规Python解释器处理的原始字节码和对象结构。一旦Psyco将操作编译成机器码,那么编译时变量就在机器寄存器和可直接访问的内存位置中表示。同时Python能高速缓存已编译的机器码以备今后重用,这样能节省一点时间。但Psyco也有其缺点,其本身运行所占内存较大。目前Psyco已经不在Python2.7中支持,而且不再提供维护和更新了,对其感兴趣的可以参考ttp://psyco.sourceforge.net/
Pypy
Pypy表示“用Python实现的Python”,但实际上它是使用一个称为RPython的Python子集实现的,能够将Python代码转成C,.NET,Java等语言和平台的代码。PyPy 集成了一种即时 (JIT)编译器。和许多编译器,解释器不同,它不关心Python代码的词法分析和语法树。因为它是用Python语言写的,所以它直接利用Python语言的Code Object。Code Object是Python字节码的表示,也就是说,PyPy直接分析Python代码所对应的字节码,这些字节码即不是以字符形式也不是以某种二进制格式保存在文件中,而在Python运行环境中。目前版本是1.8.支持不同的平台安装,Windows上安装Pypy需要先下载,然后解压到相关的目录,并将解压后的路径添加到环境变量path中即可。在命令行运行Pypy,如果出现如下错误:”没有找到MSVCR100.dll, 因此这个应用程序未能启动,重新安装应用程序可能会修复此问题”,则还需要在微软的官网上下载VS 2010 runtime libraries解决该问题。
安装成功后在命令行里运行Pypy,输出结果如下:
- C:\Documents and Settings\Administrator>pypy
- Python 2.7.2 (0e28b379d8b3, Feb 09 2012, 18:31:47)
- [PyPy 1.8.0 with MSC v.1500 32 bit] on win32
- Type "help", "copyright", "credits" or "license" for more information.
- And now for something completely different: ``PyPy is vast, and contains
- multitudes''
- >>>>
以清单5的循环为例子,使用Python和Pypy分别运行,得到的运行结果分别如下:
- C:\Documents and Settings\Administrator\ 桌面 \doc\python>pypy loop.py
- total run time:
- 8.42199993134
- C:\Documents and Settings\Administrator\ 桌面 \doc\python>python loop.py
- total run time:
- 106.391000032
可见使用Pypy来编译和运行程序,其效率大大的提高。
Cython
Cython是用Python实现的一种语言,可以用来写Python扩展,用它写出来的库都可以通过import来载入,性能上比Python的快。Cython里可以载入Python扩展(比如 import math),也可以载入C的库的头文件(比如:cdef extern from “math.h”),另外也可以用它来写Python代码。将关键部分重写成C扩展模块
Linux Cpython的安装:
第一步:下载
- [root@v5254085f259 cpython]# wget -N http://cython.org/release/Cython-0.15.1.zip
- --2012-04-16 22:08:35-- http://cython.org/release/Cython-0.15.1.zip
- Resolving cython.org... 128.208.160.197
- Connecting to cython.org|128.208.160.197|:80... connected.
- HTTP request sent, awaiting response... 200 OK
- Length: 2200299 (2.1M) [application/zip]
- Saving to: `Cython-0.15.1.zip'
- 100%[======================================>] 2,200,299 1.96M/s in 1.1s
- 2012-04-16 22:08:37 (1.96 MB/s) - `Cython-0.15.1.zip' saved [2200299/2200299]
第二步:解压
- [root@v5254085f259 cpython]# unzip -o Cython-0.15.1.zip
第三步:安装
- python setup.py install
安装完成后直接输入Cython,如果出现如下内容则表明安装成功。
- [root@v5254085f259 Cython-0.15.1]# cython
- Cython (http://cython.org) is a compiler for code written in the
- Cython language. Cython is based on Pyrex by Greg Ewing.
- Usage: cython [options] sourcefile.{pyx,py} ...
- Options:
- -V, --version Display version number of cython compiler
- -l, --create-listing Write error messages to a listing file
- -I, --include-dir <directory> Search for include files in named directory
- (multiple include directories are allowed).
- -o, --output-file <filename> Specify name of generated C file
- -t, --timestamps Only compile newer source files
- -f, --force Compile all source files (overrides implied -t)
- -q, --quiet Don't print module names in recursive mode
- -v, --verbose Be verbose, print file names on multiple compil ation
- -p, --embed-positions If specified, the positions in Cython files of each
- function definition is embedded in its docstring.
- --cleanup <level>
- Release interned objects on python exit, for memory debugging.
- Level indicates aggressiveness, default 0 releases nothing.
- -w, --working <directory>
- Sets the working directory for Cython (the directory modules are searched from)
- --gdb Output debug information for cygdb
- -D, --no-docstrings
- Strip docstrings from the compiled module.
- -a, --annotate
- Produce a colorized HTML version of the source.
- --line-directives
- Produce #line directives pointing to the .pyx source
- --cplus
- Output a C++ rather than C file.
- --embed[=<method_name>]
- Generate a main() function that embeds the Python interpreter.
- -2 Compile based on Python-2 syntax and code seman tics.
- -3 Compile based on Python-3 syntax and code seman tics.
- --fast-fail Abort the compilation on the first error
- --warning-error, -Werror Make all warnings into errors
- --warning-extra, -Wextra Enable extra warnings
- -X, --directive <name>=<value>
- [,<namename=value,...] Overrides a compiler directive
其他平台上的安装可以参考文档:http://docs.cython.org/src/quickstart/install.html
Cython代码与Python不同,必须先编译,编译一般需要经过两个阶段,将pyx文件编译为.c 文件,再将.c 文件编译为.so 文件。编译有多种方法:
- 通过命令行编译:
假设有如下测试代码,使用命令行编译为.c文件。
- [root@v5254085f259 test]# gcc -shared -pthread -fPIC -fwrapv -O2
- -Wall -fno-strict-aliasing -I/usr/include/python2.4 -o sum.so sum.c
- [root@v5254085f259 test]# ls
- total 96
- 4 drwxr-xr-x 2 root root 4096 Apr 17 02:47 .
- 4 drwxr-xr-x 4 root root 4096 Apr 16 22:20 ..
- 4 -rw-r--r-- 1 root root 35 Apr 17 02:45 1
- 60 -rw-r--r-- 1 root root 55169 Apr 17 02:45 sum.c
- 4 -rw-r--r-- 1 root root 35 Apr 17 02:45 sum.pyx
- 20 -rwxr-xr-x 1 root root 20307 Apr 17 02:47 sum.so
- 使用distutils编译
建立一个setup.py的脚本:
- from distutils.core import setup
- from distutils.extension import Extension
- from Cython.Distutils import build_ext
- ext_modules = [Extension("sum", ["sum.pyx"])]
- setup(
- name = 'sum app',
- cmdclass = {'build_ext': build_ext},
- ext_modulesext_modules = ext_modules
- )
- [root@v5254085f259 test]# python setup.py build_ext --inplace
- running build_ext
- cythoning sum.pyx to sum.c
- building 'sum' extension
- gcc -pthread -fno-strict-aliasing -fPIC -g -O2 -DNDEBUG -g -fwrapv -O3
- -Wall -Wstrict-prototypes -fPIC -I/opt/ActivePython-2.7/include/python2.7
- -c sum.c -o build/temp.linux-x86_64-2.7/sum.o
- gcc -pthread -shared build/temp.linux-x86_64-2.7/sum.o
- -o /root/cpython/test/sum.so
编译完成之后可以导入到Python中使用:
- [root@v5254085f259 test]# python
- ActivePython 2.7.2.5 (ActiveState Software Inc.) based on
- Python 2.7.2 (default, Jun 24 2011, 11:24:26)
- [GCC 4.0.2 20051125 (Red Hat 4.0.2-8)] on linux2
- Type "help", "copyright", "credits" or "license" for more information.
- >>> import pyximport; pyximport.install()
- >>> import sum
- >>> sum.sum(1,3)
下面来进行一个简单的性能比较:
清单9.Cython测试代码
- from time import time
- def test(int n):
- cdef int a =0
- cdef int i
- for i in xrange(n):
- a+= i
- return a
- t = time()
- test(10000000)
- print "total run time:"
- print time()-t
测试结果:
- [GCC 4.0.2 20051125 (Red Hat 4.0.2-8)] on linux2
- Type "help", "copyright", "credits" or "license" for more information.
- >>> import pyximport; pyximport.install()
- >>> import ctest
- total run time:
- 0.00714015960693
清单10.Python测试代码
- from time import time
- def test(n):
- a =0;
- for i in xrange(n):
- a+= i
- return a
- t = time()
- test(10000000)
- print "total run time:"
- print time()-t
- [root@v5254085f259 test]# python test.py
- total run time:
- 0.971596002579
从上述对比可以看到使用Cython的速度提高了将近100多倍。
总结
本文初步探讨了Python常见的性能优化技巧以及如何借助工具来定位和分析程序的性能。