Begrepet Memoisering kommer fra det latinske ordet notat ( å huske ), som ofte forkortes til memo på amerikansk engelsk, og som betyr å transformere resultatene av en funksjon til noe å huske.

I databehandling brukes memoisering for å øke hastigheten på dataprogrammer ved å eliminere repeterende beregning av resultater, og ved å unngå gjentatte anrop til funksjoner som behandler samme input.

Hva er memoarisering

Innholdsfortegnelse

• Hva er Memoization?
• Hvorfor brukes Memoization>
• Hvor skal jeg bruke Memoization?
• Typer memoisering
• Hvordan Memoization Technique brukes i dynamisk programmering?
  • Top Down-tilnærming
  • Bottom Up-tilnærming
• Hvordan Memoization er forskjellig fra tabulering?
• Kodepraksisproblemer for Memoization
• Vanlige spørsmål
  • 1) Er memoisering bedre enn DP?
  • 2) Er memoisering det samme som caching?
  • 3) Hvorfor huskes det ovenfra og ned?
  • 4) Bruker memoisering rekursjon?
  • 5) Bør jeg bruke tabulering eller memoisering?
  • 6) Hvor brukes memoarisering?
  • 7) Hvorfor kalles det memoisering?
  • 8) Hvordan reduserer memoisering tidskompleksiteten?
  • 9) Hva er forskjellen mellom memoisering og caching?
  • 10) Hvorfor tabulering er raskere enn memoisering?
• Konklusjon

Hvorfor brukes Memoization?

Memoisering er en bestemt form for caching som brukes i dynamisk programmering . Hensikten med caching er å forbedre ytelsen til programmene våre og holde data tilgjengelig som kan brukes senere. Den lagrer i utgangspunktet det tidligere beregnede resultatet av delproblemet og bruker det lagrede resultatet for samme delproblem. Dette fjerner den ekstra innsatsen for å beregne igjen og igjen for det samme problemet. Og vi vet allerede at hvis det samme problemet oppstår igjen og igjen, så er det problemet rekursivt.

Hvor skal jeg bruke Memoization?

Vi kan bruke memoiseringsteknikken der bruk av tidligere beregnede resultater kommer inn i bildet. Denne typen problem brukes mest i sammenheng med rekursjon , spesielt med problemer som involverer overlappende delproblemer .

La oss ta et eksempel der det samme underproblemet gjentar seg igjen og igjen.

Eksempel for å vise hvor du skal bruke memoarisering:

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

Nedenfor er en rekursiv metode for å finne faktoren til et tall:

int factorial(usignert int n)
{
hvis (n == 0)
retur 1;
returner n * faktorial(n – 1);
}

Hva skjer hvis vi bruker denne rekursive metoden?

Hvis du skriver hele koden for kodebiten ovenfor, vil du legge merke til at det vil være to metoder i koden:

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

Hvis vi har flere spørringer for å finne faktoren, for eksempel å finne faktoren 2, 3, 9 og 5, må vi kalle faktorial()-metoden 4 ganger:

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

Rekursiv metode for å finne Faktoriell

Så det er trygt å si at for å finne faktorial av tall K-tall, vil tidskompleksiteten som trengs være O(N*K)

• PÅ) for å finne faktoren til et bestemt tall, og
• PIL) å kalle faktorial()-metoden K forskjellige tider.

Hvordan Memoization kan hjelpe med slike problemer?

Hvis vi legger merke til problemet ovenfor, mens beregningsfaktoren på 9:

vba

• Vi beregner faktoren til 2
• Vi beregner også faktoren til 3,
• og vi beregner også faktoren på 5

Derfor, hvis vi lagrer resultatet av hver enkelt faktor ved første beregningstidspunkt, kan vi enkelt returnere faktoren til et hvilket som helst nødvendig tall på bare O(1) tid. Denne prosessen er kjent som Memoisering .

Løsning ved hjelp av Memoization (Hvordan fungerer Memoization?):

Hvis vi finner faktoren til 9 først og lagrer resultatene av individuelle delproblemer, kan vi enkelt skrive ut faktoren til hver inngang i O(1).

