El terme Memoització prové de la paraula llatina memoràndum ( recordar ), que s'abreuja habitualment a memo en anglès americà, i que significa transformar els resultats d'una funció en alguna cosa per recordar.
En informàtica, la memorització s'utilitza per accelerar els programes informàtics eliminant el càlcul repetitiu dels resultats i evitant les trucades repetides a funcions que processen la mateixa entrada.
Què és la memoització
Taula de continguts
- Què és la Memoization?
- Per què s'utilitza Memoization>
- On utilitzar Memoization?
- Tipus de memorització
- Com s'utilitza la tècnica de memorització en la programació dinàmica?
- Com és diferent la memorització de la tabulació?
- Problemes de pràctica de codificació per a la memorització
- Preguntes freqüents
- 1) És millor la memoització que la DP?
- 2) La memòria és el mateix que la memòria cau?
- 3) Per què la memoització és de dalt a baix?
- 4) La memorització utilitza recursivitat?
- 5) He d'utilitzar la tabulació o la memoització?
- 6) On s'utilitza la memoització?
- 7) Per què s'anomena memoització?
- 8) Com la memorització redueix la complexitat del temps?
- 9) Quina diferència hi ha entre la memòria cau i la memòria cau?
- 10) Per què la tabulació és més ràpida que la memorització?
- Conclusió
Per què s'utilitza Memoization?
La memorització és una forma específica de memòria cau que s'utilitza en programació dinàmica . L'objectiu de la memòria cau és millorar el rendiment dels nostres programes i mantenir les dades accessibles que es poden utilitzar més endavant. Bàsicament emmagatzema el resultat calculat prèviament del subproblema i utilitza el resultat emmagatzemat per al mateix subproblema. Això elimina l'esforç addicional per calcular una i altra vegada per al mateix problema. I ja sabem que si el mateix problema es repeteix una i altra vegada, llavors aquest problema és recursiu per naturalesa.
On utilitzar Memoization?
Podem utilitzar la tècnica de memoització on el ús dels resultats calculats prèviament entra a la imatge. Aquest tipus de problema s'utilitza principalment en el context de recursivitat , especialment amb problemes que impliquen subproblemes superposats .
Prenguem un exemple en què el mateix subproblema es repeteix una i altra vegada.
Exemple per mostrar on utilitzar la memòria:
Let us try to find the factorial of a number .>
A continuació hi ha a mètode recursiu per trobar el factorial d'un nombre:
int factorial (unsigned int n)
{
si (n == 0)
retorn 1;
retornar n * factorial (n – 1);
}
Què passa si utilitzem aquest mètode recursiu?
Si escriviu el codi complet del fragment anterior, notareu que hi haurà 2 mètodes al codi:
1. factorial(n) 2. main()>
Ara, si tenim diverses consultes per trobar el factorial, com ara trobar el factorial de 2, 3, 9 i 5, haurem de cridar el mètode factorial() 4 vegades:
factorial(2) factorial(3) factorial(9) factorial(5)>
Mètode recursiu per trobar factorial
Per tant, és segur dir que per trobar el factorial de nombres K nombres, la complexitat temporal necessària serà O(N*K)
- O(N) trobar el factorial d'un nombre determinat, i
- FLECHA) cridar el mètode factorial() K vegades diferents.
Com la Memoization pot ajudar amb aquests problemes?
Si observem en el problema anterior, mentre es calcula el factorial de 9:
c matriu de cadenes del programa
- Estem calculant el factorial de 2
- També estem calculant el factorial de 3,
- i estem calculant també el factorial de 5
Per tant, si emmagatzemem el resultat de cada factorial individual en el primer moment del càlcul, podem retornar fàcilment el factorial de qualsevol nombre requerit en només O(1) temps. Aquest procés es coneix com Memoització .
Solució mitjançant Memoization (Com funciona la memoization?):
Si primer trobem el factorial de 9 i emmagatzemem els resultats dels subproblemes individuals, podem imprimir fàcilment el factorial de cada entrada a O(1).
Per tant, la complexitat temporal per trobar nombres factorials mitjançant la memoització serà O(N)
- O(N) per trobar el factorial de l'entrada més gran
- O(1) per imprimir el factorial de cada entrada.
Tipus de memorització
La implementació de la memoització depèn dels paràmetres canviants que són responsables de resoldre el problema. Hi ha diverses dimensions de la memòria cau que s'utilitzen en la tècnica de memorització, a continuació es mostren algunes d'elles:
- Memoització 1D: La funció recursiva que només té un argument el valor del qual no era constant després de cada trucada de funció.
- Memorització 2D: La funció recursiva que només té dos arguments el valor dels quals no era constant després de cada trucada de funció.
- Memoització 3D : La funció recursiva que només té tres arguments els valors dels quals no eren constants després de cada trucada de funció.
Com s'utilitza la tècnica de Memoization a la Programació Dinàmica?
La programació dinàmica ajuda a resoldre de manera eficient problemes que tenen subproblemes superposats i propietats de subestructura òptimes. La idea darrere de la programació dinàmica és dividir el problema en subproblemes més petits i guardar el resultat per a un ús futur, eliminant així la necessitat de calcular el resultat repetidament.
Hi ha dos enfocaments per formular una solució de programació dinàmica:
- Enfocament de dalt a baix: Aquest enfocament segueix el memorització tècnica . Consisteix en recursivitat i memòria cau . En computació, la recursivitat representa el procés de cridar funcions repetidament, mentre que la memòria cau es refereix al procés d'emmagatzemar resultats intermedis.
- Enfocament de baix a dalt: Aquest enfocament utilitza el tabulació tècnica per implementar la solució de programació dinàmica. Aborda els mateixos problemes que abans, però sense recursivitat. En aquest enfocament, la iteració substitueix la recursivitat. Per tant, no hi ha cap error de desbordament de pila ni sobrecàrrega dels procediments recursius.
Com s'utilitza la tècnica de Memoization a la Programació Dinàmica
En què és diferent la Memoization de la Tabulació?
Tabulació vs memorització
Per a més detalls, consulteu: Tabulació vs
Problemes de pràctica de codificació sobre memorització
| Pregunta | Article | Pràctica | Vídeo |
|---|---|---|---|
| Compteu les maneres d'arribar a l'escala n' | Veure | Resol | Veure |
| Problema de trencament de paraules | DP-32 | Veure | Resol | Veure |
| Programa per als nombres de Fibonacci | Veure | Resol | Veure |
| nè Número català | Veure | Resol | Veure |
| Problema de la mina d'or | Veure | Resol | Veure |
| Problema de la suma del subconjunt | Veure | Resol | Veure |
| Tallar una vareta | Veure | Resol | Veure |
| Ruta del cost mínim | Veure | Resol | Veure |
| Nombre mínim de salts per arribar al final | Veure | Resol | Veure |
| Subcadena palindròmica més llarga | Set 1 | Veure | Resol | Veure |
| Subseqüència repetida més llarga | Veure | Resol | Veure |
| Compteu les maneres d'arribar a l'enèsima escala mitjançant el pas 1, 2 o 3 | Veure | Resol | Veure |
| Recompte de diferents maneres d'expressar N com la suma d'1, 3 i 4 | Veure | Resol | Veure |
| Comptar el nombre de maneres de cobrir una distància | Veure | Resol | Veure |
| Recompte de matrius que tenen elements consecutius amb valors diferents | Veure | Resol | Veure |
| Suma més gran Subbarray contigu què és un monitor | Veure | Resol | Veure |
| Suma més petita subarray contigua | Veure | Resol | Veure |
| Camins únics en una quadrícula amb obstacles | Veure | Resol | Veure |
| Diferents maneres de sumar n utilitzant nombres majors o iguals a m | Veure | Resol | Veure |
Preguntes freqüents (FAQ) sobre Memoization
1: És millor la memorització que la DP?
La memorització és l'enfocament de dalt a baix per resoldre un problema amb la programació dinàmica. S'anomena memoització perquè crearem una nota per als valors retornats de resoldre cada problema.
2: La memòria és el mateix que la memòria cau?
La memorització és en realitat un tipus específic de memòria cau. El terme memòria cau generalment pot referir-se a qualsevol tècnica d'emmagatzematge (com la memòria cau HTTP) per a un ús futur, però la memòria cau es refereix més específicament a la funció de memòria cau que retorna el valor.
3: Per què la memorització és de dalt a baix?
L'enfocament de dalt a baix divideix el gran problema en múltiples subproblemes. si el subproblema ja està resolt, reutilitza la resposta. En cas contrari, resoleu el subproblema i emmagatzemeu el resultat en una mica de memòria.
4: La memorització utilitza recursivitat?
La memorització segueix un enfocament de dalt a baix per resoldre el problema. Consisteix en recursivitat i memòria cau. En computació, la recursivitat representa el procés de cridar funcions repetidament, mentre que la memòria cau es refereix al procés d'emmagatzemar resultats intermedis.
5: He d'utilitzar la tabulació o la memòria?
Per als problemes que requereixen la resolució de tots els subproblemes, la tabulació normalment supera la memòria per un factor constant. Això es deu al fet que la tabulació no té cap sobrecàrrega de recursivitat, la qual cosa redueix el temps per resoldre la pila de trucades de recursivitat des de la memòria de la pila.
Sempre que cal resoldre un subproblema per resoldre el problema original, és preferible la memorització, ja que un subproblema es resol de manera mandrosa, és a dir, només es fan els càlculs que es requereixen.
6: On s'utilitza la memoització?
La memorització és una tècnica d'optimització que s'utilitza per accelerar els programes informàtics mitjançant la memòria cau dels resultats de les trucades de funcions cares i retornant-los quan es tornen a trobar les mateixes entrades.
7: Per què es diu memoització?
El terme memoització prové de la paraula llatina memorandum (recordar), que s'abreuja habitualment a memo en anglès americà, i que significa transformar els resultats d'una funció en alguna cosa per recordar.
8: Com la memorització redueix la complexitat del temps?
La resolució del mateix problema una vegada i una altra requereix temps i augmenta la complexitat d'execució del programa en general. Aquest problema es pot resoldre mantenint una mica de memòria cau o memòria on emmagatzemarem el resultat ja calculat del problema per a alguna entrada concreta. De manera que si no volem tornar a calcular el mateix problema, podem simplement utilitzar el resultat que s'emmagatzema a la memòria i reduir la complexitat del temps.
9: Quina diferència hi ha entre la memòria cau i la memòria cau?
La memorització és en realitat un tipus específic d'emmagatzematge a la memòria cau que implica la memòria cau del valor de retorn d'una funció basat en l'entrada. La memòria cau és un terme més general. Per exemple, la memòria cau HTTP és la memòria cau però no la memòria.
10: Per què la tabulació és més ràpida que la memorització?
La tabulació sol ser més ràpida que la memorització, perquè és iterativa i la resolució de subproblemes no requereix cap sobrecàrrega de trucades recursives.
La memorització és una tècnica que s'utilitza en informàtica per accelerar l'execució de funcions recursives o computacionalment costoses mitjançant l'emmagatzematge en memòria cau dels resultats de les trucades de funció i retornant els resultats a la memòria cau quan es tornen a produir les mateixes entrades.
La idea bàsica de la memòria és emmagatzemar la sortida d'una funció per a un conjunt determinat d'entrades i retornar el resultat de la memòria cau si es torna a cridar la funció amb les mateixes entrades. Aquesta tècnica pot estalviar temps de càlcul, especialment per a funcions que s'anomenen amb freqüència o que tenen una gran complexitat temporal.
Aquí teniu una guia pas a pas per implementar la memoització:
Identifiqueu la funció que voleu optimitzar mitjançant la memòria. Aquesta funció hauria de tenir càlculs repetits i costosos per a la mateixa entrada.
Creeu un objecte de diccionari per emmagatzemar els resultats a la memòria cau de la funció. Les claus del diccionari han de ser els paràmetres d'entrada de la funció i els valors han de ser els resultats calculats.
Al començament de la funció, comproveu si els paràmetres d'entrada ja estan presents al diccionari de la memòria cau. Si ho són, retorneu el resultat de la memòria cau.
Si els paràmetres d'entrada no es troben al diccionari de la memòria cau, calculeu el resultat i deseu-lo al diccionari de la memòria cau amb els paràmetres d'entrada com a clau.
Retorna el resultat calculat.
Aquí hi ha un exemple de codi Python d'implementació de la memoització mitjançant un diccionari:
Python 3
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> |
>
>Sortida
>
Al codi anterior, definim una funció anomenada Fibonacci que calcula l'enèsim nombre de la seqüència de Fibonacci. Utilitzem un objecte de diccionari anomenat cache per emmagatzemar els resultats de les trucades de funció. Si el paràmetre d'entrada n ja està present al diccionari de la memòria cau, retornem el resultat de la memòria cau. En cas contrari, calculem el resultat mitjançant trucades recursives a la funció de Fibonacci i l'emmagatzemem al diccionari de la memòria cau abans de retornar-lo.
La memorització es pot utilitzar per optimitzar el rendiment de moltes funcions que tenen càlculs repetits i costosos. Si emmagatzemen a la memòria cau els resultats de les trucades de funció, podem evitar càlculs innecessaris i accelerar l'execució de la funció.
Conclusió
La memorització és un concepte de programació i es pot aplicar a qualsevol llenguatge de programació. El seu objectiu absolut és optimitzar el programa. Normalment, aquest problema es veu quan els programes realitzen càlculs pesats. Aquesta tècnica guarda a la memòria cau tot el resultat anterior que es calcula de manera que no haurà de tornar a calcular per al mateix problema.
Articles relacionats:
- Memoització mitjançant decoradors en Python
- Memorització de JavaScript