Question

memoization是指通过缓存函数返回结果来加速函数调用的一种技术。仅当函数是纯函数时结果才可以被缓存，也就是说函数不能有任何副作用或输出，也不能依赖任何全局状态。

正弦函数sin就是一个可以用来memoize化的函数，如示例10.12所示。

示例 10.12 　基本的 memoization 技术

>>> import math
>>> _SIN_MEMOIZED_VALUES = {}
>>> def memoized_sin(x):
...　　if x not in _SIN_MEMOIZED_VALUES:
...　　　　_SIN_MEMOIZED_VALUES[x] = math.sin(x)
...　　return _SIN_MEMOIZED_VALUES[x]
>>> memoized_sin(1)
0.84 14709848078965
>>> _SIN_MEMOIZED_VALUES
{1: 0.8414709848078965}
>>> memoized_sin(2)
0.90 92974268256817
>>> memoized_sin(2)
0.90 92974268256817
>>> _SIN_MEMOIZED_VALUES
{1: 0.8414709848078965, 2: 0.9092974268256817}
>>> memoized_sin(1)
0.84 14709848078965
>>> _SIN_MEMOIZED_VALUES
{1: 0.8414709848078965, 2: 0.9092974268256817}

在第一次用参数调用memoized_sin时还没有值存在_SIN_MEMOIZED_VALUES中，因此需要计算这个值并将其存储在字典中。之后，如果再次以相同的参数值调用这个函数，结果将从这个字典中获取而不需要重新计算。尽管sin函数本身计算非常快，但是这对涉及更复杂计算的高级函数并不成立。

如果已经了解了装饰器（参见7.1节），肯定可以想到装饰器用在这里正合适，这么想完全正确。PyPI包含了一些通过装饰器实现的memoization，从简单场景到最复杂且最完备的情况都有覆盖。

从Python 3.3开始，functools模块提供了一个LRU（Least-Recently-Used）缓存装饰器。它提供了同此处描述的memoization完全一样的功能，其优势在于限定了缓存的条目数，当缓存的条目数达到最大时会移除最近最少使用的条目。

该模块还提供了对缓存命中、缺失等的统计。在我看来，对于缓存来说它们都是必备的实现。如果不能对缓存的使用和效用进行衡量，那么使用memoization是毫无意义的。

示例10.13是将上面的memoized_sin函数的示例用functools.lru_cache改写后的。

示例 10.13　使用functools.lru_cache

>>> import functools
>>> import math
>>> @functools.lru_cache(maxsize=2)
... def memoized_sin(x):
...　　 return math.sin(x)
...
>>> memoized_sin(2)
0.90　92974268256817
>>> memoized_sin.cache_info()
CacheInfo(hits=0, misses=1, maxsize=2, currsize=1)
>>> memoized_sin(2)
0.90　92974268256817
>>> memoized_sin.cache_info()
CacheInfo(hits=1, misses=1, maxsize=2, currsize=1)
>>> memoized_sin(3)
0.14　11200080598672
>>> memoized_sin.cache_info()
CacheInfo(hits=1, misses=2, maxsize=2, currsize=2)
>>> memoized_sin(4)
-0.7568024953079282
>>> memoized_sin.cache_info()
CacheInfo(hits=1, misses=3, maxsize=2, currsize=2)
>>> memoized_sin(3)
0.14 11200080598672
>>> memoized_sin.cache_info()
CacheInfo(hits=2, misses=3, maxsize=2, currsize=2)
>>> memoized_sin.cache_clear()
>>> memoized_sin.cache_info()
CacheInfo(hits=0, misses=0, maxsize=2, currsize=0)