Python性能优化之记忆化(Memoization)

记忆化(Memoization)介绍

简单说来 Memoization 是一种利用缓存来加速函数调用的技术手段,将消耗较大的调用结果存储起来,当再次遇到相同调用时就从缓存读取结果而无需重新计算。
有一个限制条件是该函数必须是纯函数式的,相当于函数式编程中的不可变性,即输入一致时输出一定不会改变。比如计算平方的函数就满足这种条件,square(3) 的结果永远是9,所以我们才能把它的结果存储起来,下次需要知道3的平方的结果时,无需计算,直接从内存中读取就好了。

而那些依赖于可变的参数的函数,则不可使用这种方式进行加速。比如获取系统当前登录用户数量的函数,也许参数都是固定的,但返回值却是可变的,这是由系统中即时登录的用户数量决定的,缓存起来就没意义了。

这里的缓存介质,可以是内存,可以是硬盘上的文件,可以是数据库,总之,能使之加速则认为是有效的。我们经常提及的 memcached 分布式内存对象缓存系统也是一种基于记忆化(memoization)的优化方式。今天不讲 memcached ,而是一种更简便小巧的办法,然而,它们的基本原理是一样的,它们都实现了LRU(Least Recently Used)缓存算法, 只缓存最少的最近使用过的数据。

Python内置函数缓存装饰器

@functools.lru_cache(maxsize=128, typed=False)maxsize 参数是指最大缓存多少个调用,如果赋值为 None 则是无限制缓存,且关闭 LRU 功能。typed 参数控制函数参数类型不同时是否单独缓存。设置为True时, 例如f(3)f(3.0)将会区别对待。

下面这个例子是缓存静态web内容的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from functools import lru_cache

@lru_cache(maxsize=32)
def get_pep(num):
'Retrieve text of a Python Enhancement Proposal'
resource = 'http://www.python.org/dev/peps/pep-%04d/' % num
try:
with urllib.request.urlopen(resource) as s:
return s.read()
except urllib.error.HTTPError:
return 'Not Found'

>>> for n in 8, 290, 308, 320, 8, 218, 320, 279, 289, 320, 9991:
... pep = get_pep(n)
... print(n, len(pep))

>>> get_pep.cache_info()
CacheInfo(hits=3, misses=8, maxsize=32, currsize=8)

lru_cache装饰器是Python3.2新增的,Python3.3新增了typed可选参数。

Python2的实现

Python2中没有lru_cache装饰器,但是我们可以自己实现,非常简单,如下:

1
2
3
4
5
6
7
8
9
10
11

_CACHE_VALUES = {}

def memoized(func):
def wrapper(x):
return _CACHE_VALUES.get(x, func(x))
return wrapper

@memoized
def addtwo(x):
return x+2

但我们上面这种写法太简单了,连缓存命中率这些统计都没有,而且也不通用。但明白了基本原理,我们要扩展也就不难了。更加复杂的装饰器实现可以参考《深入浅出Python装饰器》
更偷懒一点,你可以把Python源码中的lru_cahce函数相关代码拷贝到项目中,参考这里

  • 版权声明:自由转载-保留署名-禁止商用-禁止演绎(知识共享4.0许可协议)
  • 发表时间:2016-01-22 14:43:16
  • 最后更新:2016-04-20 14:00:22
  • 永久链接:http://aju.space/2016/01/22/python-memoization.html