Memoización
En Informática, el término memoización (del inglés memoization) es una técnica de optimización que se usa principalmente para acelerar los tiempos de cálculo, almacenando los resultados de la llamada a una subrutina en una memoria intermedia o búfer y devolviendo esos mismos valores cuando se llame de nuevo a la subrutina o función con los mismos parámetros de entrada.
La memoización también se puede usar en otras situaciones, y con propósitos diferentes del de reducir tiempos de computación, como por ejemplo en la recursión mutua de un analizador sintáctico o parser descendente.[1]
Aunque está fuertemente vinculada con el concepto de caché, la memoización se refiere a un uso específico de esta, distinguiéndose de otros casos de uso como un buffer o un algoritmo de reemplazo de páginas. En el contexto de algunos lenguajes de programación lógica, como por ejemplo Prolog, la técnica de memoización suele ser denominada tabulación o tabling.[2]
Etimología
[editar]El término "memoization" fue utilizado por primera vez por Donald Michie en 1968[3] y deriva del latín memorandum ("que debe ser recordado"), ya que se describe como "convertir [el resultado de] una función en algo a ser recordado".
Aunque "memoización" puede ser confundida con "memorización", el término memoización tiene un uso exclusivo y específico en el desarrollo informático.
Visión general
[editar]Una función memoizada "recuerda" los resultados correspondientes a un determinado conjunto de valores de entrada. Posteriores llamadas que usen los mismos valores obtendrán el resultado previamente almacenado, en vez de realizar todo el cálculo de nuevo. De esta forma se evitan todos los cálculos, excepto el realizado en la primera llamada. El conjunto de asociaciones de valores de entrada con resultados puede ser de tamaño fijo y controlado por un algoritmo de reemplazo, dependiendo de la naturaleza de la función y de su uso.
Una función solo puede ser memoizada si cumple la condición de transparencia referencial, es decir, que el resultado de realizar la llamada a la función produce el mismo efecto que reemplazar la llamada a la función por el valor devuelto. En otras palabras, que no se produzcan dentro de la función efectos colaterales.
Referencias
[editar]- ↑ Norvig, Peter (1991). «Techniques for Automatic Memoization with Applications to Context-Free Parsing». Computational Linguistics 17 (1): 91-98.
- ↑ Warren, David. «Tabling and Datalog Programming». Consultado el 29 de mayo de 2009.
- ↑ Michie, Donald (1968). «'Memo' Functions and Machine Learning». Nature 218 (5136): 19-22. Bibcode:1968Natur.218...19M. doi:10.1038/218019a0.
| Control de autoridades |
|
|---|
Datos: Q1376168