Memoizacja (z ang. memoization) to technika z programowania komputerowego służąca do optymalizacji programu poprzez przechowywanie wyników kosztownych obliczeń i ponowne ich wykorzystanie, gdy te same dane wejściowe wystąpią ponownie. Memoizacja jest szczególnym przypadkiem buforowania, stosowanym zwykle na poziomie funkcji: zamiast zawsze ponownie wykonywać obliczenia, funkcja najpierw sprawdza, czy wynik dla danych argumentów nie został już wcześniej zapisany w strukturze pamięciowej (np. tablicy asocjacyjnej).

Działanie — mechanizm krok po kroku

  • Wywołanie funkcji: gdy funkcja jest wywoływana z określonymi argumentami, tworzy się klucz reprezentujący te argumenty.
  • Sprawdzenie pamięci podręcznej: funkcja szuka klucza w swojej tabeli lookup (cache). Jeśli wynik istnieje — jest zwracany natychmiast.
  • Obliczanie i zapis: jeśli wyniku brak, funkcja wykonuje obliczenia, zwraca wynik i jednocześnie zapisuje go w tabeli, aby przyszłe wywołania mogły użyć gotowego rezultatu.
  • Zarządzanie pamięcią: podobnie jak inne mechanizmy pamięci podręcznej, tabela może być ograniczona rozmiarem i wymagać polityki usuwania (np. LRU) — wartości rzadko używane mogą być okresowo usuwane.

Przykłady zastosowań

  • Rekurencyjne obliczenia, np. ciąg Fibonacciego — memoizacja redukuje złożoność wykładniczą do liniowej, zapisując już obliczone wartości.
  • Analiza składniowa i parsowanie — wynik parsowania fragmentu wejścia można zapamiętać, aby uniknąć powtórnych analiz.
  • Optymalizacja zapytań do baz danych lub zdalnych API — cacheowanie odpowiedzi na identyczne zapytania przyspiesza działanie aplikacji i zmniejsza obciążenie zasobów.
  • Programowanie dynamiczne — wiele problemów rozwiązywanych metodą „góra‑dół” używa memoizacji do przechowywania rozwiązań podproblemów.

Memoizacja a inne techniki buforowania

Choć związana z buforowaniem, memoizacja odnosi się do szczególnego przypadku tej optymalizacji, odróżniając ją od form buforowania, takich jak buforowanie lub wymiana stron. W kontekście niektórych języków programowania logicznego, memoizacja jest również znana jako tabling; zobacz również tabelę odnośników. Główne różnice to poziom zastosowania (funkcja vs. system/OS) oraz założenie dotyczące czystości funkcji — memoizacja najlepiej sprawdza się dla funkcji deterministycznych (bez efektów ubocznych).

Zalety

  • Znaczne przyspieszenie tam, gdzie występują powtarzalne obliczenia.
  • Prosta implementacja w wielu językach (np. dekoratory w Pythonie, wywołania z pamięcią w JavaScript, memoize w bibliotekach funkcjonalnych).
  • Możliwość adaptacji: różne polityki usuwania i limitowania pamięci, cache per-thread, itp.

Wady i ograniczenia

  • Zwiększone użycie pamięci — zapisywanie wyników może prowadzić do dużego narzutu pamięciowego.
  • Nie nadaje się do funkcji niedeterministycznych (z efektami ubocznymi, zależnych od zewnętrznego stanu).
  • Trudności w środowiskach równoległych — konieczne są mechanizmy synchronizacji, aby uniknąć warunków wyścigu.
  • Problemy z tworzeniem kluczy — argumenty muszą być reprezentowalne jako klucz (np. niektóre obiekty wymagają serializacji lub haszowania).

Wskazówki implementacyjne

  • Memoizować głównie funkcje czyste (bez efektów ubocznych), których wyniki zależą wyłącznie od argumentów.
  • Używać odpowiedniej struktury danych do kluczy: proste typy (liczby, łańcuchy) są najłatwiejsze; w przypadku bardziej złożonych obiektów rozważyć serializację lub generowanie stabilnego hasha.
  • Zastosować ograniczenia rozmiaru cache i politykę usuwania (np. LRU) w aplikacjach długotrwałych.
  • W środowiskach wielowątkowych stosować mechanizmy locków lub atomowe struktury danych, albo użyć cache per-thread, aby uniknąć kosztownych blokad.
  • Rozważyć słabe referencje (weak references) dla języków/platform, które je wspierają, aby pozwolić GC zwalniać nieużywane wpisy.

Krótki pseudokod (schemat)

cache = {} function memoized_f(args):     key = make_key(args)     if key in cache:         return cache[key]     result = f(args)     cache[key] = result     return result

Przykład w Pythonie (koncept)

from functools import lru_cache  @lru_cache(maxsize=None)  # lub ustaw maxsize, np. 128 def fib(n):     if n < 2:         return n     return fib(n-1) + fib(n-2)

Podsumowując, memoizacja to potężne, a często proste do wdrożenia narzędzie optymalizacyjne. Dobrze stosowana redukuje koszty obliczeń, ale wymaga uwagi przy zarządzaniu pamięcią oraz w kontekście funkcji niedeterministycznych lub środowisk wielowątkowych.