Derfor vil tidskompleksiteten for å finne faktortall ved bruk av memoisering være PÅ)

• PÅ) for å finne faktoren til den største inngangen
• O(1) for å skrive ut faktoren for hver inngang.

Typer memoisering

Implementeringen av memoisering avhenger av de endrede parameterne som er ansvarlige for å løse problemet. Det er forskjellige dimensjoner av caching som brukes i memoiseringsteknikk, nedenfor er noen av dem:

• 1D Memoisering: Den rekursive funksjonen som bare har ett argument hvis verdi ikke var konstant etter hvert funksjonskall.
• 2D Memoization: Den rekursive funksjonen som bare har to argumenter hvis verdi ikke var konstant etter hvert funksjonskall.
• 3D Memoization : Den rekursive funksjonen som bare har tre argumenter hvis verdier ikke var konstante etter hvert funksjonskall.

Hvordan Memoization-teknikk brukes i dynamisk programmering?

Dynamisk programmering bidrar til å effektivt løse problemer som har overlappende delproblemer og optimale understrukturegenskaper. Ideen bak dynamisk programmering er å dele opp problemet i mindre delproblemer og lagre resultatet for fremtidig bruk, og dermed eliminere behovet for å beregne resultatet gjentatte ganger.

Det er to tilnærminger for å formulere en dynamisk programmeringsløsning:

1. Top-down-tilnærming: Denne tilnærmingen følger memoisering teknikk . Det består av rekursjon og caching . Ved beregning representerer rekursjon prosessen med å kalle opp funksjoner gjentatte ganger, mens cache refererer til prosessen med å lagre mellomresultater.
2. Bottom-up-tilnærming: Denne tilnærmingen bruker tabulering teknikk å implementere den dynamiske programmeringsløsningen. Den tar opp de samme problemene som før, men uten rekursjon. I denne tilnærmingen erstatter iterasjon rekursjon. Derfor er det ingen stabeloverløpsfeil eller overhead av rekursive prosedyrer.

Hvordan Memoization-teknikk brukes i dynamisk programmering

Hvordan Memoization er forskjellig fra tabulering?

Tabulering vs Memoisering

For mer informasjon vennligst se: Tabulering vs. Memoisering

Problemer med kodingspraksis på Memoization

Vanlige spørsmål (FAQs) om Memoization

1: Er memoisering bedre enn DP?

Memoisering er ovenfra-ned-tilnærmingen for å løse et problem med dynamisk programmering. Det kalles memoisering fordi vi vil lage et notat for verdiene som returneres fra å løse hvert problem.

2: Er memoisering det samme som caching?

Memoisering er faktisk en bestemt type caching. Begrepet caching kan generelt referere til enhver lagringsteknikk (som HTTP-caching) for fremtidig bruk, men memoizing refererer mer spesifikt til caching-funksjon som returnerer verdien.

3: Hvorfor huskes det ovenfra og ned?

Top-Down-tilnærmingen deler det store problemet inn i flere delproblemer. hvis underproblemet allerede er løst, bruk svaret på nytt. Ellers løser du underproblemet og lagrer resultatet i noe minne.

4: Bruker memoisering rekursjon?

Memoisering følger top-down tilnærming for å løse problemet. Den består av rekursjon og caching. Ved beregning representerer rekursjon prosessen med å kalle opp funksjoner gjentatte ganger, mens cache refererer til prosessen med å lagre mellomresultater.

5: Bør jeg bruke tabulering eller memoisering?

For problemer som krever at alle delproblemer skal løses, overgår tabulering vanligvis memoisering med en konstant faktor. Dette er fordi tabuleringen ikke har noen overhead av rekursjon som reduserer tiden for å løse rekursjonsanropsstakken fra stabelminnet.
Når et delproblem må løses for at det opprinnelige problemet skal løses, er memoisering å foretrekke siden et delproblem løses dovent, det vil si at bare beregningene som kreves, utføres.

6: Hvor brukes memoarisering?

