Odpowiedź.

Historia pytania:

Memoizacja to technika optymalizacji, szeroko stosowana w programowaniu funkcyjnym, obliczeniach rekurencyjnych i programowaniu dynamicznym, kiedy te same funkcje są wywoływane wielokrotnie z tymi samymi argumentami. W Pythonie zyskała popularność dzięki dekoratorowi functools.lru_cache oraz wzorcom buforowania wyników obliczeń.

Problem:

Bez buforowania funkcje rekurencyjne, takie jak obliczanie liczb Fibonacciego, działają bardzo wolno: dla każdego argumentu obliczenia są powtarzane wiele razy, co prowadzi do wykładniczego wzrostu liczby wywołań.

Rozwiązanie:

Memoizacja zapisuje już obliczone wartości (na przykład w słowniku), aby ponownie je wykorzystać w razie potrzeby:

Przykład ręcznej implementacji:

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib(n-1) + fib(n-2)
    memo[n] = result
    return result

Od Pythona 3.2 można po prostu użyć dekoratora:

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Kluczowe cechy:

Pozwala przyspieszyć funkcje rekurencyjne lub obliczeniowo kosztowne bez zmiany ich logiki.
Implementacja może być ręczna (za pomocą słownika) lub automatyczna (przez lru_cache).
Należy uważać na zmienne argumenty, ponieważ lru_cache działa tylko z argumentami haszowalnymi (niemutowalnymi).

Pytania z haczykiem.

Czy można memoizować funkcję z zmiennymi argumentami (np. listami)?

Nie, lru_cache wymaga, aby wszystkie argumenty były haszowalne (niemutowalne), w przeciwnym razie wystąpi TypeError.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: unhashable type: 'list'

Czy memoizowane wartości są automatycznie usuwane?

Tak, jeśli ustawiony jest maxsize — wartości przekraczające limit są usuwane (Least Recently Used). Nieskończony bufor (maxsize=None) może prowadzić do przepełnienia pamięci.

Co się stanie, jeśli memoizowana funkcja wywoła samą siebie z nowymi argumentami?

Memoizacja nadal zadziała — dla każdego unikalnego zestawu argumentów wynik obliczany jest tylko raz i jest buforowany.

Typowe błędy i antywzorce

Używanie memoizacji bez ograniczenia bufora i przepełnienia pamięci.
Próba memoizacji funkcji z zmiennymi argumentami.
Zapominanie o czyszczeniu bufora, gdy nie jest już potrzebny.

Przykład z życia

Negatywny przypadek

Pisanie własnego bufora bez ograniczenia rozmiaru:

cache = {}
def foo(x):
    if x not in cache:
        cache[x] = long_heavy_computation(x)
    return cache[x]

po pewnym czasie program wykorzystuje gigabajty pamięci.

Zalety:

Szybko działa dla powtarzających się wywołań.

Wady:

Nieograniczony wzrost pamięci.
Możliwe Out of Memory.

Pozytywny przypadek

Użycie lru_cache z maxsize:

from functools import lru_cache

@lru_cache(maxsize=1000)
def foo(x):
    return long_heavy_computation(x)