Co to jest memoizacja i jak mogę jej używać w Pythonie?

378

Właśnie uruchomiłem Python i nie mam pojęcia, co to jest memoization i jak go używać. Czy mogę też podać uproszczony przykład?

blur959
źródło
215
Gdy drugie zdanie odpowiedniego artykułu na Wikipedii zawiera frazę „parsowanie wzajemnie rekurencyjne [1] w ogólnym algorytmie parsowania z góry na dół [2] [3], który uwzględnia dwuznaczność i pozostawił rekurencję w wielomianowym czasie i przestrzeni,„ myślę, że całkowicie słuszne jest zapytanie SO, co się dzieje.
Clueless
10
@Clueless: Ta fraza poprzedza „Memoization został również użyty w innych kontekstach (i do celów innych niż przyrost prędkości), takich jak in”. Jest to więc tylko lista przykładów (i nie trzeba ich rozumieć); nie jest to część wyjaśnienia zapamiętywania.
ShreevatsaR
1
@StefanGruenwald Ten link jest martwy. Czy możesz znaleźć aktualizację?
JS.
2
Nowy link do pliku pdf, ponieważ pycogsci.info nie działa: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf
Stefan Gruenwald
4
@Cluless, artykuł faktycznie mówi „ proste wzajemnie rekurencyjne parsowanie zejścia [1] w ogólnym algorytmie parsowania z góry na dół [2] [3], który uwzględnia dwuznaczność i lewą rekurencję w wielomianowym czasie i przestrzeni”. Pominąłeś proste , co oczywiście czyni ten przykład znacznie jaśniejszym :).
studgeek

Odpowiedzi:

353

Zapamiętywanie efektywnie odnosi się do zapamiętywania („zapamiętywanie” → „memorandum” → do zapamiętania) wyników wywołań metod opartych na danych wejściowych metody, a następnie zwracania zapamiętanego wyniku zamiast ponownego obliczania wyniku. Można to traktować jako pamięć podręczną wyników metod. W celu uzyskania dalszych informacji, patrz strona 387, definicja w Wprowadzenie do algorytmów (3e), Cormen i in.

Prostym przykładem obliczania silni przy użyciu zapamiętywania w Pythonie byłoby coś takiego:

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

Możesz się bardziej skomplikować i zamknąć proces zapamiętywania w klasie:

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

Następnie:

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

factorial = Memoize(factorial)

W Pythonie 2.4 dodano funkcję znaną jako „ dekoratory ”, która pozwala teraz po prostu napisać następujące rzeczy, aby osiągnąć to samo:

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

Python Decorator Library ma podobny dekorator nazwie memoized, który jest nieco bardziej wytrzymałe niż Memoizeklasy przedstawionej tutaj.

Jason
źródło
2
Dziękuję za tę sugestię. Klasa Memoize to eleganckie rozwiązanie, które można z łatwością zastosować do istniejącego kodu bez konieczności przeprowadzania dużego refaktoryzacji.
Kapitan Lepton
10
Rozwiązanie klasy Memoize jest błędne, nie będzie działać tak samo jak factorial_memo, ponieważ factorialwnętrze def factorialnadal wywołuje stary unememize factorial.
adamsmith,
9
Nawiasem mówiąc, możesz również pisać if k not in factorial_memo:, który czyta lepiej niż if not k in factorial_memo:.
ShreevatsaR
5
Naprawdę powinien to zrobić jako dekorator.
Emlyn O'Regan
3
@ durden2.0 Wiem, że to stary komentarz, ale argsjest krotką. def some_function(*args)robi krotkę args.
Adam Smith
232

Nowością w Python 3.2 jest functools.lru_cache. Domyślnie tylko buforuje 128 ostatnio używany nazywa, ale można ustawić maxsize, aby Nonewskazać, że skrzynka nie powinny wygasa:

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Ta funkcja sama w sobie jest bardzo powolna, spróbuj fib(36)i będziesz musiał poczekać około dziesięciu sekund.

Dodanie lru_cacheadnotacji gwarantuje, że jeśli funkcja została ostatnio wywołana dla określonej wartości, nie przeliczy tej wartości, ale użyje poprzedniego wyniku w pamięci podręcznej. W takim przypadku prowadzi to do ogromnej poprawy prędkości, a kod nie jest zaśmiecony szczegółami buforowania.

Flimm
źródło
2
Próbowałem Fib (1000), otrzymałem błąd rekursji: maksymalna głębokość rekurencji została przekroczona w porównaniu
X Æ A-12
5
@Andyk Domyślny limit rekurencji Py3 wynosi 1000. Przy pierwszym fibwywołaniu trzeba będzie odwołać się do przypadku podstawowego, zanim będzie możliwe zapamiętanie. Twoje zachowanie jest więc prawie oczekiwane.
Quelklef
1
Jeśli się nie mylę, buforuje tylko do momentu, gdy proces nie zostanie zabity, prawda? A może buforuje bez względu na to, czy proces zostanie zabity? Powiedzmy, że ponownie uruchamiam system - czy wyniki w pamięci podręcznej nadal będą buforowane?
Kristada673,
1
@ Kristada673 Tak, jest przechowywany w pamięci procesu, a nie na dysku.
Flimm
2
Zauważ, że przyspiesza to nawet pierwsze uruchomienie funkcji, ponieważ jest to funkcja rekurencyjna i buforuje własne wyniki pośrednie. Może warto zilustrować nierekurencyjną funkcję, która jest z natury powolna, aby była bardziej zrozumiała dla manekinów takich jak ja. : D
endolith
61

Pozostałe odpowiedzi dotyczą tego, co jest całkiem nieźle. Nie powtarzam tego. Tylko kilka punktów, które mogą Ci się przydać.

Zazwyczaj zapamiętywanie jest operacją, którą można zastosować do dowolnej funkcji, która oblicza coś (kosztownie) i zwraca wartość. Z tego powodu często jest wdrażany jako dekorator . Wdrożenie jest proste i byłoby coś takiego

memoised_function = memoise(actual_function)

lub wyrażone jako dekorator

@memoise
def actual_function(arg1, arg2):
   #body
Noufal Ibrahim
źródło
18

Memoizacja zachowuje wyniki kosztownych obliczeń i zwraca wynik z pamięci podręcznej, a nie stale go przelicza.

Oto przykład:

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

Pełniejszy opis można znaleźć we wpisie w Wikipedii dotyczącym zapamiętywania .

Bryan Oakley
źródło
Hmm, teraz, gdyby to był poprawny Python, to by zadziałało, ale wydaje się, że nie jest ... w porządku, więc "pamięć podręczna" to nie dykt? Bo jeśli tak, to powinno być if input not in self.cache i self.cache[input] ( has_keyjest przestarzałe, ponieważ ... na początku serii 2.x, jeśli nie 2.0. self.cache(index)Nigdy nie było poprawne. IIRC)
Jürgen A. Erhard
15

Nie zapomnijmy o wbudowanej hasattrfunkcji dla tych, którzy chcą ręcznie wytwarzać. W ten sposób możesz przechowywać pamięć podręczną wewnątrz definicji funkcji (w przeciwieństwie do globalnej).

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]
Karel Kubat
źródło
To wydaje się bardzo kosztownym pomysłem. Dla każdego n nie tylko buforuje wyniki dla n, ale także dla 2 ... n-1.
codeforester
15

Uważam to za bardzo przydatne

def memoize(function):
    from functools import wraps

    memo = {}

    @wraps(function)
    def wrapper(*args):
        if args in memo:
            return memo[args]
        else:
            rv = function(*args)
            memo[args] = rv
            return rv
    return wrapper


@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(25)
mr.bjerre
źródło
Zobacz docs.python.org/3/library/functools.html#functools.wraps, aby dowiedzieć się, dlaczego należy tego używać functools.wraps.
anishpatel
1
Czy muszę ręcznie wyczyścić memopamięć, aby zwolnić pamięć?
nos
Cały pomysł polega na tym, że wyniki są przechowywane w notatce w ramach sesji. Tj. Nic nie jest usuwane w
obecnej formie
6

Zapamiętywanie polega zasadniczo na zapisywaniu wyników poprzednich operacji wykonanych algorytmami rekurencyjnymi w celu zmniejszenia potrzeby przechodzenia przez drzewo rekurencyjne, jeśli takie samo obliczenie jest wymagane na późniejszym etapie.

patrz http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Przykład zapamiętywania Fibonacciego w Pythonie:

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]
Romaine Carter
źródło
2
Aby zwiększyć wydajność, należy wstępnie zaszczepić swój fibcache za pomocą kilku pierwszych znanych wartości, a następnie można wziąć dodatkową logikę do obsługi ich poza „gorącą ścieżką” kodu.
jkflying
5

Zapamiętywanie to konwersja funkcji na struktury danych. Zazwyczaj chce się, aby konwersja następowała stopniowo i leniwie (na żądanie danego elementu domeny - lub „klucza”). W leniwych językach funkcjonalnych ta leniwa konwersja może odbywać się automatycznie, a zatem zapamiętywanie może być realizowane bez (wyraźnych) skutków ubocznych.

Conal
źródło
5

Cóż, najpierw powinienem odpowiedzieć na pierwszą część: czym jest zapamiętywanie?

To tylko metoda wymiany pamięci na czas. Pomyśl o tabliczce mnożenia .

