| Next revision | Previous revision |
| teaching:cc4101:tareas:2025-1:tarea2:parte2 [2025/05/11 15:14] – created msegur | teaching:cc4101:tareas:2025-1:tarea2:parte2 [2025/05/11 19:54] (current) – [Parte 2. Memoización (2 ptos.)] msegur |
|---|
| [[teaching:cc4101:tareas:2024-1:tarea2|<< Volver]] | [[teaching:cc4101:tareas:2025-1:tarea2|<< Volver]] |
| ===== Parte 2. Memoización (2 ptos.) ===== | ===== Parte 2. Memoización (2 ptos.) ===== |
| En esta sección van a extender el lenguaje CL con un mecanismo de [[https://es.wikipedia.org/wiki/Memoizaci%C3%B3n|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. | En esta sección van a extender el lenguaje CL con un mecanismo de [[https://es.wikipedia.org/wiki/Memoizaci%C3%B3n|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. |
| * (0.2 ptos) Extienda el tipo de dato de los valores con un nuevo constructor ''mclosV'' para representar una función memoizada en tiempo de ejecución. La única diferencia con clausuras tradicionales es la presencia de una tabla de memoización. | * (0.2 ptos) Extienda el tipo de dato de los valores con un nuevo constructor ''mclosV'' para representar una función memoizada en tiempo de ejecución. La única diferencia con clausuras tradicionales es la presencia de una tabla de memoización. |
| |
| <note>La librería functools de Python posee un [[https://docs.python.org/3/library/functools.html#functools.lru_cache|decorador]] para memoizar los llamados de función y así ahorrar tiempo cuando se llama periódicamente a función con los mismos argumentos.</note> | <note> Un ejemplo de una aplicación de este concepto es la librería functools de Python, que posee un [[https://docs.python.org/3/library/functools.html#functools.lru_cache|decorador]] para memoizar los llamados de función y así ahorrar tiempo cuando se llama periódicamente a función con los mismos argumentos.</note> |
| |
| Para implementar la tabla de memoización de una función, usen una tabla de hash ([[https://docs.racket-lang.org/reference/hashtables.html|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. | Para implementar la tabla de memoización de una función, usen una tabla de hash ([[https://docs.racket-lang.org/reference/hashtables.html|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. |
| * (0.5 ptos) Usando lo realizado en la Parte 1, implemente tests que evidencien que una función memoizada efectivamente no vuelve a ejecutar su cuerpo cuando la vuelven a aplicar con el mismo argumento. | * (0.5 ptos) Usando lo realizado en la Parte 1, implemente tests que evidencien que una función memoizada efectivamente no vuelve a ejecutar su cuerpo cuando la vuelven a aplicar con el mismo argumento. |
| |
| <note important>Considere la función con memoización ''doble''. Si un programa ejecutara | <note important>Considere la función con memoización ''doble'', que evalúa su argumento dos veces. Si un programa ejecutara |
| <code>{doble {printn 3}} | <code>{doble {printn 3}} |
| {doble {printn 3}} | {doble {printn 3}} |
