Există câteva articole excelente care vorbesc despre tehnica de optimizare numită memoizare. Le puteți accesa aici și aici. Ceea ce vom face noi va fi să vă oferim o scurtă prezentare generală a ceea ce este memoizarea. Vom merge puțin mai departe, realizând o analiză pas cu pas a ceea ce face de fapt codul „memoizing”-ul, linie cu linie. Până la sfârșitul articolului, veți înțelege pe deplin memoizarea.

Memoizarea este practica programatică de a face ca funcțiile recursive/iterative lungi să ruleze mult mai repede.

Cum, vă întrebați? Prin stocarea în cache a valorilor pe care funcția le returnează după execuția sa inițială.

Când introducem aceeași valoare în funcția noastră memoizată, aceasta returnează valoarea stocată în cache în loc să ruleze din nou funcția, sporind astfel performanța. Programul dumneavoastră nu mai trebuie să recalculeze fiecare număr pentru a obține un rezultat.

Sună minunat, nu-i așa? Ei bine, ceea ce este și mai bine este că nu este greu de înțeles ce face o funcție memoize odată ce descompuneți codul.

Iată un exemplu de funcție memo de bază:

Să începem cu începutul…

Întoarcem ceea ce se numește o închidere anonimă. Închiderea noastră anonimă este capabilă să moștenească orice variabilă sau, în acest caz, funcție trecută în memo. Putem apoi să ne jucăm cu obiectul de argumente pe care îl oferă funcția noastră transmisă.

Nota laterală: Deci, dacă fiecare funcție are un obiect de argumente, de ce nu moștenim obiectul de argumente din memo? Acest lucru se datorează faptului că, de regulă, închiderile nu moștenesc obiectul argumente al unei funcții exterioare. Folosim această regulă în avantajul nostru pentru a ne juca cu funcția pe care dorim să o memoizăm.

Să deslușim ce anume face memoizarea analizând un exemplu foarte simplu și nepractic. Apropo, ar trebui să copiați/lipiți acest cod, sau orice alt cod de altfel, pentru a vă face cu adevărat o idee despre cum funcționează.

Cred că am înțeles esența acestui exemplu de cod. Practic, acesta vorbește de la sine. Haideți să îl dezvoltăm puțin mai mult, uitându-ne la un instantaneu al unei funcții memo reale:

Acum că am descompus ceea ce face o funcție memo, haideți să creăm o expresie de funcție și să trecem o funcție Fibonacci recursivă în memo și să vedem ce se întâmplă.

//Now we'll test our code!
// =======TEST=======
fib(10)//On the first try we need to load//=> loading…//=> loading…//=> loading…//=> loading…//=> loading…//=> 4 loadings later we get...//=> 89// And on the second try…fib(10)//=> 89//No loading! Yaay!//The cool thing about memoizing the recursive Fibonacci algorithm is that once we make a call for the value of the nth number in the series, we are able to store all the previous numbers in the series.//So if we try...
fib(7) //=> 21
//We don't have to recalculate anything.//And if we want to try fib(11)...
fib(11)
//loading...
//=> 144
//Our memoized recursive function already cached fib(1-10),so all it needed to do was to calculate the cached values. // This is what the cache now looks like:
/*
{ '{"0":0}': 1,
'{"0":1}': 1,
'{"0":2}': 2,
'{"0":3}': 3,
'{"0":4}': 5,
'{"0":5}': 8,
'{"0":6}': 13,
'{"0":7}': 21,
'{"0":8}': 34,
'{"0":9}': 55,
'{"0":10}': 89,
'{"0":11}': 144}
*/

Concluzie

Memoizarea devine demistificată atunci când o reduceți la perechi cheie-valoare. Tot ceea ce facem este să creăm un obiect, să verificăm dacă există valori care se potrivesc cu cele introduse de utilizator și să stocăm noi perechi cheie-valoare dacă acestea nu există în obiectul nostru.

Desigur, stocarea tuturor acestor date înseamnă că vom consuma memorie. Cel mai bine este să implementăm memoizarea pe funcții care sunt pure și care implică calcule grele, repetitive.

Bonus:

Doar pentru distracție, iată o versiune funcțională a memoizerului nostru: