Termen Memoisering kommer från det latinska ordet promemoria ( att komma ihåg ), som vanligtvis förkortas till memo på amerikansk engelska, och som betyder att omvandla resultaten av en funktion till något att komma ihåg.

Inom datoranvändning används memoisering för att påskynda datorprogram genom att eliminera den upprepade beräkningen av resultat och genom att undvika upprepade anrop till funktioner som behandlar samma indata.

Vad är memoisering

Innehållsförteckning

• Vad är Memoization?
• Varför används Memoization>
• Var kan man använda Memoization?
• Typer av Memoization
• Hur används memoiseringsteknik i dynamisk programmering?
  • Uppifrån och ner tillvägagångssätt
  • Bottom Up Approach
• Hur Memoization skiljer sig från tabulering?
• Kodövningsproblem för memoisering
• Vanliga frågor
  • 1) Är memoization bättre än DP?
  • 2) Är memoisering detsamma som cachning?
  • 3) Varför memoization är uppifrån och ned?
  • 4) Använder memoisering rekursion?
  • 5) Ska jag använda tabulering eller memoisering?
  • 6) Var används memoization?
  • 7) Varför kallas det memoisering?
  • 8) Hur minskar memoisering tidskomplexiteten?
  • 9) Vad är skillnaden mellan memoisering och cachelagring?
  • 10) Varför går tabulering snabbare än memoisering?
• Slutsats

Varför används Memoization?

Memoization är en specifik form av cachelagring som används i dynamisk programmering . Syftet med cachelagring är att förbättra prestandan för våra program och hålla data tillgänglig som kan användas senare. Den lagrar i princip det tidigare beräknade resultatet av delproblemet och använder det lagrade resultatet för samma delproblem. Detta tar bort den extra ansträngningen att beräkna om och om igen för samma problem. Och vi vet redan att om samma problem uppstår om och om igen, så är det problemet rekursivt till sin natur.

Var kan man använda Memoization?

Vi kan använda memoiseringstekniken där använda de tidigare beräknade resultaten kommer in i bilden. Denna typ av problem används mest i samband med rekursion , särskilt med problem som involverar överlappande delproblem .

Låt oss ta ett exempel där samma delproblem upprepas om och om igen.

Exempel för att visa var man kan använda memoisering:

  Let us try to     find the factorial of a number    .>

Nedan är en rekursiv metod för att hitta fakulteten för ett tal:

int factorial(osignerad int n)
{
om (n == 0)
retur 1;
return n * factorial(n – 1);
}

Vad händer om vi använder denna rekursiva metod?

Om du skriver hela koden för ovanstående kodavsnitt kommer du att märka att det kommer att finnas två metoder i koden:

1. factorial(n) 2. main()>

Om vi ​​nu har flera frågor för att hitta faktorialen, som att hitta faktorial av 2, 3, 9 och 5, måste vi anropa factorial()-metoden 4 gånger:

factorial(2) factorial(3) factorial(9) factorial(5)>

Rekursiv metod för att hitta Faktoriell

Så det är säkert att säga att för att hitta faktorial av tal K-tal, kommer den tidskomplexitet som behövs att vara O(N*K)

• PÅ) för att hitta fakulteten för ett visst tal, och
• PIL) att anropa factorial()-metoden K olika gånger.

Hur Memoization kan hjälpa till med sådana problem?

Om vi ​​märker i ovanstående problem, medan beräkningsfaktorial av 9:

polymorfism

• Vi beräknar faktorn 2
• Vi beräknar också faktorn 3,
• och vi beräknar också faktorn 5

Om vi ​​därför lagrar resultatet av varje enskild faktor vid första beräkningstillfället, kan vi enkelt returnera fakulteten för alla nödvändiga tal på bara O(1) tid. Denna process är känd som Memoisering .

Lösning med Memoization (Hur fungerar Memoization?):

