Izraz Memoizacija izvira iz latinske besede memorandum ( spomniti se ), kar je v ameriški angleščini običajno skrajšano na memo in pomeni pretvorbo rezultatov funkcije v nekaj, kar si je treba zapomniti.

V računalništvu se memoizacija uporablja za pospešitev računalniških programov z odpravo ponavljajočega se izračunavanja rezultatov in z izogibanjem ponavljajočim se klicem funkcij, ki obdelujejo isti vnos.

Kaj je memoizacija

Kazalo

• Kaj je memoizacija?
• Zakaj se uporablja memoizacija>
• Kje uporabiti Memoization?
• Vrste memoizacije
• Kako se tehnika memoizacije uporablja v dinamičnem programiranju?
  • Pristop od zgoraj navzdol
  • Pristop od spodaj navzgor
• Kako se memoizacija razlikuje od tabeliranja?
• Težave pri vadbi kodiranja za memoizacijo
• pogosta vprašanja
  • 1) Je memoizacija boljša od DP?
  • 2) Je memoizacija enaka predpomnjenju?
  • 3) Zakaj je memoizacija od zgoraj navzdol?
  • 4) Ali memoizacija uporablja rekurzijo?
  • 5) Ali naj uporabim tabeliranje ali memoizacijo?
  • 6) Kje se uporablja memoizacija?
  • 7) Zakaj se temu reče memoizacija?
  • 8) Kako memoizacija zmanjša časovno kompleksnost?
  • 9) Kakšna je razlika med memoizacijo in predpomnjenjem?
  • 10) Zakaj je tabeliranje hitrejše kot memoizacija?
• Zaključek

Zakaj se uporablja memoizacija?

Memoizacija je posebna oblika predpomnjenje ki se uporablja v dinamično programiranje . Namen predpomnjenja je izboljšati delovanje naših programov in ohraniti dostopnost podatkov, ki jih je mogoče pozneje uporabiti. V bistvu shrani predhodno izračunani rezultat podproblema in shranjeni rezultat uporabi za isti podproblem. To odstrani dodaten napor za vedno znova izračunavanje iste težave. In že vemo, da če se ista težava pojavlja znova in znova, potem je ta težava ponavljajoče se narave.

Kje uporabiti Memoization?

Uporabimo lahko tehniko pomnjenja, kjer je uporabo predhodno izračunanih rezultatov pride na sliko. Ta vrsta problema se večinoma uporablja v kontekstu rekurzija , zlasti pri težavah, ki vključujejo prekrivajočih se podproblemov .

Vzemimo primer, ko se isti podproblem ponavlja znova in znova.

Primer, ki prikazuje, kje uporabiti memoizacijo:

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

Spodaj je a rekurzivna metoda za iskanje faktoriala števila:

int faktorial (nepredznačeno int n)
{
če (n == 0)
vrnitev 1;
vrni n * faktorijel (n – 1);
}

Kaj se zgodi, če uporabimo to rekurzivno metodo?

Če napišete celotno kodo za zgornji delček, boste opazili, da bosta v kodi 2 metodi:

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

Zdaj, če imamo več poizvedb za iskanje faktoriala, na primer iskanje faktoriala 2, 3, 9 in 5, bomo morali štirikrat poklicati metodo factorial():

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

Rekurzivna metoda za iskanje faktoriala

Zato lahko varno rečemo, da bo za iskanje faktoriala števil K števil potrebna časovna zapletenost O(N*K)

• O(N) najti faktorijel določenega števila in
• PUŠČICA) da pokličete metodo factorial() K različnih časov.

Kako lahko Memoizacija pomaga pri takih težavah?

Če opazimo v zgornjem problemu, medtem ko je faktorial izračuna 9:

primeri kode c#

• Računamo faktoriel 2
• Izračunavamo tudi faktoriel 3,
• in Računamo tudi faktoriel 5

Če torej ob prvem izračunu shranimo rezultat vsakega posameznega faktoriala, lahko preprosto vrnemo faktorial katerega koli zahtevanega števila v samo O(1) času. Ta postopek je znan kot Memoizacija .

Rešitev z uporabo memoizacije (Kako deluje memoizacija?):

Če najprej poiščemo faktorial števila 9 in shranimo rezultate posameznih podproblemov, lahko preprosto natisnemo faktorial vsakega vnosa v O(1).

Zato bo iskanje faktorielnih števil z memoizacijo časovno zahtevno O(N)

• O(N) da bi našli faktoriel največjega vložka
• O(1) za tiskanje faktoriala vsakega vnosa.

Vrste memoizacije

Izvedba memoizacije je odvisna od spreminjajočih se parametrov, ki so odgovorni za rešitev problema. Obstajajo različne dimenzije predpomnjenja, ki se uporabljajo v tehniki pomnjenja. Spodaj je nekaj izmed njih:

• 1D memoizacija: Rekurzivna funkcija, ki ima samo en argument, katerega vrednost ni bila konstantna po vsakem klicu funkcije.
• 2D memoizacija: Rekurzivna funkcija, ki ima samo dva argumenta, katerih vrednost ni bila konstantna po vsakem klicu funkcije.
• 3D memoizacija : Rekurzivna funkcija, ki ima samo tri argumente, katerih vrednosti niso bile konstantne po vsakem klicu funkcije.

Kako se tehnika memoizacije uporablja v dinamičnem programiranju?

Dinamično programiranje pomaga učinkovito reševati probleme, ki imajo prekrivajoče se podprobleme in optimalne lastnosti podstrukture. Ideja dinamičnega programiranja je razdeliti problem na manjše podprobleme in shraniti rezultat za prihodnjo uporabo, s čimer se odpravi potreba po ponavljajočem se izračunavanju rezultata.

Obstajata dva pristopa za oblikovanje rešitve dinamičnega programiranja:

1. Pristop od zgoraj navzdol: Ta pristop sledi memoizacija tehnika . Sestavljen je iz rekurzija in predpomnjenje . Pri računanju rekurzija predstavlja postopek ponavljajočega se klicanja funkcij, medtem ko se predpomnilnik nanaša na postopek shranjevanja vmesnih rezultatov.
2. Pristop od spodaj navzgor: Ta pristop uporablja tabeliranje tehnika za implementacijo rešitve dinamičnega programiranja. Rešuje iste težave kot prej, vendar brez rekurzije. Pri tem pristopu iteracija nadomesti rekurzijo. Zato ni napake prelivanja sklada ali dodatnih stroškov rekurzivnih postopkov.

Kako se tehnika memoizacije uporablja v dinamičnem programiranju

Kako se memoizacija razlikuje od tabeliranja?

Tabelariranje vs Memoizacija

Za več podrobnosti glejte: Tabelariranje vs. Memoizacija

Težave pri vadbi kodiranja pri memoizaciji

Pogosto zastavljena vprašanja (FAQ) o memoizaciji

1: Je memoizacija boljša od DP?

Memoizacija je pristop od zgoraj navzdol za reševanje problema z dinamičnim programiranjem. Imenuje se memoizacija, ker bomo ustvarili beležko za vrednosti, vrnjene pri reševanju vsake težave.

2: Je memoizacija enaka predpomnjenju?

Memoizacija je pravzaprav posebna vrsta predpomnjenja. Izraz predpomnjenje se na splošno lahko nanaša na katero koli tehniko shranjevanja (kot je predpomnjenje HTTP) za prihodnjo uporabo, vendar se memoizing natančneje nanaša na funkcijo predpomnjenja, ki vrne vrednost.

3: Zakaj je memoizacija od zgoraj navzdol?

Pristop od zgoraj navzdol velik problem razdeli na več podproblemov. če je podproblem že rešen, ponovno uporabite odgovor. V nasprotnem primeru rešite podproblem in shranite rezultat v pomnilnik.

4: Ali memoizacija uporablja rekurzijo?

Memoizacija sledi pristopu od zgoraj navzdol k reševanju problema. Sestavljen je iz rekurzije in predpomnjenja. Pri računanju rekurzija predstavlja postopek ponavljajočega se klicanja funkcij, medtem ko se predpomnilnik nanaša na postopek shranjevanja vmesnih rezultatov.

5: Ali naj uporabim tabeliranje ali memoizacijo?

Pri težavah, ki zahtevajo rešitev vseh podproblemov, tabeliranje običajno prekaša memoizacijo za stalni faktor. To je zato, ker tabeliranje nima dodatnih stroškov rekurzije, kar skrajša čas za razrešitev sklada klicev rekurzije iz pomnilnika sklada.
Kadarkoli je treba rešiti podproblem za rešitev prvotnega problema, je boljša memoizacija, saj se podproblem rešuje leno, tj. izvedejo se samo zahtevani izračuni.

6: Kje se uporablja memoizacija?

Memoizacija je optimizacijska tehnika, ki se uporablja za pospešitev računalniških programov s predpomnjenjem rezultatov dragih funkcijskih klicev in njihovo vrnitvijo, ko se znova naletijo na iste vnose.

7: Zakaj se temu reče memoizacija?

Izraz memoizacija izhaja iz latinske besede memorandum (zapomniti si), ki je v ameriški angleščini običajno skrajšana na memo, kar pomeni pretvoriti rezultate funkcije v nekaj, kar si je treba zapomniti.

8: Kako memoizacija zmanjša časovno kompleksnost?

Vedno znova reševanje istega problema zahteva čas in poveča kompleksnost izvajalnega časa celotnega programa. To težavo je mogoče rešiti z vzdrževanjem predpomnilnika ali pomnilnika, kamor bomo shranili že izračunan rezultat težave za določen vnos. Tako da, če ne želimo ponovno izračunati istega problema, lahko preprosto uporabimo rezultat, ki je shranjen v pomnilniku in zmanjšamo časovno zahtevnost.

9: Kakšna je razlika med memoizacijo in predpomnjenjem?

Memoizacija je pravzaprav posebna vrsta predpomnjenja, ki vključuje predpomnjenje vrnjene vrednosti funkcije na podlagi vnosa. Predpomnjenje je bolj splošen izraz. Na primer, predpomnjenje HTTP je predpomnjenje, vendar ni memoizacija.

10: Zakaj je tabeliranje hitrejše od pomnilnika?

Tabelarni prikaz je običajno hitrejši od memoizacije, ker je iterativen in reševanje podproblemov ne zahteva dodatnih stroškov rekurzivnih klicev.

Memoizacija je tehnika, ki se uporablja v računalništvu za pospešitev izvajanja rekurzivnih ali računsko dragih funkcij s predpomnjenjem rezultatov funkcijskih klicev in vračanjem predpomnjenih rezultatov, ko se isti vnosi ponovno pojavijo.

filmi 123 do

Osnovna ideja memoizacije je shraniti izhod funkcije za dani nabor vhodov in vrniti predpomnjeni rezultat, če je funkcija znova poklicana z istimi vhodi. Ta tehnika lahko prihrani čas računanja, zlasti za funkcije, ki se pogosto kličejo ali imajo visoko časovno zapletenost.

Tukaj je vodnik po korakih za izvajanje memoizacije:

Določite funkcijo, ki jo želite optimizirati z memoizacijo. Ta funkcija bi morala imeti ponavljajoče se in drage izračune za isti vnos.

Ustvarite slovarski objekt za shranjevanje predpomnjenih rezultatov funkcije. Ključi slovarja bi morali biti vhodni parametri za funkcijo, vrednosti pa bi morali biti izračunani rezultati.

Na začetku funkcije preverite, ali so vhodni parametri že prisotni v predpomnilniškem slovarju. Če so, vrni predpomnjeni rezultat.

Če vhodni parametri niso v predpomnilniškem slovarju, izračunajte rezultat in ga shranite v predpomnilniški slovar z vhodnimi parametri kot ključem.

Vrni izračunani rezultat.

Tukaj je primer kode Python za implementacijo memoizacije z uporabo slovarja:

Python3

>

>

>

V zgornji kodi definiramo funkcijo, imenovano fibonacci, ki izračuna n-to število v Fibonaccijevem zaporedju. Za shranjevanje rezultatov funkcijskih klicev uporabljamo slovarski objekt, imenovan predpomnilnik. Če je vhodni parameter n že prisoten v predpomnilniškem slovarju, vrnemo predpomnjeni rezultat. V nasprotnem primeru izračunamo rezultat z rekurzivnimi klici fibonaccijeve funkcije in ga shranimo v slovar predpomnilnika, preden ga vrnemo.

Memoizacijo je mogoče uporabiti za optimizacijo delovanja številnih funkcij, ki zahtevajo ponavljajoče in drage izračune. S predpomnilnikom rezultatov funkcijskih klicev se lahko izognemo nepotrebnim izračunom in pospešimo izvajanje funkcije.

Zaključek

Memoizacija je programski koncept in se lahko uporablja za kateri koli programski jezik. Njegov absolutni cilj je optimizacija programa. Običajno se ta težava pojavi, ko programi izvajajo težke izračune. Ta tehnika predpomni vse prejšnje rezultate, ki so izračunani, tako da jih ne bo treba ponovno izračunati za isto težavo.

Povezani članki:

• Memoizacija z dekoraterji v Pythonu
• JavaScript Memoizacija