Memoisering er en optimaliseringsteknikk som brukes til å øke hastigheten på dataprogrammer ved å bufre resultatene av dyre funksjonskall og returnere dem når de samme inngangene oppstår igjen.

7: Hvorfor kalles det memoisering?

Begrepet memoization kommer fra det latinske ordet memorandum (å huske), som ofte forkortes til memo på amerikansk engelsk, og som betyr å transformere resultatene av en funksjon til noe å huske.

8: Hvordan reduserer memoisering tidskompleksiteten?

Å løse det samme problemet igjen og igjen tar tid og øker kjøretidskompleksiteten til det generelle programmet. Dette problemet kan løses ved å opprettholde en cache eller et minne hvor vi vil lagre det allerede beregnede resultatet av problemet for en bestemt inngang. Slik at hvis vi ikke ønsker å beregne det samme problemet på nytt, kan vi ganske enkelt bruke resultatet som er lagret i minnet og redusere tidskompleksiteten.

9: Hva er forskjellen mellom memoisering og caching?

Memoisering er faktisk en spesifikk type caching som involverer caching av returverdien til en funksjon basert på input. Caching er et mer generelt begrep. For eksempel er HTTP-bufring caching, men det er ikke huskelagring.

10: Hvorfor tabulering er raskere enn memoisering?

Tabulering er vanligvis raskere enn memoisering, fordi den er iterativ og å løse delproblemer krever ingen overhead av rekursive anrop.

Memoisering er en teknikk som brukes i informatikk for å fremskynde utførelsen av rekursive eller beregningsmessig dyre funksjoner ved å bufre resultatene av funksjonskall og returnere de hurtigbufrede resultatene når de samme inngangene skjer igjen.

Den grunnleggende ideen med memoisering er å lagre utdata fra en funksjon for et gitt sett med innganger og returnere det hurtigbufrede resultatet hvis funksjonen kalles opp igjen med de samme inngangene. Denne teknikken kan spare utregningstid, spesielt for funksjoner som kalles ofte eller har høy tidskompleksitet.

Her er en trinn-for-trinn-guide for implementering av memoization:

Identifiser funksjonen du ønsker å optimalisere ved hjelp av memoization. Denne funksjonen skal ha gjentatte og dyre beregninger for samme inngang.

Lag et ordbokobjekt for å lagre de bufrede resultatene av funksjonen. Nøklene til ordboken skal være inngangsparametrene til funksjonen, og verdiene skal være de beregnede resultatene.

I begynnelsen av funksjonen, sjekk om inngangsparametrene allerede er til stede i hurtigbufferordboken. Hvis de er det, returner det bufrede resultatet.

Hvis inngangsparametrene ikke er i hurtigbufferordboken, beregne resultatet og lagre det i hurtigbufferordboken med inndataparameterne som nøkkel.

Returner det beregnede resultatet.

Her er et Python-kodeeksempel på implementering av memoisering ved hjelp av en ordbok:

Python3

>

>

>

I koden ovenfor definerer vi en funksjon kalt fibonacci som beregner det n-te tallet i Fibonacci-sekvensen. Vi bruker et ordbokobjekt kalt cache for å lagre resultatene av funksjonskallene. Hvis inngangsparameteren n allerede er til stede i hurtigbufferordboken, returnerer vi det bufrede resultatet. Ellers beregner vi resultatet ved å bruke rekursive kall til fibonacci-funksjonen og lagrer det i cache-ordboken før vi returnerer det.

Memoisering kan brukes til å optimalisere ytelsen til mange funksjoner som har gjentatte og dyre beregninger. Ved å bufre resultatene av funksjonskall kan vi unngå unødvendige beregninger og fremskynde utførelsen av funksjonen.

Konklusjon

Memoisering er et programmeringskonsept og kan brukes på alle programmeringsspråk. Dets absolutte mål er å optimalisere programmet. Vanligvis ses dette problemet når programmer utfører tunge beregninger. Denne teknikken cacher alle de tidligere resultatene som er beregnet, slik at de ikke trenger å beregne på nytt for det samme problemet.

Relaterte artikler:

• Memoisering ved hjelp av dekoratører i Python
• JavaScript Memoization