The Functools Module
This binomial function involves computing three factorial values. It might make
sense to use an @lru_cache decorator on a factorial function. A program that
calculates a number of binomial values will not need to re-compute all of those
factorials. For cases where similar values are computed repeatedly, the speedup
can be impressive. For situations where the cached values are rarely reused, the
overheads of maintaining the cached values outweigh any speedups.
When computing similar values repeatedly, we see the following:
- Naive Factorial 0.174
- Cached Factorial 0.046
- Cleared Cache Factorial 1.335
If we re-calculate the same binomial with the timeit module, we'll only really do the
computation once, and return the same value the rest of the time; the cleared cache
factorial shows the impact of clearing the cache before each calculation. The cache
clearing operation—the cache_clear() function—introduces some overheads,
making it appear more costly than it actually is. The moral of the story is that an
lru_cache decorator is trivial to add. It often has a profound impact; but it may
also have no impact, depending on the distribution of the actual data.
It's important to note that the cache is a stateful object. This design pushes the
edge of the envelope on purely functional programming. A possible ideal is to
avoid assignment statements and the associated changes of state. This concept of
avoiding stateful variables is exemplified by a recursive function: the current state
is contained in the argument values, and not in the changing values of variables.
We've seen how tail-call optimization is an essential performance improvement to
assure that this idealized recursion actually works nicely with the available processor
hardware and limited memory budgets. In Python, we do this tail-call optimization
manually by replacing the tail recursions with a for loop. Caching is a similar kind
of optimization: we'll implement it manually as needed.
In principle, each call to a function with an LRU cache has two results: the
expected result and a new cache object which should be used for all future
requests. Pragmatically, we encapsulate the new cache object inside the decorated
version of the fibc() function.
Caching is not a panacea. Applications that work with float values might not
benefit much from memoization because all floats differ by small amounts.
The least-significant bits of a float value are sometimes just random noise which
prevents the exact equality test in the lru_cache decorator from working.
We'll revisit this in Chapter 16, Optimizations and Improvements. We'll look at some
additional ways to implement this.