算法工程师必备技能Python 优化提速小技巧.docx

算法工程师必备技能（Python优化提速小技巧）代码优化原那么本文会介绍不少的Python代码加速运行的技巧。在深化代码优化细节之前需要解析一些代码优化根本原那么。第一个根本原那么是不要过早优化。很多人一开场写代码就奔着性能优化的目的“让正确的程序更快要比让快速的程序正确容易得多。因此优化的前提是代码能正常工作。过早地进展优化可能会无视对总体性能指标的把握在得到全局结果前不要主次颠倒。第二个根本原那么是权衡优化的代价。优化是有代价的想解决所有性能的问题是几乎不可能的。通常面临的选择是时间换空间或者空间换时间。另外开发代价也需要考虑。第三个原那么是不要优化那些无关紧要的局部。假如对代码的每一局部都去优化这些修改会使代码难以浏览以及理解。假如你的代码运行速度很慢首先要找到代码运行慢的位置通常是内部循环专注于运行慢的地方进展优化。在其他地方一点时间上的损失没有什么影响。全局变量很耗时#不推荐写法。代码耗时26.8秒importmathsize10000forxinrange(size):foryinrange(size):zmath.sqrt(x)math.sqrt(y)许多程序员刚开场会用Python语言写一些简单的脚本当编写脚本时通常习惯了直接将其写为全局变量例如上面的代码。但是由于全局变量以及部分变量实现方式不同定义在全局范围内的代码运行速度会比定义在函数中的慢不少。通过将脚本语句放入到函数中通常可带来15%-30%的速度提升。#推荐写法。代码耗时20.6秒importmathdefmain():#定义到函数中以减少全部变量使用size10000forxinrange(size):foryinrange(size):zmath.sqrt(x)math.sqrt(y)main().很耗时防止模块以及函数属性访问#不推荐写法。代码耗时14.5秒importmathdefcomputeSqrt(size:int):resultforiinrange(size):result.append(math.sqrt(i)returnresultdefmain():size10000for_inrange(size):resultcomputeSqrt(size)main()每次使用.属性访问操作符时会触发特定的方法如_getattribute_()以及_getattr_()这些方法会进展字典操作因此会带来额外的时间开销。通过fromimport语句可以消除属性访问。#第一次优化写法。代码耗时10.9秒frommathimportsqrtdefcomputeSqrt(size:int):resultforiinrange(size):result.append(sqrt(i)#防止math.sqrt的使用returnresultdefmain():size10000for_inrange(size):resultcomputeSqrt(size)main()部分变量的查找会比全局变量更快因此对于频繁访问的变量sqrt通过将其改为部分变量可以加速运行。#第二次优化写法。代码耗时9.9秒importmathdefcomputeSqrt(size:int):resultsqrtmath.sqrt#赋值给部分变量foriinrange(size):result.append(sqrt(i)#防止math.sqrt的使用returnresultdefmain():size10000for_inrange(size):resultcomputeSqrt(size)main()除了math.sqrt外computeSqrt()函数中还有.的存在那就是调用list的append方法。通过将该方法赋值给一个部分变量可以彻底消除computeSqrt()函数中for循环内部的.使用。#推荐写法。代码耗时7.9秒importmathdefcomputeSqrt(size:int):resultappendresult.appendsqrtmath.sqrt#赋值给部分变量foriinrange(size):append(sqrt(i)#防止result.append以及math.sqrt的使用returnresultdefmain():size10000for_inrange(size):resultcomputeSqrt(size)main()防止类内属性访问#不推荐写法。代码耗时10.4秒importmathfromtypingimportListclassDemoClass:def_init_(self,value:int):self._valuevaluedefcomputeSqrt(self,size:int)-Listfloat:resultappendresult.appendsqrtmath.sqrtfor_inrange(size):append(sqrt(self._value)returnresultdefmain():size10000for_inrange(size):demo_instanceDemoClass(size)resultdemo_instanceputeSqrt(size)main()防止.的原那么也适用于类内属性访问self._value的速度会比访问一个部分变量更慢一些。通过将需要频繁访问的类内属性赋值给一个部分变量可以提升代码运行速度。#推荐写法。代码耗时8.0秒importmathfromtypingimportListclassDemoClass:def_init_(self,value:int):self._valuevaluedefcomputeSqrt(self,size:int)-Listfloat:resultappendresult.appendsqrtmath.sqrtvalueself._valuefor_inrange(size):append(sqrt(value)#防止self._value的使用returnresultdefmain():size10000for_inrange(size):demo_instanceDemoClass(size)demo_instanceputeSqrt(size)main()防止不必要的抽象#不推荐写法代码耗时0.55秒classDemoClass:def_init_(self,value:int):self.valuevaluepropertydefvalue(self)-int:returnself._valuevalue.setterdefvalue(self,x:int):self._valuexdefmain():size1000000foriinrange(size):demo_instanceDemoClass(size)valuedemo_instance.valuedemo_instance.valueimain()任何时候当你使用额外的处理层比方装饰器、属性访问、描绘器去包装代码时都会让代码变慢。大局部情况下需要重新进展审视使用属性访问器的定义是否有必要使用getter/setter函数对属性进展访问通常是C/C程序员遗留下来的代码风格。假如真的没有必要就使用简单属性。#推荐写法代码耗时0.33秒classDemoClass:def_init_(self,value:int):self.valuevalue#防止不必要的属性访问器defmain():size1000000foriinrange(size):demo_instanceDemoClass(size)valuedemo_instance.valuedemo_instance.valueimain()防止数据复制毫无意义的数据复制#不推荐写法代码耗时6.5秒defmain():size10000for_inrange(size):valuerange(size)value_listxforxinvaluesquare_listx*xforxinvalue_listmain()上面的代码中value_list完全没有必要这会创立不必要的数据构造或者复制。#推荐写法代码耗时4.8秒defmain():size10000for_inrange(size):valuerange(size)square_listx*xforxinvalue#防止无意义的复制main()另外一种情况是对Python的数据分享机制过于偏执并没有很好地理解或者信任Python的内存模型滥用copy.deepcopy()之类的函数。通常在这些代码中是可以去掉复制操作的。交换值时不使用中间变量#不推荐写法代码耗时0.07秒defmain():size1000000for_inrange(size):tempabtempmain()上面的代码在交换值时创立了一个临时变量temp假如不借助中间变量代码更为简洁、且运行速度更快。#推荐写法代码耗时0.06秒defmain():size1000000for_inrange(size):a,bb,a#不借助中间变量main()字符串拼接用join而不是#不推荐写法代码耗时2.6秒importstringfromtypingimportListdefconcatString(string_list:Liststr)-str:resultforstr_iinstring_list:resultstr_ireturnresultdefmain():string_listlist(string.ascii_letters*100)for_inrange(10000):resultconcatString(string_list)main()当使用ab拼接字符串时由于Python中字符串是不可变对象其会申请一块内存空间将a以及b分别复制到该新申请的内存空间中。因此假如要拼接n个字符串会产生n-1个中间结果每产生一个中间结果都需要申请以及复制一次内存严重影响运行效率。而使用join()拼接字符串时会首先计算出需要申请的总的内存空间然后一次性地申请所需内存并将每个字符串元素复制到该内存中去。#推荐写法代码耗时0.3秒importstringfromtypingimportListdefconcatString(string_list:Liststr)-str:return.join(string_list)#使用join而不是defmain():string_listlist(string.ascii_letters*100)for_inrange(10000):resultconcatString(string_list)main()利用if条件的短路特性#不推荐写法代码耗时0.05秒fromtypingimportListdefconcatString(string_list:Liststr)-str:abbreviationscf.,e.g.,ex.,etc.,flg.,i.e.,Mr.,vs.abbr_count0resultforstr_iinstring_list:ifstr_iinabbreviations:resultstr_ireturnresultdefmain():for_inrange(10000):string_listMr.,Hat,is,Chasing,the,black,cat,.resultconcatString(string_list)main()if条件的短路特性是指对ifaandb这样的语句当a为False时将直接返回不再计算b对于ifaorb这样的语句当a为True时将直接返回不再计算b。因此为了节约运行时间对于or语句应该将值为True可能性比拟高的变量写在or前而and应该推后。#推荐写法代码耗时0.03秒fromtypingimportListdefconcatString(string_list:Liststr)-str:abbreviationscf.,e.g.,ex.,etc.,flg.,i.e.,Mr.,vs.abbr_count0resultforstr_iinstring_list:ifstr_i-1.andstr_iinabbreviations:#利用if条件的短路特性resultstr_ireturnresultdefmain():for_inrange(10000):string_listMr.,Hat,is,Chasing,the,black,cat,.resultconcatString(string_list)main()循环优化用for循环代替while循环#不推荐写法。代码耗时6.7秒defcomputeSum(size:int)-int:sum_0whileisize:sum_ireturnsum_defmain():size10000for_inrange(size):sum_computeSum(size)main()Python的for循环比while循环快不少。#推荐写法。代码耗时4.3秒defcomputeSum(size:int)-int:sum_0foriinrange(size):#for循环代替while循环sum_ireturnsum_defmain():size10000for_inrange(size):sum_computeSum(size)main()使用隐式for循环代替显式for循环针对上面的例子更进一步可以用隐式for循环来替代显式for循环#推荐写法。代码耗时1.7秒defcomputeSum(size:int)-int:returnsum(range(size)#隐式for循环代替显式for循环defmain():size10000for_inrange(size):sumcomputeSum(size)main()减少内层for循环的计算#不推荐写法。代码耗时12.8秒importmathdefmain():size10000sqrtmath.sqrtforxinrange(size):foryinrange(size):zsqrt(x)sqrt(y)main()上面的代码中sqrt(x)位于内侧for循环每次训练经过中都会重新计算一次增加了时间开销。#推荐写法。代码耗时7.0秒importmathdefmain():size10000sqrtmath.sqrtforxinrange(size):sqrt_xsqrt(x)#减少内层for循环的计算foryinrange(size):zsqrt_xsqrt(y)main()使用numba.jit我们沿用上面介绍过的例子在此根底上使用numba.jit。numba可以将Python函数JIT编译为机器码执行大大进步代码运行速度。关于numba的更多信息见下面的主页#推荐写法。代码耗时0.62秒importnumbanumba.jitdefcomputeSum(size:float)-int:sum0foriinrange(size):sumireturnsumdefmain():size10000for_inrange(size):sumcomputeSum(size)main()选择适宜的数据构造Python内置的数据构造如str,tuple,list,set,dict底层都是C实现的速度非常快自己实现新的数据构造想在性能上到达内置的速度几乎是不可能的。list类似于C中的std:vector是一种动态数组。其会预分配一定内存空间当预分配的内存空间用完又继续向其中添加元素时会申请一块更大的内存空间然后将原有的所有元素都复制过去之后销毁之前的内存空间再插入新元素。删除元素时操作类似当已使用内存空间比预分配内存空间的一半还少时会另外申请一块小内存做一次元素复制之后销毁原有大内存空间。因此假如有频繁的新增、删除操作新增、删除的元素数量又很多时list的效率不高。此时应该考虑使用collections.deque。collections.deque是双端队列同时具备栈以及队列的特性可以在两端进展O(1)复杂度的插入以及删除操作。list的查找操作也非常耗时。当需要在list频繁查找某些元素或者频繁有序访问这些元素时可以使用bisect维护list对象有序并在其中进展二分查找提升查找的效率。另外一个常见需求是查找极小值或者极大值此时可以使用heapq模块将list转化为一个堆使得获取最小值的时间复杂度是O(1)。下面的网页给出了常用的Python数据构造的各项操作的时间复杂度