What is memoization and how is it used?

Memoization is an optimization technique that avoids recalculating previously obtained results. For this, the previous results are stored; and when an already calculated result is requested, the remembered value is returned, avoiding recalculation.

Memoization applies to functions that meet two requirements:

• Idempotent. That is, funcion(n)it will always return the same value for a ndie.
• No side effects . The function must not alter the external environment. For example, you cannot change global variables, the contents of files or databases, print, etc.

A memoizable function can only call other memoizable functions.

We will use the factorial function to exemplify, starting from the traditional basic implementation that we will use as a reference:

def factorial(n):
    ''' Factorial basico
    '''
    if n > 1:
        fac = n * factorial(n - 1)
    else:
        fac = 1
    return fac

manual storage

Functions, like other objects, can have attributes, which can be dynamically created, queried, and modified. For example, a default attribute is __doc__, which returns the docstring of the function, like so:

>>>print(factorial.__doc__)
Factorial basico

Another predefined attribute, which we will take advantage of here, is __dict__, an initially empty dictionary where we will store the previously calculated factorials. The key will be the factorial number and the value, the calculated factorial.

This is the manual implementation:

def factorial_1(n):
    ''' Factorial memoizado manualmente.
    Los factoriales ya calculados se guardan en __dict__
    '''
    if n in factorial_1.__dict__:
        return factorial_1.__dict__[n]

    if n > 1:
        fac = n * factorial_1(n - 1)
    else:
        fac = 1

    factorial_1.__dict__[n] = fac
    return fac

Memoization with decorators

Manual memorization has the drawback of adding code to the function, which can lead to confusion and errors. Of course, Python has a solution for that: the @lru_cache decorator .

The use could not be simpler: it is simply added before the function, which now looks like this:

from functools import lru_cache

@lru_cache(maxsize=30)
def factorial_2(n):
    ''' Factorial con decorador
    '''
    if n > 1:
        fac = n * factorial_2(n - 1)
    else:
        fac = 1

    return fac

What we have here is the basic factorial plus the decorator.

@lru_cachehas an optional argument, maxsize, which is an estimate of the number of results to remember. The default value is 128 results, and can be increased if the problem handles a larger number of possible results.

Demonstration

We are going to try all three versions of factorial and profile using cProfile, which receives a function, executes it and prints the statistics of time, number of calls, etc.

We first define the function that will test a version of factorial. The function calcularreceives a version of factorial and the number of times to call it:

def calcular(funcion, limite):
    ''' Ejecuta una función un número de veces '''
    for n in range(limite):
        n = random.randrange(1, 30)
        fac = funcion(n)

and then we run:

limite = 10_000_000  # Diez millones de ejecuciones
print("Ejecución sin memoización:")
cProfile.run("calcular(factorial, limite)")
print("---")
print("Ejecución con memoización manual")
cProfile.run("calcular(factorial_1, limite)")
print("---")
print("Ejecución con memoización por decorador")
cProfile.run("calcular(factorial_2, limite)")

what it produces:

Ejecución sin memoización:
         191056920 function calls (51033737 primitive calls) in 49.410 seconds

Ejecución con memoización manual
         51034926 function calls (51034898 primitive calls) in 14.175 seconds

Ejecución con memoización por decorador
         41034155 function calls (41034129 primitive calls) in 11.722 seconds

Note: Only the first line of each result is shown for clarity.

As you can see, we've reduced the execution time by a fifth simply by adding a decorator to our function.