Optimizations and Improvements
In Chapter 6, Recursions and Reductions, we looked at a few common kinds of
recursions. The simplest kind of recursion is a tail recursion with arguments that
can be easily matched to values in a cache. If the arguments are integers, strings, or
materialized collections, then we can compare arguments quickly to determine if the
cache has a previously computed result.
We can see from these examples that integer numeric calculations such as computing
factorial or locating a Fibonacci number will be obviously improved. Locating prime
factors and raising integers to powers are more examples of numeric algorithms that
apply to integer values.
When we looked at the recursive version of a Fibonacci number calculator, we saw
that it contained two tail-call recursions. Here's the definition:
FFnn=+−−1 2FnThis can be turned into a loop, but the design change requires some thinking.
The memoized version of this can be quite fast and doesn't require quite so much
thinking to design.
The Syracuse function, shown in Chapter 6, Recursions and Reductions, is an example
of the kind of function used to compute fractal values. It contains a simple rule that's
applied recursively. Exploring the Collatz conjecture ("does the Syracuse function
always lead to 1?") requires memoized intermediate results.
The recursive application of the Syracuse function is an example of a function
with an "attractor," where the value is attracted to 1. In some higher dimensional
functions, the attractor can be a line or perhaps a fractal. When the attractor is a
point, memoization can help; otherwise, memoization may actually be a hindrance,
since each fractal value is unique.
When working with collections, the benefits of caching may vanish. If the collection
happens to have the same number of integer values, strings, or tuples, then there's
a chance that the collection is a duplicate and time can be saved. However, if a
calculation on a collection will be needed more than once, manual optimization is
best: do the calculation once and assign the results to a variable.
When working with iterables, generator functions, and other lazy objects, caching of
an overall object is essentially impossible. In these cases, memoization is not going to
help at all.