Istnieje kilka doskonałych artykułów, które mówią o technice optymalizacji zwanej memoization. Możesz uzyskać do nich dostęp tutaj i tutaj. To, co zamierzamy zrobić, to dać ci krótki przegląd tego, czym jest memoizacja. Pójdziemy nieco dalej, analizując krok po kroku, co tak naprawdę robi „memoizing” w kodzie, linia po linii. Pod koniec artykułu, będziesz w pełni rozumiał memoization.

Memoization jest programistyczną praktyką, dzięki której długie rekurencyjne/iteracyjne funkcje działają znacznie szybciej.

Jak, pytasz? Poprzez buforowanie wartości, które funkcja zwraca po swoim pierwszym wykonaniu.

Kiedy wprowadzimy tę samą wartość do naszej funkcji memoized, zwraca ona wartość przechowywaną w pamięci podręcznej zamiast uruchamiać funkcję ponownie, zwiększając w ten sposób wydajność. Twój program nie musi już przeliczać każdej liczby, aby uzyskać wynik.

Brzmi świetnie, prawda? Cóż, co jest jeszcze lepsze, to fakt, że nie jest trudno zrozumieć, co robi funkcja memoize, gdy rozbije się kod.

Oto przykład podstawowej funkcji memo:

Zacznijmy od początku…

Zwracamy to, co nazywa się anonimowym zamknięciem. Nasze anonimowe zamknięcie jest w stanie odziedziczyć dowolną zmienną lub, w tym przypadku, funkcję przekazaną do memo. Możemy wtedy bawić się obiektem argumentów, który dostarcza nasza przekazana funkcja.

Uwaga dodatkowa: Skoro więc każda funkcja ma obiekt argumentów, to dlaczego nie dziedziczymy obiektu argumentów z memo? Dzieje się tak dlatego, że z reguły funkcje zamykające nie dziedziczą obiektu argumentów funkcji zewnętrznej. Wykorzystamy tę regułę na naszą korzyść, aby pobawić się funkcją, którą chcemy memoizować.

Przeanalizujmy dokładnie, co robi memoizacja, przyglądając się bardzo prostemu i niepraktycznemu przykładowi. Przy okazji, powinieneś skopiować/wkleić ten kod, lub jakikolwiek inny kod, aby naprawdę poczuć jak to działa.

Myślę, że rozumiemy sedno tego przykładu kodu. Praktycznie mówi on sam za siebie. Rozszerzmy go trochę bardziej, patrząc na migawkę prawdziwej funkcji memo:

Teraz, gdy już zrozumieliśmy, co robi funkcja memo, stwórzmy wyrażenie funkcyjne i przekażmy rekurencyjną funkcję Fibonacciego do memo i zobaczmy, co się stanie.

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

Wniosek

Memoizacja staje się zdemistyfikowana, gdy sprowadzimy ją do par klucz-wartość. Wszystko, co robimy, to tworzenie obiektu, sprawdzanie istniejących wartości, które pasują do danych wprowadzonych przez użytkownika, i przechowywanie nowych par klucz-wartość, jeśli nie ma ich w naszym obiekcie.

Oczywiście, przechowywanie wszystkich tych danych oznacza, że będziemy zużywać pamięć. Najlepiej jest zaimplementować memoizację na funkcjach, które są czyste i wymagają ciężkich, powtarzających się obliczeń.

Bonus:

Dla zabawy, oto funkcjonalna wersja naszego memoizera: