Python 指定记忆化

Python 指定记忆化，记忆化的基本思想十分简单，用@lru_cache装饰器即可捕获。可以将该装饰器应用于任何函数来实现记忆化。在某些情况下，可以用更特定的方式来改进此通用思想。下面在大量潜在可优化的多值函数中选取一个，并在更复杂的案例研究中考察另一个。
二项式

表示 n 个不同事物按组大小 m 排列方式的数量，其值如下所示：

显然，应该缓存单独计算的阶乘值，而不是重新计算所有的乘积，然而缓存整个二项式计算也可能有用。

下面创建一个包含多个内部缓存的Callable对象。需要用到的辅助函数如下：

from functools import reduce
from operator import mul
from typing import Callable, Iterable

prod: Callable[[Iterable[int]], int] = lambda x: reduce(mul, x)

函数prod()计算了可迭代数值的乘积。将它定义为了使用*运算符的归约。

以下带有两个缓存的Callable对象使用了该prod()函数。

class Binomial:
    def __init__(self):
        self.fact_cache = {}
        self.bin_cache = {}
    def fact(self, n: int) ->int:
        if n not in self.fact_cache:
            self.fact_cache[n] = prod(range(1, n+1))
        return self.fact_cache[n]
    def __call__(self, n: int, m: int) -> int:
        if (n, m) not in self.bin_cache:
            self.bin_cache[n, m] = (
                self.fact(n)//(self.fact(m)*self.fact(n-m)))
        return self.bin_cache[n, m]

上面创建了两个缓存：一个用于阶乘值，另一个用于二项式系数值。内部的fact()方法使用了fact_cache属性。如果值不在缓存中，则进行计算并将其添加到缓存中。外部的__call__()方法以类似的方式使用了bin_cache属性：如果已经计算过了特定二项式，则直接返回该值；如果没有，则会用内部的fact()方法计算一个新值。

可以如下所示使用上述Callable类：

>>> binom = Binomial()
>>> binom(52, 5)
2598960

这显示了如何从类中创建一个Callable对象，然后在特定的一组参数上调用该对象。将52张牌派分为一手5张牌，则会有260万种可能。