Python specified memoization

Python Specified Memoization. The basic idea of memoization is very simple and can be captured using the @lru_cache decorator. This decorator can be applied to any function to implement memoization. In some cases, this general idea can be improved in more specific ways. Below, we will select one of the many potentially optimizable multi-valued functions and examine another in a more complex case study.
Binomial

The number of ways to arrange n different things by group size m is as follows:

Obviously, you should cache individual factorial values rather than recalculating all products. However, caching the entire binomial calculation may also be useful.

The following creates a Callable object that contains several internal caches. The helper functions needed are as follows:

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

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

The function prod() computes the product of iterable values. It is defined to perform a reduction using the * operator.

The following Callable object with two buffers uses the prod() function.

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]

This creates two caches: one for factorial values and one for binomial coefficient values. The inner fact() method uses the fact_cache attribute. If the value isn’t already in the cache, it’s calculated and added to the cache. The outer __call__() method uses the bin_cache attribute in a similar way: if the binomial has already been calculated, that value is returned; if not, a new value is calculated using the inner fact() method.

The above Callable class can be used as follows:

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

This shows how to create a Callable object from a class and then call it on a specific set of parameters. There are 2.6 million possible ways to deal 52 cards into a hand of 5.