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

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?

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.

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.

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

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 .

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]

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)

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]

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.

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]

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)))

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

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]

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.