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:
1 | 0, 1, 1, 2, 3, 5, 8, 13, 21... |
En forma recursiva, se podría explicar de la siguiente forma
1 | fib(n) = fib(n-1) + fib(n-1) |
La siguiente es una implementación de la función de fibonacci:
1 2 3 4 5 6 7 | def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) fib = memoize(fib) print(fib(40)) |
Tal como esta expresada la función, se podría cambiar la función memoize en un decorador, y la llamada sería distinta:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper @memoize def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print(fib(40)) |
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.
1 2 3 4 5 6 7 8 9 10 11 12 | from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print(fib(40)) |
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:
- Memoization with Decorators, en donde se puede ver el concepto y la implementación de la memorización.
- Classic Computer Science, en el capítulo 1 revisan la implementación de la función de fibonacci en diferentes formas.
- Código para Fibonacci, en GitHub.
