Was ist Memoisierung und wie kann ich sie in Python verwenden?

Question

Ich habe gerade mit Python angefangen und habe keine Ahnung, was Memoisierung ist und wie man es verwendet. Kann ich auch ein vereinfachtes Beispiel haben?

Answer 1

Nicht zu vergessen sind die eingebauten hasattr Funktion, für diejenigen, die handwerklich arbeiten wollen. Auf diese Weise können Sie den Zwischenspeicher innerhalb der Funktionsdefinition halten (im Gegensatz zu einer globalen).

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]

Answer 2

Memoisierung ist die Umwandlung von Funktionen in Datenstrukturen. Normalerweise möchte man, dass die Umwandlung inkrementell und träge erfolgt (auf Anforderung eines bestimmten Domänenelements - oder "Schlüssels"). In faulen funktionalen Sprachen kann diese faule Konvertierung automatisch erfolgen, und somit kann Memoisierung ohne (explizite) Seiteneffekte implementiert werden.

Answer 3

Memoisierung bedeutet im Grunde, dass die Ergebnisse früherer Operationen, die mit rekursiven Algorithmen durchgeführt wurden, gespeichert werden, um die Notwendigkeit zu verringern, den Rekursionsbaum zu durchlaufen, wenn die gleiche Berechnung zu einem späteren Zeitpunkt erforderlich ist.

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

Beispiel für die Fibonacci-Memoisierung in Python:

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]

Answer 4

Nun, ich sollte den ersten Teil zuerst beantworten: Was ist Memoisierung?

Das ist nur eine Methode, um Erinnerung gegen Zeit zu tauschen. Denken Sie an Multiplikationstabelle .

Die Verwendung eines veränderlichen Objekts als Standardwert in Python wird normalerweise als schlecht angesehen. Aber wenn man es mit Bedacht einsetzt, kann es tatsächlich nützlich sein, ein memoization .

Hier ist ein Beispiel aus http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Mit einer veränderbaren dict in der Funktionsdefinition können die berechneten Zwischenergebnisse zwischengespeichert werden (z. B. bei der Berechnung von factorial(10) nach Berechnung factorial(9) können wir alle Zwischenergebnisse wiederverwenden)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]

Answer 5

Hier ist eine Lösung, die mit Argumenten vom Typ Liste oder Diktat funktioniert, ohne zu jammern:

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

Beachten Sie, dass dieser Ansatz natürlich auf jedes beliebige Objekt ausgeweitet werden kann, indem Sie Ihre eigene Hash-Funktion als Spezialfall in handle_item implementieren. Um diesen Ansatz zum Beispiel für eine Funktion zu verwenden, die ein Set als Eingangsargument nimmt, könnten Sie zu handle_item hinzufügen:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))