Chapter 16Raw data that includes measurements often use floating point values. Since an
exact equality comparison between floating point values may not work out well,
memoizing intermediate results may not work out well either.
Raw data that includes counts, however, may benefit from memoization.
These are integers, and we can trust exact integer comparisons to (potentially)
save recalculating a previous value. Some statistical functions, when applied to
counts, can benefit from using the fractions module instead of floating point
values. When we replace x/y with the Fraction(x,y) method, we've preserved
the ability to do exact value matching. We can produce the final result using the
float(some_fraction) method.
Specializing memoization
The essential idea of memoization is so simple that it can be captured by the
@lru_cache decorator. This decorator can be applied to any function to implement
memoization. In some cases, we might be able to improve on the generic idea with
something more specialized. There are a large number of potentially optimizable
multivalued functions. We'll pick one here and look at another in a more complex
case study.
The binomial,
n
m
, shows the number of ways n different things can be arranged in
groups of size m. The value is as follows:
()!
!!n n
m mn m
=
−Clearly, we should cache the factorial calculations rather than redo all those
multiplications. However, we may also benefit from caching the overall binomial
calculation, too.
We'll create a Callable object that contains multiple internal caches. Here's a helper
function that we'll need:
from functools import reduce
from operator import mul
prod = lambda x: reduce(mul, x)
The prod() function computes the product of an iterable of numbers. It's defined as
a reduction using the * operator.