El término Memorización viene de la palabra latina memorándum ( recordar ), que comúnmente se abrevia como memo en inglés americano, y que significa transformar los resultados de una función en algo para recordar.
En informática, la memorización se utiliza para acelerar los programas informáticos eliminando el cálculo repetitivo de resultados y evitando llamadas repetidas a funciones que procesan la misma entrada.
¿Qué es la memorización?
Tabla de contenido
- ¿Qué es la memorización?
- ¿Por qué se utiliza la memorización?>
- ¿Dónde utilizar la memorización?
- Tipos de memorización
- ¿Cómo se utiliza la técnica de memorización en la programación dinámica?
- ¿En qué se diferencia la memorización de la tabulación?
- Problemas de práctica de codificación para la memorización
- Preguntas frecuentes
- 1) ¿Es la memorización mejor que la DP?
- 2) ¿Es la memorización lo mismo que el almacenamiento en caché?
- 3) ¿Por qué la memorización es de arriba hacia abajo?
- 4) ¿La memorización utiliza la recursividad?
- 5) ¿Debo utilizar tabulación o memorización?
- 6) ¿Dónde se utiliza la memorización?
- 7) ¿Por qué se llama memorización?
- 8) ¿Cómo reduce la memorización la complejidad del tiempo?
- 9) ¿Cuál es la diferencia entre memorización y almacenamiento en caché?
- 10) ¿Por qué la tabulación es más rápida que la memorización?
- Conclusión
¿Por qué se utiliza la memorización?
La memorización es una forma específica de almacenamiento en caché que se utiliza en programación dinámica . El propósito del almacenamiento en caché es mejorar el rendimiento de nuestros programas y mantener los datos accesibles para poder utilizarlos más adelante. Básicamente almacena el resultado calculado previamente del subproblema y utiliza el resultado almacenado para el mismo subproblema. Esto elimina el esfuerzo adicional de calcular una y otra vez para el mismo problema. Y ya sabemos que si el mismo problema ocurre una y otra vez, entonces ese problema es de naturaleza recursiva.
¿Dónde utilizar la memorización?
Podemos utilizar la técnica de memorización donde el uso de los resultados previamente calculados entra en escena. Este tipo de problema se utiliza principalmente en el contexto de recursividad , especialmente con problemas que involucran subproblemas superpuestos .
Tomemos un ejemplo en el que el mismo subproblema se repite una y otra vez.
Ejemplo para mostrar dónde utilizar la memorización:
Let us try to find the factorial of a number .>
A continuación se muestra un método recursivo para encontrar el factorial de un número:
int factorial (int sin signo n)
{
si (n == 0)
devolver 1;
devolver n * factorial(n – 1);
}
¿Qué pasa si utilizamos este método recursivo?
Si escribe el código completo para el fragmento anterior, notará que habrá 2 métodos en el código:
1. factorial(n) 2. main()>
Ahora, si tenemos varias consultas para encontrar el factorial, como encontrar el factorial de 2, 3, 9 y 5, entonces necesitaremos llamar al método factorial() 4 veces:
factorial(2) factorial(3) factorial(9) factorial(5)>
Método recursivo para encontrar Factorial
Por lo tanto, es seguro decir que para encontrar factoriales de números K, la complejidad temporal necesaria será O(N*K)
- EN) para encontrar el factorial de un número particular, y
- FLECHA) para llamar al método factorial() K diferentes veces.
¿Cómo puede ayudar la memorización con estos problemas?
Si notamos en el problema anterior, mientras calculamos el factorial de 9:
algoritmo de cabina
- Estamos calculando el factorial de 2.
- También estamos calculando el factorial de 3,
- y también estamos calculando el factorial de 5
Por lo tanto, si almacenamos el resultado de cada factorial individual en el primer momento del cálculo, podemos devolver fácilmente el factorial de cualquier número requerido en solo O(1) tiempo. Este proceso se conoce como Memorización .
Solución mediante Memoización (¿Cómo funciona la memorización?):
Si primero encontramos el factorial de 9 y almacenamos los resultados de los subproblemas individuales, podemos imprimir fácilmente el factorial de cada entrada en O(1).
Por lo tanto, la complejidad temporal para encontrar números factoriales usando la memorización será EN)
- EN) para encontrar el factorial de la entrada más grande
- O(1) para imprimir el factorial de cada entrada.
Tipos de memorización
La implementación de la memorización depende de los parámetros cambiantes que son responsables de resolver el problema. Hay varias dimensiones de almacenamiento en caché que se utilizan en la técnica de memorización. A continuación se muestran algunas de ellas:
- Memorización 1D: La función recursiva que tiene un solo argumento cuyo valor no era constante después de cada llamada a la función.
- Memorización 2D: La función recursiva que tiene solo dos argumentos cuyo valor no era constante después de cada llamada a la función.
- Memorización 3D : La función recursiva que tiene solo tres argumentos cuyos valores no fueron constantes después de cada llamada a la función.
¿Cómo se utiliza la técnica de memorización en la programación dinámica?
La programación dinámica ayuda a resolver eficientemente problemas que tienen subproblemas superpuestos y propiedades de subestructura óptimas. La idea detrás de la programación dinámica es dividir el problema en subproblemas más pequeños y guardar el resultado para uso futuro, eliminando así la necesidad de calcular el resultado repetidamente.
Hay dos enfoques para formular una solución de programación dinámica:
- Enfoque de arriba hacia abajo: Este enfoque sigue el memorización técnica . Consiste en recursividad y almacenamiento en caché . En informática, la recursividad representa el proceso de llamar funciones repetidamente, mientras que el caché se refiere al proceso de almacenar resultados intermedios.
- Enfoque de abajo hacia arriba: Este enfoque utiliza el tabulación técnica para implementar la solución de programación dinámica. Aborda los mismos problemas que antes, pero sin recursividad. En este enfoque, la iteración reemplaza a la recursividad. Por lo tanto, no hay errores de desbordamiento de pila ni sobrecarga de procedimientos recursivos.
Cómo se utiliza la técnica de memorización en la programación dinámica
¿En qué se diferencia la memorización de la tabulación?
Tabulación versus memorización
Para obtener más detalles, consulte: Tabulación versus memorización
Problemas de práctica de codificación sobre memorización
| Pregunta | Artículo | Práctica | Video |
|---|---|---|---|
| Cuente las formas de llegar a la enésima escalera | Vista | Resolver | Mirar |
| Problema de ruptura de palabras | DP-32 | Vista | Resolver | Mirar |
| Programa para números de Fibonacci | Vista | Resolver | Mirar |
| enésimo número catalán | Vista | Resolver | Mirar |
| Problema de la mina de oro | Vista | Resolver | Mirar |
| Problema de suma de subconjuntos | Vista | Resolver | Mirar |
| Cortar una varilla | Vista | Resolver | Mirar |
| Ruta de costo mínimo | Vista | Resolver | Mirar |
| Número mínimo de saltos para llegar al final. | Vista | Resolver | Mirar |
| Subcadena palindrómica más larga | Serie 1 | Vista | Resolver | Mirar |
| Subsecuencia repetida más larga | Vista | Resolver | Mirar |
| Cuente las formas de llegar a la enésima escalera usando el paso 1, 2 o 3 | Vista | Resolver | Mirar |
| Recuento de diferentes formas de expresar N como suma de 1, 3 y 4 | Vista | Resolver | Mirar |
| Contar el número de formas de cubrir una distancia. | Vista | Resolver | Mirar |
| Recuento de matrices que tienen elementos consecutivos con diferentes valores | Vista | Resolver | Mirar |
| Subarreglo contiguo de suma más grande | Vista | Resolver | Mirar |
| Subarreglo contiguo de suma más pequeña | Vista | Resolver | Mirar |
| Caminos únicos en una cuadrícula con obstáculos | Vista | Resolver | Mirar |
| Diferentes formas de sumar n usando números mayores o iguales a m | Vista | Resolver | Mirar |
Preguntas frecuentes (FAQ) sobre la memorización
1: ¿Es la memorización mejor que la DP?
La memorización es el enfoque de arriba hacia abajo para resolver un problema con programación dinámica. Se llama memorización porque crearemos una nota para los valores obtenidos al resolver cada problema.
2: ¿Es la memorización lo mismo que el almacenamiento en caché?
La memorización es en realidad un tipo específico de almacenamiento en caché. El término almacenamiento en caché generalmente puede referirse a cualquier técnica de almacenamiento (como el almacenamiento en caché HTTP) para uso futuro, pero memorizar se refiere más específicamente a la función de almacenamiento en caché que devuelve el valor.
3: ¿Por qué la memorización es de arriba hacia abajo?
El enfoque de arriba hacia abajo divide el gran problema en múltiples subproblemas. Si el subproblema ya está resuelto, reutilice la respuesta. De lo contrario, resuelva el subproblema y almacene el resultado en alguna memoria.
4: ¿La memorización utiliza la recursividad?
La memorización sigue un enfoque de arriba hacia abajo para resolver el problema. Consiste en recursividad y almacenamiento en caché. En informática, la recursividad representa el proceso de llamar funciones repetidamente, mientras que el caché se refiere al proceso de almacenar resultados intermedios.
5: ¿Debo utilizar tabulación o memorización?
Para problemas que requieren que se resuelvan todos los subproblemas, la tabulación generalmente supera a la memorización por un factor constante. Esto se debe a que la tabulación no tiene una sobrecarga de recursividad, lo que reduce el tiempo para resolver la pila de llamadas de recursividad desde la memoria de la pila.
Siempre que es necesario resolver un subproblema para resolver el problema original, es preferible la memorización, ya que un subproblema se resuelve de forma perezosa, es decir, solo se realizan los cálculos necesarios.
6: ¿Dónde se utiliza la memorización?
La memorización es una técnica de optimización que se utiliza para acelerar los programas informáticos almacenando en caché los resultados de costosas llamadas a funciones y devolviéndolos cuando se vuelven a encontrar las mismas entradas.
7: ¿Por qué se llama memorización?
El término memorización proviene de la palabra latina memorándum (recordar), que comúnmente se abrevia a memo en inglés americano, y que significa transformar los resultados de una función en algo para recordar.
8: ¿Cómo reduce la memorización la complejidad del tiempo?
Resolver el mismo problema una y otra vez lleva tiempo y aumenta la complejidad del tiempo de ejecución del programa en general. Este problema se puede resolver manteniendo algo de caché o memoria donde almacenaremos el resultado ya calculado del problema para alguna entrada en particular. De modo que si no queremos volver a calcular el mismo problema, simplemente podemos usar el resultado almacenado en la memoria y reducir la complejidad del tiempo.
cadena inversa en java
9: ¿Cuál es la diferencia entre memorización y almacenamiento en caché?
La memorización es en realidad un tipo específico de almacenamiento en caché que implica almacenar en caché el valor de retorno de una función según la entrada. El almacenamiento en caché es un término más general. Por ejemplo, el almacenamiento en caché HTTP es almacenamiento en caché pero no es memorización.
10: ¿Por qué la tabulación es más rápida que la memorización?
La tabulación suele ser más rápida que la memorización porque es iterativa y la resolución de subproblemas no requiere llamadas recursivas.
La memorización es una técnica utilizada en informática para acelerar la ejecución de funciones recursivas o computacionalmente costosas al almacenar en caché los resultados de las llamadas a funciones y devolver los resultados almacenados en caché cuando se repiten las mismas entradas.
La idea básica de la memorización es almacenar la salida de una función para un conjunto determinado de entradas y devolver el resultado almacenado en caché si la función se llama nuevamente con las mismas entradas. Esta técnica puede ahorrar tiempo de cálculo, especialmente para funciones que se llaman con frecuencia o tienen una gran complejidad de tiempo.
Aquí hay una guía paso a paso para implementar la memorización:
Identifique la función que desea optimizar mediante la memorización. Esta función debería tener cálculos repetidos y costosos para la misma entrada.
Cree un objeto de diccionario para almacenar los resultados almacenados en caché de la función. Las claves del diccionario deben ser los parámetros de entrada de la función y los valores deben ser los resultados calculados.
Al comienzo de la función, verifique si los parámetros de entrada ya están presentes en el diccionario de caché. Si es así, devuelve el resultado almacenado en caché.
Si los parámetros de entrada no están en el diccionario de caché, calcule el resultado y guárdelo en el diccionario de caché con los parámetros de entrada como clave.
Devuelve el resultado calculado.
Aquí hay un ejemplo de código Python sobre cómo implementar la memorización usando un diccionario:
Python3
def> fibonacci(n, cache>=>{}):> >if> n>in> cache:> >return> cache[n]> >if> n>=>=> 0>:> >result>=> 0> >elif> n>=>=> 1>:> >result>=> 1> >else>:> >result>=> fibonacci(n>->1>)>+> fibonacci(n>->2>)> >cache[n]>=> result> >return> result> |
>
>Producción
>
En el código anterior, definimos una función llamada fibonacci que calcula el enésimo número en la secuencia de Fibonacci. Usamos un objeto de diccionario llamado caché para almacenar los resultados de las llamadas a funciones. Si el parámetro de entrada n ya está presente en el diccionario de caché, devolvemos el resultado almacenado en caché. De lo contrario, calculamos el resultado mediante llamadas recursivas a la función de Fibonacci y lo almacenamos en el diccionario de caché antes de devolverlo.
La memorización se puede utilizar para optimizar el rendimiento de muchas funciones que implican cálculos repetidos y costosos. Al almacenar en caché los resultados de las llamadas a funciones, podemos evitar cálculos innecesarios y acelerar la ejecución de la función.
Conclusión
La memorización es un concepto de programación y se puede aplicar a cualquier lenguaje de programación. Su objetivo absoluto es optimizar el programa. Generalmente, este problema se observa cuando los programas realizan cálculos pesados. Esta técnica almacena en caché todo el resultado anterior calculado para que no tenga que volver a calcularse para el mismo problema.
Artículos relacionados:
- Memoización usando decoradores en Python
- Memorización de JavaScript