For functions which are called often, particulary recursive functions or functions which are intensive to calculate, memoizing (cacheing) the return values can dramatically improve performance.
Python, 52 lines
Note that when using the Memoize class, it is important that the value of fib is replaced by the memoized version. Storing the memoized version elsewhere, as in memoized_fib = Memoize(fib) will not work, because the recursive calls will call fib() directly, bypassing the cache.
Obviously, functions to be memoized must have no side effects, and return the same value whenever they are called with the same set of arguments.
More significantly, the Memoize class (and the inline version above) does not cater for functions which take mutable arguments, such as length() on a list. More precisely, the argument tuple must be suitable for use as a dictionary key. (Note that you can't memoize functions which change their mutable arguments, in any case). The MemoizeMutable class handles mutable arguments, by pickling the argument tuple into a constant string.