22

Tengo un programa para estudio de probabilidades que efectúa 10.000.000 de iteraciones. En cada iteración debe aplicar algunas pesadas formulas que incluyen el cálculo del factorial, y se está demorando mucho.

Me han dicho que debo aplicar memoización para reducir los tiempos de procesos.

¿Me podrían decir qué es y cómo lo uso?

1 respuesta 1

21

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.

5
  • 10
    La pregunta es buenisima.. pero la respuesta no es agnostica :/... aca hay mucho python, cuando deberia ser pseudocodigo o algun lenguaje totalmente inventado.. hay cosas que no existen en otros lenguajes o no funcionan asi, por lo tanto la respuesta no aplica... podes hacerla agnostica?
    – gbianchi
    Commented el 15 oct. 2020 a las 12:59
  • 2
    Estoy de acuerdo con gbianchi. La pregunta es buena pero no lenguaje-agnóstica, esta orientada a ser una respuesta para una implementación en Python. Por otro lado: ¿ Otra de las condiciones no debería ser que siempre dicha función sea llamada con los mismos argumentos ?, ¿ cual es el perjuicio de memoizar una función ? El benficio es claro: el tiempo de ejecución.
    – marmurar
    Commented el 15 oct. 2020 a las 13:16
  • 2
    @marmurar Creo que la gracia es esa, si llamas primero a factorial(100) esta memorizará los resultados para factorial(1...100). Posteriormente llamando a factorial(99) ya debería tener el resultado almacenado. El perjuicio es el gasto de memoria, si no lo controlas (en el ejemplo de la respuesta con maxsize) podría ser un problema. Commented el 15 oct. 2020 a las 13:29
  • No tendras un blog por ahi vos, con esas respuestas parece que te vendria bien abrir uno hablando de python Commented el 13 nov. 2020 a las 15:08
  • @Pablochaches. No tengo blog, no tengo nada novedoso que aportar al tema.
    – Candid Moe
    Commented el 13 nov. 2020 a las 16:04

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.