Om vi ​​hittar faktorn 9 först och lagrar resultaten av individuella delproblem, kan vi enkelt skriva ut factorialen för varje ingång i O(1).

Därför blir tidskomplexiteten för att hitta faktortal med hjälp av memoisering PÅ)

• PÅ) för att hitta faktorn för den största ingången
• O(1) för att skriva ut fakulteten för varje ingång.

Typer av Memoization

Implementeringen av memoisering beror på de förändrade parametrarna som är ansvariga för att lösa problemet. Det finns olika dimensioner av caching som används i memoiseringsteknik, nedan är några av dem:

• 1D Memoization: Den rekursiva funktionen som bara har ett argument vars värde inte var konstant efter varje funktionsanrop.
• 2D Memoization: Den rekursiva funktionen som bara har två argument vars värde inte var konstant efter varje funktionsanrop.
• 3D Memoization : Den rekursiva funktionen som bara har tre argument vars värden inte var konstanta efter varje funktionsanrop.

Hur Memoization-teknik används i dynamisk programmering?

Dynamisk programmering hjälper till att effektivt lösa problem som har överlappande delproblem och optimala understrukturegenskaper. Tanken bakom dynamisk programmering är att dela upp problemet i mindre delproblem och spara resultatet för framtida bruk, vilket eliminerar behovet av att beräkna resultatet upprepade gånger.

Det finns två sätt att formulera en dynamisk programmeringslösning:

1. Uppifrån och ner tillvägagångssätt: Detta tillvägagångssätt följer memoisering Metod . Den består av rekursion och cachelagring . I beräkning representerar rekursion processen att anropa funktioner upprepade gånger, medan cache hänvisar till processen att lagra mellanliggande resultat.
2. Bottom-up-metoden: Detta tillvägagångssätt använder tabulering Metod att implementera den dynamiska programmeringslösningen. Den tar upp samma problem som tidigare, men utan återfall. I detta tillvägagångssätt ersätter iteration rekursion. Följaktligen finns det inget stackspillfel eller overhead av rekursiva procedurer.

Hur Memoization-teknik används i dynamisk programmering

Hur Memoization skiljer sig från tabulering?

Tabulering vs Memoisering

För mer information, se: Tabulering vs Memoisering

Kodövningsproblem vid memoisering

Vanliga frågor (FAQs) om Memoization

1: Är memoization bättre än DP?

Memoization är uppifrån och ned-metoden för att lösa ett problem med dynamisk programmering. Det kallas memoisering eftersom vi kommer att skapa ett memo för de värden som returneras från att lösa varje problem.

2: Är memoisering detsamma som cachelagring?

Memoisering är faktiskt en specifik typ av cachelagring. Termen cachning kan i allmänhet hänvisa till vilken lagringsteknik som helst (som HTTP-cache) för framtida användning, men memoisering hänvisar mer specifikt till cachningsfunktion som returnerar värdet.

3: Varför memoization är top-down?

Top-Down-metoden delar upp det stora problemet i flera delproblem. om underproblemet redan är löst återanvänd svaret. Annars lös underproblemet och lagra resultatet i lite minne.

4: Använder memoisering rekursion?

Memoisering följer uppifrån och ned-strategi för att lösa problemet. Den består av rekursion och cachning. Vid beräkning representerar rekursion processen att anropa funktioner upprepade gånger, medan cache hänvisar till processen att lagra mellanliggande resultat.

5: Ska jag använda tabulering eller memoisering?

För problem som kräver att alla delproblem ska lösas överträffar tabulering vanligtvis memoisering med en konstant faktor. Detta beror på att tabuleringen inte har någon rekursionsoverhead, vilket minskar tiden för att lösa rekursionsanropsstacken från stackminnet.
Närhelst ett delproblem behöver lösas för att det ursprungliga problemet ska lösas är memoisering att föredra eftersom ett delproblem löses lätt, det vill säga endast de beräkningar som krävs utförs.

6: Var används memoization?

