<< Volver

Parte 2. Memoización (2 ptos.)

En esta sección van a extender el lenguaje CL con un mecanismo de memoización. La memoización es una técnica de optimización que permite evaluar más rápidamente llamadas a funciones. Una función memoizada tiene asociada una estructura (p.ej. tabla de hash) donde se van guardando los argumentos con que se aplica la función y el resultado de evaluar la función con esos argumento. Luego, si se realiza una nueva aplicación con el mismo argumento, basta con acceder a la memoria para obtener el valor resultante, sin tener que evaluar todo el cuerpo de la función de nuevo.

La librería functools de Python posee un decorador para memoizar los llamados de función y así ahorrar tiempo cuando se llama periódicamente a función con los mismos argumentos.

Para implementar la tabla de memoización de una función, usen una tabla de hash (documentación), que permite asociar llaves a valores (las llaves y valores pueden ser de cualquier tipo). A continuación, les dejamos un resumen de la interfaz.

> (define my-table (make-hash)) ;; Crea una tabla de hash nueva, vacía
> (hash-set! my-table "key1" 23) ;; Agrega una llave "key1" asociada al valor 23 
> (hash-ref my-table "key1") ;; Accede al valor asociado a la llave "key1", si es que existe
23
> (hash-has-key? my-table "key1") ;; Chequea si la llave "key1" está definida en la tabla
#t
Considere la función con memoización doble. Si un programa ejecutara
{doble {printn 3}}
{doble {printn 3}}

¿Cuántas veces debería imprimirse el número 3? Piense en la solución antes de ver la respuesta. 1)

Observaciones:

1)
Se debe imprimir dos veces, CL siempre usa evaluación temprana. Por ende, la función doble recibe 3, después de que se hace printn. Para la segunda aplicación recibe 3, también después de imprimir con printn. Al recibir el 3 por segunda vez, responde lo que tiene en memoria, pero en este punto el 3 ya fue impreso por segunda vez.
2)
ver documentación sobre hash tables y valores mutables.
3)
ver documentación sobre igualdad de estructuras y mutación.