5.2　提高性能

我们针对power3类的性能问题可以考虑两个方面。

首先，考虑使用更好的算法。然后，考虑带有记忆的算法，包含缓存。因此，函数变得有状态了，这是可调用对象的亮点。

第1点改变是使用分治算法。在先前版本中把xⁿ拆分为n个步骤；使用循环计算每个n的乘法运算。如果可以找到把一个问题划分为两个相同子问题的方式，问题就会被分解为log₂n个步骤。对于pow1(2,1024)，power1函数中执行了1024次2的乘法运算。我们可以把这个问题优化为只需要10次乘法计算，无疑是显著的性能提升。

如果只是简单地使用一个固定的值做乘法运算，我们会使用“快速幂”算法。它使用了以下3个基本逻辑来计算xⁿ。

• 如果n=0：xn=1，结果返回1。
• 如果n是奇数并且n mod 2 = 1，结果为xn-1 × x。这里包含了xn-1的递归运算。这里仍做了一次乘法运算但并非是一个优化的点。
• 如果是偶数并且n mod = 0，结果为xn/2× xn/2。这里包含了xn/2的递归计算。这里把乘法计算的数量减少了一半。

以下是一个递归的、可调用对象的实现。

class Power4( abc.Callable ):
　　def call( self, x, n ):
　　　　if n == 0: return 1
　　　　elif n % 2 == 1:
　　　　　　return self.call(x, n-1)x
　　　　else: # n % 2 == 0:
　　　　　　t= self.call(x, n//2)
　　　　　　return tt

pow4= Power4()

我们应用以上思路实现了快速幂算法。如果n为0，返回1。如果n为奇数，返回递归调用的x^n-1× x。如果n为偶数，返回递归调用的x^n/2× x^n/2。

执行效率显著提高了。可以使用timeit模块来查看性能的对比。在使用timeit时，需要学习一些预备知识。当我们分别允许powl(2,1024)和pow4(2,1024) 函数10000次进行对比，会发现第1个函数耗时183秒而后者只需要8秒。加入记忆化功能还可以进一步优化。

以下是使用timeit来进行性能分析的示例。

import timeit
iterative= timeit.timeit( "pow1(2,1024)","""
import collections.abc
class Power1( collections.abc.Callable ):
　　def call( self, x, n ):
　　　　p= 1
　　　　for i in range(n):
　　　　　　p *= x
　　　　return p
pow1= Power1()
""", number=100000 ) # otherwise it takes 3 minutes
print( "Iterative", iterative )

通过timeit模块，可使用timeit.timeit()函数来对每行语句的表达式进行耗时计算。在上例中，表达式为powl(2,1024)。而该语句的上下文是Pow1()函数的定义，包含了导入、类定义和实例的创建。

通过定义number=100000来让测试更快地结束。如果使用之前例子的迭代数量，几乎要花两分钟才能运行完毕。

记忆化与缓存

所谓的记忆化功能，即缓存上一次的计算结果为了下次可以重用。为了提高性能，可考虑通过使用更多的内存而尽量避免计算。

一个普通的函数通常不会缓存上次的执行结果。函数通常是无状态的，然而一个可调用对象可以是有状态的，它可以缓存上次的执行结果。

如下是power可调用对象带有记忆功能的实现版本。

class Power5( collections.abc.Callable ):
　　def init( self ):
　　　　self.memo = {}
def call( self, x, n ):
　　if (x,n) not in self.memo:
　　　　if n == 0:
　　　　　　self.memo[x,n]= 1
　　　　elif n % 2 == 1:
　　　　　　self.memo[x,n]= self.call(x, n-1) x
　　　　elif n % 2 == 0:
　　　　　　t= self.call(x, n//2)
　　　　　　self.memo[x,n]= tt
　　　　else:
　　　　　　raise Exception("Logic Error")
　　　　return self.memo[x,n]
pow5= Power5()

我们修改了算法，加入了self.memo缓存。

如果xⁿ的值之前计算过，再次访问时将会从缓存取而非重新计算。这就是之前说的性能提升的地方。

否则，xⁿ的值必须被计算然后放入缓存。计算快速指数的3条法则只是操作缓存中的值，这使得以后的计算过程可以重用缓存的结果。

记忆化发挥的作用还不止于此。通常使用可调用对象来替换执行速度缓慢、逻辑复杂的函数，对性能的提升也是显著的。