Existuje několik vynikajících článků, které pojednávají o optimalizační technice zvané memoizace. Přístup k nim máte zde a zde. My vám nyní poskytneme stručný přehled o tom, co memoizace je. Půjdeme trochu dál a provedeme rozbor toho, co „memoizace“ kódu vlastně dělá, řádek po řádku. Na konci článku budete memoizaci plně rozumět.

Memoizace je programátorská praxe, která umožňuje, aby dlouhé rekurzivní/iterativní funkce běžely mnohem rychleji.

Ptáte se jak? Pomocí ukládání hodnot, které funkce vrací po svém prvním provedení, do mezipaměti.

Když do naší memoizované funkce zadáme stejnou hodnotu, vrátí nám hodnotu uloženou v mezipaměti, místo aby se funkce spouštěla znovu, čímž se zvýší její výkon. Program už nemusí přepočítávat každé číslo, aby získal výsledek.

Zní to úžasně, že? No, ještě lepší je, že není těžké pochopit, co funkce memoize dělá, jakmile kód rozeberete.

Tady je příklad základní memofunkce:

Začněme od začátku…

Vracíme to, čemu se říká anonymní uzávěr. Náš anonymní uzávěr je schopen zdědit jakoukoli proměnnou nebo v tomto případě funkci předanou do memo. Můžeme si pak hrát s objektem argumentů, který nám předaná funkce poskytuje.

Poznámka na okraj: Pokud má tedy každá funkce objekt argumentů, proč nedědíme objekt argumentů funkce memo? Je to proto, že uzávěry zpravidla nedědí objekt argumentů vnější funkce. Toto pravidlo využijeme ve svůj prospěch, abychom si mohli pohrát s funkcí, kterou chceme memoizovat.

Podívejme se na velmi jednoduchý a nepraktický příklad a rozeberme si, co přesně memoizace dělá. Mimochodem, tento kód, nebo vlastně jakýkoli jiný kód, byste měli zkopírovat/vložit, abyste si opravdu uvědomili, jak to funguje.

Myslím, že jsme pochopili podstatu tohoto příkladu. Prakticky mluví sám za sebe. Pojďme si to ještě trochu upřesnit tím, že se podíváme na snímek skutečné funkce memo:

Teď, když jsme si rozebrali, co dělá funkce memo, vytvořme funkční výraz a do memo předejme rekurzivní Fibonacciho funkci a uvidíme, co se stane.

//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}
*/

Závěr

Paměťové funkce se stanou demystifikovanými, když je omezíte na dvojice klíč-hodnota. Vše, co děláme, je vytvoření objektu, kontrola existujících hodnot, které odpovídají vstupu uživatele, a uložení nových dvojic klíč-hodnota, pokud v našem objektu neexistují.

Uložení všech těchto dat samozřejmě znamená, že budeme spotřebovávat paměť. Nejlepší je implementovat memoizaci u funkcí, které jsou čisté a zahrnují těžké, opakující se výpočty.

Bonus:

Jen pro zajímavost, zde je funkční verze našeho memoizeru:

.