Czym jest memoizacja?

Memoizacja to technika optymalizacji stosowana w programowaniu w celu przyspieszenia wykonywania funkcji poprzez buforowanie wyników ich wywołań przy określonych parametrach wejściowych.

Przy kolejnym wywołaniu funkcji z tymi samymi argumentami, co wcześniej, funkcja nie oblicza wyniku od nowa, lecz zwraca zapisane (zapamiętane) wartość z pamięci podręcznej.

Jest to szczególnie skuteczne dla funkcji zasobożernych o deterministycznym zachowaniu (funkcji, które zawsze zwracają ten sam wynik dla tych samych danych wejściowych).

Zalety:

• Przyspieszenie wykonywania funkcji zasobożernych.
• Zmniejszenie obciążenia procesora poprzez unikanie powtórnych obliczeń.

Wady:

• Zwiększenie zużycia pamięci na przechowywanie pamięci podręcznej.
• Może być nieefektywne dla funkcji, które są często wywoływane z różnymi argumentami lub zmieniają swoje zachowanie.

Przykład w JavaScript:

function fibonacci(n) { // Funkcjonalna definicja liczb Fibonacciego
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Wywołanie rekurencyjne
}

// Wersja memoizowana funkcji fibonacci
function memoizedFibonacci(n, cache = {}) {
  if (n in cache) { // Sprawdzamy, czy wynik jest w pamięci podręcznej
    return cache[n];
  }

  if (n <= 1) {
    return n;
  }

  // Obliczamy i zapisujemy wynik w pamięci podręcznej
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// Porównanie szybkości wykonania:
console.time('Bez memoizacji');
fibonacci(40);
console.timeEnd('Bez memoizacji'); // Znacznie dłuższy czas

console.time('Z memoizacją');
memoizedFibonacci(40);
console.timeEnd('Z memoizacją'); // Znacznie krótszy czas

W tym przykładzie, bez memoizacji, funkcja fibonacci wielokrotnie oblicza te same wartości. Wersja memoizowana memoizedFibonacci zapisuje wyliczone wartości w obiekcie cache, znacznie przyspieszając kolejne wywołania z tymi samymi argumentami.