Memoization är en optimeringsteknik som används för att snabba upp datorprogram genom att cachelagra resultaten av dyra funktionsanrop och returnera dem när samma ingångar påträffas igen.

7: Varför kallas det memoisering?

Termen memoization kommer från det latinska ordet memorandum (att komma ihåg), som vanligtvis förkortas till memo på amerikansk engelska, och som betyder att förvandla resultaten av en funktion till något att komma ihåg.

8: Hur minskar memoisering tidskomplexiteten?

Att lösa samma problem om och om igen tar tid och ökar körtidens komplexitet för det övergripande programmet. Detta problem kan lösas genom att upprätthålla någon cache eller ett minne där vi kommer att lagra det redan beräknade resultatet av problemet för någon speciell ingång. Så att om vi inte vill räkna om samma problem kan vi helt enkelt använda resultatet som är lagrat i minnet och minska tidskomplexiteten.

9: Vad är skillnaden mellan memoisering och cachelagring?

Memoisering är faktiskt en specifik typ av cachelagring som involverar cachelagring av returvärdet för en funktion baserat på indata. Caching är en mer allmän term. Till exempel är HTTP-caching cachning men det är inte memoisering.

10: Varför är tabulering snabbare än memoisering?

Tabulering är vanligtvis snabbare än memoisering, eftersom det är iterativt och att lösa delproblem kräver ingen overhead av rekursiva anrop.

Memoisering är en teknik som används inom datavetenskap för att påskynda exekveringen av rekursiva eller beräkningsmässigt dyra funktioner genom att cachelagra resultaten av funktionsanrop och returnera de cachade resultaten när samma inmatningar sker igen.

Grundidén med memoisering är att lagra utdata från en funktion för en given uppsättning ingångar och returnera det cachade resultatet om funktionen anropas igen med samma ingångar. Denna teknik kan spara beräkningstid, särskilt för funktioner som anropas ofta eller har hög tidskomplexitet.

Här är en steg-för-steg-guide för att implementera memoization:

Identifiera funktionen som du vill optimera med hjälp av memoization. Denna funktion bör ha upprepade och dyra beräkningar för samma ingång.

Skapa ett ordboksobjekt för att lagra de cachade resultaten av funktionen. Nycklarna till ordboken bör vara indataparametrarna till funktionen, och värdena bör vara de beräknade resultaten.

I början av funktionen, kontrollera om ingångsparametrarna redan finns i cacheordlistan. Om de är det, returnera det cachade resultatet.

Om inmatningsparametrarna inte finns i cacheordlistan, beräkna resultatet och lagra det i cachelexikonet med indataparametrarna som nyckel.

Returnera det beräknade resultatet.

Här är ett Python-kodexempel på att implementera memoization med hjälp av en ordbok:

Python3

>

python är numeriskt

>

>

I ovanstående kod definierar vi en funktion som heter fibonacci som beräknar det n:e talet i Fibonacci-sekvensen. Vi använder ett ordboksobjekt som heter cache för att lagra resultaten av funktionsanropen. Om ingångsparametern n redan finns i cacheordlistan returnerar vi det cachade resultatet. Annars beräknar vi resultatet med hjälp av rekursiva anrop till fibonacci-funktionen och lagrar det i cache-lexikonet innan vi returnerar det.

Memoization kan användas för att optimera prestandan för många funktioner som har upprepade och dyra beräkningar. Genom att cachelagra resultaten av funktionsanrop kan vi undvika onödiga beräkningar och påskynda exekveringen av funktionen.

Slutsats

Memoization är ett programmeringskoncept och kan appliceras på alla programmeringsspråk. Dess absoluta mål är att optimera programmet. Vanligtvis ses detta problem när program utför tunga beräkningar. Den här tekniken cachelagrar alla tidigare resultat som beräknas så att det inte behöver räknas om för samma problem.

Relaterade artiklar:

• Memoisering med dekoratörer i Python
• JavaScript Memoization