Optimizations and Improvements
Here's a Callable object with two caches that uses this prod() function:
from collections.abc import Callable
class Binomial(Callable):
def init(self):
self.fact_cache= {}
self.bin_cache= {}
def fact(self, n):
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, m):
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]
We created two caches: one for factorial values and one for binomial coefficient
values. The internal fact() method uses the fact_cache attribute. If the value isn't
in the cache, it's computed and added to the cache. The external call() method
uses the bin_cache attribute in a similar way: if a particular binomial has already
been calculated, the answer is simply returned. If not, the internal fact() method is
used to compute a new value.
We can use the preceding Callable class like this:
binom= Binomial()
binom(52,5)
2598960
This shows how we can create a Callable object from our class and then invoke the
object on a particular set of arguments. There are a number of ways that a 52-card
deck can be dealt into 5-card hands. There are 2.6 million possible hands.
Tail recursion optimizations
In Chapter 6, Recursions and Reductions, among many others, we looked at how a
simple recursion can be optimized into a for loop. The general approach is this: