Memoizacja: buforowanie wyników rekurencji
Zastosują Państwo @functools.lru_cache i ręczne słowniki memo do problemów Fibonacciego i climbing-stairs, eliminując wykładnicze powtarzanie obliczeń.
Memoizacja: buforowanie wyników rekurencji to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem zbędnej rekurencji
Naiwna rekurencja dla ciągu Fibonacciego wielokrotnie oblicza te same wartości. fib(5) wywołuje fib(4) i fib(3); fib(4) wywołuje fib(3) i fib(2) — dlatego fib(3) jest obliczane dwukrotnie. Ta redundancja rośnie wykładniczo: fib(40) wykonuje ponad miliard wywołań funkcji. Zapamiętywanie wyników rozwiązuje ten problem, przechowując każdy wynik przy jego pierwszym obliczeniu, dzięki czemu kolejne wywołania pobierają go w czasie O(1), zamiast obliczać go ponownie.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40Ręczne zapamiętywanie wyników za pomocą słownika
Dodaj słownik memo jako parametr (lub użyj domknięcia). Przed wykonaniem obliczeń sprawdź, czy wynik znajduje się już w memo. Jeśli tak, natychmiast go zwróć. Jeśli nie, oblicz go, zapisz w memo i zwróć. Każdy unikatowy podproblem jest teraz obliczany dokładnie raz, co zmienia złożoność z O(2^n) na czas O(n) i pamięć O(n) na słownik memo oraz dodatkowe O(n) miejsca na stosie.
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!Dekorator functools.lru_cache
Python udostępnia @functools.lru_cache(maxsize=None) (dostępny również jako @functools.cache w Pythonie 3.9+), który automatyzuje zapamiętywanie wyników. Dodanie tego dekoratora nad funkcją powoduje buforowanie wszystkich wywołań na podstawie ich argumentów. maxsize=None oznacza nieograniczony rozmiar bufora — każda unikatowa kombinacja argumentów jest buforowana. Dzięki temu dowolna funkcja rekurencyjna staje się wersją z zapamiętywaniem wyników za pomocą jednej linii kodu.
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # 354224848179261915075
print(fib.cache_info()) # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)Wspinanie się po schodach (LeetCode 70)
LeetCode 70 „Climbing Stairs”: można pokonywać 1 lub 2 stopnie naraz. Na ile sposobów można dotrzeć do stopnia n? To w istocie ciąg Fibonacciego: ways(n) = ways(n-1) + ways(n-2). Przypadki bazowe: ways(0) = 1 (jeden sposób na pozostanie na poziomie podłogi), ways(1) = 1. Z zapamiętywaniem wyników złożoność czasowa wynosi O(n), a pamięciowa O(n).
import functools
@functools.lru_cache(maxsize=None)
def climbStairs(n):
if n <= 1:
return 1
return climbStairs(n-1) + climbStairs(n-2)
for i in range(1, 8):
print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21Wydawanie reszty (LeetCode 322)
LeetCode 322 „Coin Change”: mając dane nominały monet i kwotę docelową, znajdź minimalną liczbę monet. Rekurencja z zapamiętywaniem wyników w podejściu zstępującym: dp(amount) = 1 + min(dp(amount - coin)) dla każdej poprawnej monety. Przypadek bazowy: dp(0) = 0. Buforuj każdy podprzedział kwoty. Jeśli uzyskanie danej podkwoty jest niemożliwe, zwróć nieskończoność. Zapamiętywanie wyników zmienia wykładniczą metodę brute force na złożoność czasową O(amount × len(coins)).
import functools
def coinChange(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coinChange([1, 5, 11], 15)) # 3 (5+5+5)
print(coinChange([1, 2, 5], 11)) # 3 (5+5+1)
print(coinChange([2], 3)) # -1Word Break (LeetCode 139) z zapamiętywaniem wyników
LeetCode 139 „Word Break”: ustal, czy ciąg znaków można podzielić na słowa ze słownika. Rekurencja zstępująca: can_break(s, start) sprawdza każdy prefiks s[start:end]; jeśli znajduje się on w słowniku, a can_break(s, end) zwraca true, zwróć true. Bez zapamiętywania wyników złożoność wynosi O(2^n); z zapamiętywaniem wyników (buforowaniem każdego indeksu początkowego) spada do O(n² × L), gdzie L jest maksymalną długością słowa.
import functools
def wordBreak(s, wordDict):
word_set = set(wordDict)
@functools.lru_cache(maxsize=None)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(wordBreak('leetcode', ['leet', 'code'])) # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat'])) # FalseZapamiętywanie wyników a tabelaryzacja
Zapamiętywanie wyników (podejście zstępujące) rozpoczyna od pierwotnego problemu i buforuje odpowiedzi w miarę ich odkrywania rekurencyjnie. Rozwiązuje tylko te podproblemy, które są rzeczywiście potrzebne. Tabelaryzacja (podejście oddolne) wypełnia z góry tabelę, przechodząc od małych podproblemów do dużych, i rozwiązuje wszystkie podproblemy niezależnie od tego, czy są potrzebne. Zapamiętywanie wyników łatwiej wyprowadzić z rozwiązania rekurencyjnego, natomiast tabelaryzacja eliminuje ograniczenia głębokości rekurencji i koszt wywołań funkcji.
# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
if n <= 1: return n
return fib_td(n-1) + fib_td(n-2)
# Tabulation (bottom-up)
def fib_bu(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_td(20), fib_bu(20)) # 6765 6765
# Both O(n) time; fib_bu avoids recursion limitOptymalizacja pamięci: zmienne przesuwne
Wiele problemów programowania dynamicznego, które rekurencja z zapamiętywaniem wyników rozwiązuje przy użyciu O(n) pamięci, można dodatkowo zoptymalizować do O(1) pamięci, gdy potrzebna jest tylko stała liczba wyników poprzednich podproblemów. W przypadku ciągu Fibonacciego znaczenie mają tylko dwie ostatnie wartości. Tak samo jest przy wspinaniu się po schodach. Zastąpienie całego słownika memo lub tabeli dwiema przesuwanymi zmiennymi wystarcza do rozwiązania problemu.
# Fibonacci with O(1) space
def fib_o1(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
for i in range(8):
print(f'fib({i})={fib_o1(i)}', end=' ')
print()
# Climbing stairs O(1) space
def climbStairs_o1(n):
if n <= 1: return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(climbStairs_o1(10)) # 89lru_cache a domknięcie i globalny słownik
Istnieją trzy sposoby ręcznej implementacji zapamiętywania wyników. Globalny słownik jest prosty, ale zanieczyszcza zakres modułu. Domknięcie enkapsuluje bufor wewnątrz funkcji, zapobiegając wyciekowi stanu, ale wymaga użycia opakowania. @lru_cache jest najczystszym rozwiązaniem — jeden dekorator zastępuje cały kod pomocniczy. Podczas rozmowy kwalifikacyjnej należy zacząć od @lru_cache, chyba że osoba prowadząca rozmowę wyraźnie poprosi o implementację ręczną.
import functools
# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
if n in memo_global: return memo_global[n]
if n <= 1: return n
memo_global[n] = fib_global(n-1) + fib_global(n-2)
return memo_global[n]
# 2. Closure (cleaner scope)
def make_fib():
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fib_closure = make_fib()
# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_global(30), fib_closure(30), fib_cached(30)) # all 832040Kiedy zapamiętywanie wyników nie pomaga
Zapamiętywanie wyników przyspiesza tylko problemy z nakładającymi się podproblemami — przypadki, w których ten sam podproblem jest obliczany wielokrotnie. Jeśli każdy podproblem jest unikatowy (jak w prostym przechodzeniu drzewa, gdzie każdy węzeł jest odwiedzany dokładnie raz), zapamiętywanie wyników zwiększa narzut bez żadnej korzyści. Nie rozwiązuje również problemów, w których drzewo rekurencji jest wykładnicze względem liczby różnych podproblemów, a nie względem liczby powtórnych obliczeń — w takich przypadkach potrzebny jest zupełnie inny algorytm.
# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.
# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself
print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')Podsumowanie: lista kontrolna zapamiętywania wyników
Stosuj zapamiętywanie wyników, gdy: masz rozwiązanie rekurencyjne, które jest poprawne, ale wolne z powodu zbędnych ponownych obliczeń; funkcja ma niewielką liczbę różnych kombinacji argumentów; a wartość zwracana zależy wyłącznie od argumentów (funkcja czysta — bez efektów ubocznych i bez stanu globalnego). Sprawdź przestrzeń stanów podproblemów: jeśli istnieje co najwyżej O(n) lub O(n²) różnych stanów, zapamiętywanie wyników zmieni złożoność wykładniczą na wielomianową.
Szybki sprawdzian
Sprawdź swoje zrozumienie zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczył(a) się Pan/Pani, że: zapamiętywanie wyników przechowuje rezultaty podproblemów, aby uniknąć ponownych obliczeń, zmieniając wykładniczą rekurencję na czas wielomianowy, @functools.lru_cache to idiomatyczne narzędzie Pythona wymagające tylko jednej linii, a także że zapamiętywanie wyników (podejście zstępujące) i tabelaryzacja (podejście oddolne) to dwa style programowania dynamicznego — zapamiętywanie wyników łatwiej wyprowadzić, a tabelaryzacja pozwala uniknąć problemów z głębokością stosu. Gratulacje — ukończył(a) Pan/Pani moduły dotyczące rekurencji i map haszujących!
Często zadawane pytania
Czy lekcja „Memoizacja: buforowanie wyników rekurencji” jest bezpłatna?
Tak — pełny tekst „Memoizacja: buforowanie wyników rekurencji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Memoizacja: buforowanie wyników rekurencji”?
Zastosują Państwo @functools.lru_cache i ręczne słowniki memo do problemów Fibonacciego i climbing-stairs, eliminując wykładnicze powtarzanie obliczeń. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Memoizacja: buforowanie wyników rekurencji”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Schemat rekurencji: przypadek bazowy, zaufanie, budowa
- Wizualizacja stosu wywołań
- Kompromisy między rekurencją a iteracją
- Memoizacja: buforowanie wyników rekurencji