Cache jest tym efektywniejszy im szybsza jest pamięć, w której składujemy buforowane w jego ramach dane. Buforowaliśmy już dane w systemie plików, następnie w bazie danych, w pamięci RAM (memcached), w chmurze (ElastiCache zbudowany za pomocą memcached). Co nam jeszcze zostało? Pamięć cache procesora 🙂

Memoizacja (ang. memoization lub memoisation) to technika optymalizacji kodu polegająca na zapamiętywaniu zwróconych wartości dla konkretnych argumentów i konkretnej funkcji (lub metody). Jest to działający na poziomie kodu aplikacji mechanizm, który pozwala zaoszczędzić moc obliczeniową w przypadku wielokrotnego wykonywania tych samych i stosunkowo kosztownych funkcji.

Terminu memoization pierwszy raz użył Donald Michie w 1968 roku w artykule dotyczącym funkcji i uczenia maszynowego. Oczywiście nie jest on autorem metody, bo to tak jakby przypisać mu wymyślenie mechanizmu cache. Według mnie pionierem był człowiek, który pierwszy raz poszedł do studni z wiadrem a nie po to by się tylko napić.

Tego typu sytuacje mamy często w uczeniu maszynowym co powinno tym bardziej zachęcić do zapoznania się z tą uniwersalną techniką optymalizacji kodu. Dlaczego uniwersalną? Bo choć pokażę algorytm na przykładzie PHP, mechanizm ten zadziała w każdym funkcyjnym języku programowania.

Prosty przypadek użycia memoizacji

Załóżmy, że mamy funkcję, która zużywa wiele zasobów procesora. Dla celów badawczych, załóżmy, że takim działaniem jest sumowanie liczb:

<?php
 function heavy($a, $b, $c){
     return $a+$b+$c;
 }
 echo heavy(1,2,3);

W memoizacji chodzi o to, aby „zapisać sobie”, że wynikiem działania funkcji heavy dla argumentów 1,2,3 jest liczba 6.

Stwórzmy sobie zatem tablicę do zapamiętywania takich operacji.

$memo = [];

Jakby ktoś pytał, dlaczego używam w przykładach PHP, to właśnie dlatego (oszczędzam 90% czasu z powodu inteligentnie zwięzłej składni) 😉

Sprytna osoba wytknie błąd, że lepiej przechowywać wyniki w tablicy haszującej, bo przy dużej liczbie elementów będzie występować strata czasu na szukanie konkretnego klucza – oczywiście, że tak – ale złożoność wyszukiwania elementów w tablicy zostawimy sobie na inny artykuł.

Zamiast od razu wywoływać funkcję heavy() odpytamy najpierw tę tablicę $memo czy tak czasem nie wie, jaki jest wynik tej „kosztownej” operacji. Jeżeli tam jej nie będzie, to potem wywołamy sobie tę funkcję heavy(). Aby utrzymać czytelność kodu stworzymy funkcję, która to odpytywanie zrobi za nas.

function _memo_func($f, $a="", $b="", $c=""){
   global $memo;
   $key = $f.$a1.$a2.$a3;

   if(isset($memo[$key])){
         return "Wynik leci z memo: ".$memo[$key];
     }
     else{
         return "Wywołuję funkcję: ".call_user_func($f, $a1, $a2, $a3);
     }
}

Dodaliśmy podłogę do nazwy funkcji aby nie przysłonić nazwy ewentualnie już istniejącej nazwy funkcji – wszak jesteśmy hakerami od optymalizacji a nie od klepania programików i czytania dokumentacji.

W naszej funkcji heavy() musimy zapisywać raz wykonane operacje:

function heavy($a, $b, $c){
     global $memo;
     $result = $a+$b+$c;
     $memo["heavy".$a.$b.$c] = $result;
     return $result;
 }

Wywołujemy

echo _memo_func("heavy", 2,3,4)."<br>";
echo _memo_func("heavy", 2,3,4);

Rezultat

Jak widać, pięknie oszukaliśmy system:


Zalety memoizacji

  • Radykalne skrócenie czasu wykonywania się operacji, w których jest szansa kilkakrotnego wywołania funkcji z tymi samymi argumentami,
  • odciąża inne mechanizmy Cache,
  • odciążenie innych zasobów np. łącza, bazy danych (w przypadku wykorzystania w integracjach zewnętrznych),
  • brak konieczności wdrażania dodatkowych pamięci podręcznych,
  • wszechstronność – można w ten sposób buforować odpowiedzi zewnętrznych usług, zasoby plikowe, itp.,
  • odciąża CPU i minimalizuje wykorzystanie najcenniejszych zasobów i koszty związane z utrzymaniem maszyny/serwera/klienta.
  • Możemy w prosty sposób analizować wykorzystanie mechanizmu i poznać coś w rodzaju Cache-Hit-Ratio.

Wady memoizacji

  • Zapełnia pamięć RAM,
  • dodatkowe skomplikowanie kodu,
  • konieczność rozwiązania wielu dodatkowych problemów (np. złożoność wyszukiwania elementów w tablicy, obsługa wyjątków itp.).
  • nie nadaje się do wszystkich problemów.n
  • niektóre kompilatory/interpretery a nawet procesory mogą implementować tego typu mechanizmy automatycznie dla prostych operacji.

Kiedy stosować memoizację?

  • Wąskim gardłem jest CPU,
  • Mamy dużo RAMu,
  • Aplikacja spowalnia usługa zewnętrzna lub zasób (np. dyskowy) do której wysyłamy powtarzające się zapytania.

Podsumowanie

Memoizacja to uniwersalny sposób na radykalne przyspieszenie działania aplikacji. Im kosztowniejsze funkcje tym zysk ze stosowania tego mechanizmu jest bardziej spektakularny.

Źródła

https://en.wikipedia.org/wiki/Memoization

https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf

Oceń artykuł na temat: Memoizacja – uniwersalna optymalizacja kodu (PHP)
Średnia : 4.7 , Maksymalnie : 5 , Głosów : 10