Memorizare

Memorizarea este o tehnică de programare care este de a salva în memorie valorile returnate de o funcție pentru a le avea disponibile pentru reutilizarea ulterioară fără a fi nevoie să recalculați. Memorizarea, care înseamnă literalmente „pus în memorie” este o caracteristică tehnică a programării dinamice . Adesea acest termen este confundat cu „memorare” care, deși descrie același proces, are un sens mai larg.

O funcție poate fi „memoizzata” numai dacă îndeplinește transparența referențială , adică dacă nu are efecte secundare și returnează întotdeauna aceeași valoare atunci când primește aceiași parametri ca intrarea. Operațiile care nu îndeplinesc această condiție, dar ale căror valori de returnare au o mică șansă de a se modifica, pot fi în continuare duplicate ( „cache”, franceză caché) folosind tehnici mai complexe. În general, rezultatele memorate nu își pierd valabilitatea în timp, în timp ce, dimpotrivă, cele duplicate o pierd.

În limbajele de programare funcționale puteți crea o memoize funcții de nivel memoize care, la rândul său, creează automat funcții memoizzate pentru fiecare funcție cu transparență referențială. În schimb, în limbile fără funcții de ordin superior, memoizarea trebuie implementată separat pentru fiecare funcție care trebuie să beneficieze de aceasta.

Tehnica este adesea utilizată în abordarea programării dinamice de sus în jos.

Exemplu

Un program banal pentru calcularea numerelor Fibonacci este

 fib (n) {
   dacă n este 1 sau 2, returnează 1;
   return fib (n-1) + fib (n-2);
}

Deoarece fib() este recalculat de mai multe ori pe același subiect, timpul de execuție pentru acest program este Ω ⁽ⁿ 1.6). Cu toate acestea, dacă memoizziamo (salvare), valoarea fib (n) este calculată pentru prima dată când timpul de rulare se reduce la Θ (n).

 alocați tablouri per memo, setând toate valorile la zero;
inițializează memo [1] și memo [2] la 1;

fib (n) {
   dacă nota [n] alta decât 0, returnează nota [n];
   memo [n] = fib (n-1) + fib (n-2);
   returnează nota [n];
}

Într-un limbaj cu închideri și funcții de ordin superior , memorarea oricărei funcții poate fi definită automat. Acest „memoize” construiește și returnează o altă funcție care face ca argumentul memoization f.

 memoize (f) {
  alocați tablouri per memo, setând toate valorile la nedefinit;
  construiți o nouă funcție numită "temp":
  temp (* args) {
    dacă argumentează nu în memo {
       memo [args] = f (* args)
    }
    returnează nota [args]
  }
  revenire temp
}

Notarea *args aici este intenționată ca un argument rest ca în Python sau Common Lisp . Această soluție se bazează pe revenirea o închidere pe variabila memo care acționează ca un cache pentru funcția returnat.

Această funcție „memoize” poate fi utilizată pentru a construi o versiune memoized a „fib”:

 memofib = memoize (fib)

Calculul numerelor Fibonacci se poate face încă în timp logaritmic (vezi secvența Fibonacci ); acest exemplu are ca scop ilustrarea numai a conceptului de memoizare.

Exemple de implementări

Piton

Un exemplu banal de memoizare în Python, folosind scopuri imbricate:

 memoize def (f):
    cache = {}
    def g (* args):
        args dacă nu este în cache:
            cache [args] = f (* args)
        returnează memoria cache [args]
    întoarce g

def fib (n):
    dacă n în [0, 1]: returnează n
    return fib (n - 1) + fib (n - 2)

fib = memoize (fib)

Acest memoizer banal folosește cantități tot mai mari de memorie, deoarece elementele vechi nu sunt niciodată eliminate din cache. Utilizarea memoriei poate fi îmbunătățită utilizând o schemă de evacuare a cache-ului, păstrând doar rezultatele pentru un timp pre-specificat [1] sau curățând cache-ul numai când revine la ultimul apel la f [2] .

arțar

Sistemul algebric de computer Maple are un memoizzatore construit, prin utilizarea așa-numitelor tabele amintiți-vă. De exemplu, definim o procedură „pătrată” după cum urmează:

square := proc(x) option remember; x^2; end proc:

După aceea, fiecare apel la „pătrat” face ca funcția să fie inserată în tabel pentru reutilizare ulterioară. Acest tabel poate fi extras și:

 > pătrat (4), pătrat (7); # două intrări sunt inserate în tabel
                     16, 49

> op (4, eval (pătrat)); # obțineți tabelul de amintire și conținutul acestuia
            tabel ([4 = 16, 7 = 49])

Istorie

Termenul „memoizare” (memoizare) a fost inventat de Donald Michie în articolul său „Memo functions and machine learning” (1968) din Nature .

Utilizări

Cercetare
Generarea de cod sursă , inclusiv HTML
Calcule repetitive, cum ar fi conversia imaginilor , criptarea și compresia datelor .
Recunoașterea tiparelor, cum ar fi în recunoașterea vocii
Evaluarea arborilor de vânat

Elemente conexe

linkuri externe

Memoize.pm - Un modul Perl care implementează subroutine memoizzate.
Memorizare Java - un exemplu în Java care utilizează clase proxy dinamice pentru a crea un model generic de memorare.

Notă: Acest articol conține materiale dintr-un element de domeniu public din Dicționarul de algoritmi și structuri de date NIST la http://www.nist.gov/dads/HTML/memoize.html