Using functools for memoization

The Python library includes a memoization decorator in the functools module. We can use this module instead of creating our own callable object.

We can use it as follows:

from functools import lru_cache
@lru_cache(None)
def pow6( x, n ):
    if n == 0: return 1
    elif n % 2 == 1:
        return pow6(x, n-1)*x
    else: # n % 2 == 0:
        t= pow6(x, n//2)
        return t*t

This defined a function, pow6(), which is decorated with a Least Recently Used (LRU) cache. Previous requests are stored in a memoization cache. The requests are tracked in the cache, and the size is limited. The idea behind an LRU cache is that the most recently made requests are kept and the least recently made requests are quietly purged.

Using timeit, we can see that 10,000 iterations of pow5() run in about 1 second, while the iterations for pow6() run in about 8 seconds.

What this also shows is that a trivial use of timeit can misstate the performance of the memoization algorithms....