Memorización

El termino «memorización» fue introducido por Donald Michie en 1968. La memorización es una técnica utilizada en la informática para acelerar los programas. Esto se logra memorizando los resultados del cálculo de la entrada procesada, como los resultados de las llamadas a funciones. Si se usa la misma entrada o una llamada de función con los mismos parámetros, los resultados almacenados previamente se pueden usar nuevamente y se evitan los cálculos innecesarios. En muchos casos, se usa una matriz simple para almacenar los resultados, pero también se pueden usar otras estructuras, como matrices asociativas, denominadas diccionarios en Python.

El programador puede programar explícitamente la memorización, pero algunos lenguajes de programación como Python proporcionan mecanismos para memorizar funciones automáticamente.

Memorización con Decoradores

Para explicar el uso de la memorización utilizaremos la serie de fibonacci:

 

En forma recursiva, se podría explicar de la siguiente forma 

La siguiente es una implementación de la función de fibonacci:

También presentamos una forma de mejorar el comportamiento en tiempo de ejecución de la versión recursiva al agregar un diccionario para memorizar los valores de la función calculados previamente. Este es un ejemplo explícito de la técnica de memorización, la desventaja de este método es que se pierde la claridad y la belleza de la implementación recursiva. 

El «problema» es que cambiamos el código de la función recursiva de fib. El siguiente código no cambia la función fib, por lo que no toca su claridad y legibilidad. Para este propósito, definimos y usamos una función que llamamos memorizar: memoize(). Esta nueva función memoize() toma una función como argumento. La función memorizar utiliza un diccionario «memo» para almacenar los resultados de la función.

Tal como esta expresada la función, se podría cambiar la función memoize en un decorador, y la llamada sería distinta:

En este caso particular, el usar el decorador de memorización nos ayuda, más Python ya tiene un decorador para memorización de cualquier función en forma auto-mágica. El decorador es @functools.lru_cache(), que se puede utilizar con el mismo código, sin tener que construir el decorador por nuestra cuenta.

La propiedad maxsize de @lru_cache indica cuántas de las llamadas más recientes de la función que está decorando deben almacenarse en caché. Establecerlo en None indica que no hay límite.

Conclusiones:

En el uso de recursividad, muchas veces la cantidad de ejecuciones genera que el código no se pueda ejecutar correctamente por el número de veces que la función se llama a sí misma. 

En el caso de Python, se puede utilizar el concepto de memorización para ayudarnos con la ejecución, el decorador @lru_cache, nos ayuda en estos casos.

Como referencia y para complementar la información, pueden revisar:

Python: Memorización con Decoradores
Si te gusto, comparte ...Email this to someone
email
Share on Facebook
Facebook
Tweet about this on Twitter
Twitter
Share on LinkedIn
Linkedin
Etiquetado en:

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Facebook