Memoization (zapamiętywanie wyników)

1. Czym jest memoization?

Memoization to technika optymalizacji polegająca na zapamiętywaniu wyników funkcji, aby uniknąć ponownych obliczeń dla tych samych argumentów.

1.1. Nazwa:

"Memoization" pochodzi od łacińskiego "memorandum" (do zapamiętania)
NIE "memorization"!

1.2. Zasada działania:

---

2. Implementacja ręczna - słownik

2.1. Fibonacci z cache:

Złożoność: - Czasowa: O(n) ✅ (każde fib(i) obliczane tylko raz) - Pamięciowa: O(n) – cache + stos rekurencji

---

3. Python @lru_cache decorator

3.1. Wbudowane narzędzie:

Zalety @lru_cache: - ✅ Automatyczne cachowanie - ✅ Thread-safe - ✅ Statystyki (hits, misses) - ✅ Czyszczenie cache (cache_clear())

3.2. LRU (Least Recently Used):

---

4. Przykład: Schody z różnymi krokami

4.1. Problem:

Wchodzisz po schodach o n stopniach.
Możesz wejść o 1, 2 lub 3 stopnie na raz.
Ile jest sposobów dotarcia na szczyt?

4.2. Rekurencja naiwna:

4.3. Z memoization:

---

5. Problem: Minimalna liczba monet (Coin Change)

5.1. Rekurencja z memoization:

5.2. Z @lru_cache:

---

6. Wizualizacja cache

6.1. Debug version:

Wynik:

fib(5) → obliczam...
  fib(4) → obliczam...
    fib(3) → obliczam...
      fib(2) → obliczam...
        fib(1) = 1 (bazowy)
        fib(0) = 0 (bazowy)
      fib(2) = 1
      fib(1) → cache: 1
    fib(3) = 2
    fib(2) → cache: 1
  fib(4) = 3
  fib(3) → cache: 2
fib(5) = 5

---

7. Memoization dla funkcji z wieloma argumentami

7.1. Problem: Kombinacje z powtórzeniami:

7.2. Levenshtein distance (edit distance):

---

8. Benchmark: Rekurencja vs Memoization

---

9. Kiedy NIE używać memoization?

❌ Problem 1: Funkcje niedeterministyczne

❌ Problem 2: Funkcje z efektami ubocznymi

❌ Problem 3: Duże obiekty mutowalne

---

10. Czyszczenie cache

10.1. cache_clear():

10.2. Statystyki cache:

---

11. Własny decorator memoization

11.1. Prosty decorator:

11.2. Z funkcjonalnościami:

---

12. Podsumowanie

Memoization:

• Zapamiętywanie wyników funkcji
• Top-Down – rekurencja z cache
• Automatyczne – @lru_cache w Pythonie
• Transparentne – nie zmienia logiki funkcji

Zalety:

✅ Dramatyczne przyspieszenie (nawet 100,000x) ✅ Prosta implementacja (1 linia z @lru_cache) ✅ Zachowuje naturalną rekurencję ✅ Automatyczne cachowanie

Wady:

❌ O(n) pamięci dla cache ❌ O(n) pamięci dla stosu rekurencji ❌ Tylko dla funkcji "czystych" (pure functions) ❌ Problemy z mutowalnymi argumentami

Implementacje:

Złożoność:

Problem	Naiwna rekurencja	Memoization
Fibonacci	O(2^n) ❌	O(n) ✅
Schody	O(3^n) ❌	O(n) ✅
Coin Change	O(2^n) ❌	O(n×m) ✅

Kiedy używać:

✅ Funkcje "czyste" (bez efektów ubocznych) ✅ Drogie obliczenia ✅ Powtarzające się wywołania ✅ Naturalna rekurencja

Kiedy NIE używać:

❌ Funkcje niedeterministyczne (random) ❌ Efekty uboczne (I/O, modyfikacje) ❌ Mutowalne argumenty (listy) ❌ Pamięć jest krytyczna

@lru_cache parametry:

Statystyki:

Co dalej warto poznać:

• Tabulation – bottom-up DP (bez rekurencji)
• Space optimization – redukcja pamięci
• DP patterns – typowe wzorce problemów
• Advanced caching – Redis, Memcached
• Persistent memoization – cache na dysku