Użycie zmiennego obiektu jako wartości domyślnej w Pythonie jest zwykle uważane za złe. Ale jeśli użyjesz go mądrze, może być użyteczne wdrożenie memoization.

Oto przykład zaadaptowany z http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Używając zmiennej dictw definicji funkcji, wyniki pośrednie obliczone mogą być buforowane (np. Podczas obliczania factorial(10)po obliczeniu factorial(9)możemy ponownie wykorzystać wszystkie wyniki pośrednie)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]
czatować
źródło
4

Oto rozwiązanie, które będzie działać z argumentami typu list lub dict bez marudzenia:

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

Zauważ, że to podejście można oczywiście rozszerzyć na dowolny obiekt, implementując własną funkcję skrótu jako specjalny przypadek w handle_item. Na przykład, aby to podejście działało dla funkcji, która przyjmuje zestaw jako argument wejściowy, możesz dodać do handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
RussellStewart
źródło
1
Niezła próba. Bez marudzenia listargument [1, 2, 3]można błędnie uznać za taki sam jak inny setargument o wartości {1, 2, 3}. Ponadto zestawy są nieuporządkowane jak słowniki, więc i tak powinny być sorted(). Zauważ również, że argument rekurencyjnej struktury danych spowodowałby nieskończoną pętlę.
martineau,
Tak, zestawy powinny być obsługiwane przez specjalną obudowę handle_item (x) i sortowanie. Nie powinienem powiedzieć, że ta implementacja obsługuje zestawy, ponieważ tak nie jest - chodzi o to, że można to łatwo rozszerzyć o specjalną obudowę handle_item, i to samo będzie działać dla dowolnej klasy lub obiektu iterowalnego, o ile jesteś gotów sam napisać funkcję skrótu. Trudna część - zajmowanie się wielowymiarowymi listami lub słownikami - została już tutaj omówiona, więc odkryłem, że ta funkcja zapamiętywania jest o wiele łatwiejsza w obsłudze jako podstawa niż proste typy „biorę tylko argumenty haszowalne”.
RussellStewart
Problem, o którym wspomniałem, wynika z faktu, że listsi setsą „zmontowane” w to samo i dlatego stają się nierozróżnialne. Przykładowy kod dodawania obsługi setsopisanego w najnowszej aktualizacji nie pozwala uniknąć tego. Można to łatwo zauważyć, osobno przekazując [1,2,3]i {1,2,3}jako argument funkcji testowej „zapamiętaj” i sprawdzając, czy jest wywoływana dwukrotnie, tak jak powinna, czy nie.
martineau
tak, przeczytałem ten problem, ale nie rozwiązałem go, ponieważ uważam, że jest on znacznie mniejszy niż ten, o którym wspominałeś. Kiedy ostatnio pisałeś zapamiętaną funkcję, w której ustalony argument może być listą lub zestawem, a te dwa dają różne wyniki? Jeśli miałbyś spotkać się z tak rzadkim przypadkiem, ponownie napisałbyś po prostu handle_item, aby wstawić, powiedzieć 0, jeśli element jest zbiorem, lub 1, jeśli jest listą.
RussellStewart
W rzeczywistości istnieje podobny problem z listsi i dicts, ponieważ możliwe jest, listaby mieć dokładnie to samo, co wynikało z wywołania make_tuple(sorted(x.items()))słownika. Prostym rozwiązaniem dla obu przypadków byłoby uwzględnienie type()wartości w wygenerowanej krotce. Mogę wymyślić jeszcze prostszy sposób obsługi sets, ale nie uogólnia.
martineau
3

Rozwiązanie, które działa zarówno z argumentami pozycyjnymi, jak i słowami kluczowymi niezależnie od kolejności przekazywania argumentów słów kluczowych (przy użyciu inspect.getargspec ):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

Podobne pytanie: Identyfikacja równoważnych wywołań funkcji varargs do zapamiętywania w Pythonie

ndpu
źródło
2
cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
Vikrant Singh
źródło
4
if n not in cachezamiast tego możesz użyć po prostu . użycie cache.keysspowoduje zbudowanie niepotrzebnej listy w Pythonie 2
n611x007,
2

Chciałem tylko dodać do już podanych odpowiedzi, biblioteka dekoratorów Pythona ma kilka prostych, ale przydatnych implementacji, które mogą zapamiętywać „typy niewymagalne”, w przeciwieństwie do functools.lru_cache.

Sid
źródło
1
Ten dekorator nie zapamiętuje „niewymownych typów” ! Po prostu wraca do wywoływania funkcji bez zapamiętywania, przeciwstawianie się temu, co jawne, jest lepsze niż dogmat ukryty .
ostrokach