¿Qué es memoización y cómo se usa?

Memoización es una técnica de optimización que evita recalcular resultados previamente obtenidos. Para esto, los resultados anteriores se almacenan; y cuando se pide un resultado ya calculado, se retorna el valor recordado, evitando recalcularlo.

La memoización se aplica a funciones que cumplan dos requisitos:

• Idempotentes. Es decir, funcion(n) siempre retornara el mismo valor para un n dado.
• Sin efectos secundarios. La función no debe alterar el ambiente externo. Por ejemplo, no puede cambiar variables globales, el contenido de archivos o bases de datos, imprimir, etc.

Una función memoizable sólo puede llamar a otras funciones memoizables.

Usaremos la función factorial para ejemplificar, partiendo de la implementación básica tradicional que usaremos como referencia:

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

Memoización manual

Las funciones, como otros objetos, pueden tener atributos, los que pueden ser creados, consultados y modificados dinámicamente. Por ejemplo, un atributo predefinido es __doc__, que retorna el docstring de la función, así:

>>>print(factorial.__doc__)
Factorial basico

Otro atributo predefinido, que aprovecharemos aquí, es __dict__, un diccionario inicialmente vacío donde guardaremos los factoriales previamente calculado. La llave será el número de factorial y el valor, el factorial calculado.

Esta es la implementación manual:

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

Memoizacion con decoradores

La memoización manual tiene el inconveniente de agregar código a la función, lo que se puede prestar para confusiones y errores. Por supuesto, Python tiene una solución para eso: el decorador @lru_cache.

El uso no puede ser más simple: simplemente se agrega antes de la función, que ahora queda asi:

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

Lo que tenemos aquí es el factorial básico más el decorador.

@lru_cache tiene un argumento opcional, maxsize, que es una estimación del número de resultados a recordar. El valor por omisión es 128 resultados, y se puede aumentar si el problema manejara un mayor número de resultados posibles.

Demostración

Vamos a probar las tres versiones de factorial y perfilaras usando cProfile, que recibe una función, la ejecuta e imprime las estadísticas de tiempo, número de llamadas, etc.

Primero definimos la función que pondrá a prueba una versión de factorial. La función calcular recibe una versión de factorial y el número de veces que debe invocarla:

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)

y luego ejecutamos:

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)")

lo que produce:

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

Nota: sólo se muestra la primera línea de cada resultado para mayor claridad.

Como se aprecia, hemos reducido el tiempo de ejecución a la quinta parte simplemente agregando un decorador a nuestra función.