Memoization / lookup tables

This is one of the most common techniques used to improve the performance of a piece of code (namely a function). We can save the results of expensive function calls associated with a specific set of input values and return the saved result (instead of redoing the whole computation) when the function is called with the remembered input. It might be confused with caching, since this is one type of memoization, although this term also refers to other types of optimization (such as HTTP caching, buffering, and so on).

This methodology is very powerful because in practice, it'll turn what should have been a potentially very expensive call into a O(1) function call (for more information about this, refer to Chapter 1, Profiling 101) if the implementation is right. Normally, the parameters are used to create a unique key, which is then used on a dictionary to either save the result or obtain it if it's been already saved.

There is, of course, a trade-off to...