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

378

Ich habe gerade Python gestartet und habe keine Ahnung, was Memoisierung ist und wie man sie verwendet. Darf ich auch ein vereinfachtes Beispiel haben?

blur959
quelle
215
Wenn der zweite Satz des relevanten Wikipedia-Artikels den Ausdruck "gegenseitig rekursives Abstiegsparsing [1] in einem allgemeinen Top-Down-Parsing-Algorithmus [2] [3] enthält, der Mehrdeutigkeit und Linksrekursion in Polynomzeit und -raum berücksichtigt", denke ich Es ist völlig angebracht, SO zu fragen, was los ist.
Ahnungslos
10
@ Clueless: Vor diesem Satz steht "Memoization wurde auch in anderen Kontexten (und für andere Zwecke als Geschwindigkeitsgewinne) verwendet, z. B. in". Es ist also nur eine Liste von Beispielen (und muss nicht verstanden werden); Es ist nicht Teil der Erklärung der Memoisierung.
ShreevatsaR
1
@StefanGruenwald Dieser Link ist tot. Kannst du bitte ein Update finden?
JS.
2
Neuer Link zur PDF-Datei, da pycogsci.info nicht verfügbar ist: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf
Stefan Gruenwald
4
@ Clueless, Der Artikel sagt tatsächlich " einfache gegenseitig rekursive Abstiegsanalyse [1] in einem allgemeinen Top-Down-Analyse-Algorithmus [2] [3], der Mehrdeutigkeit und Linksrekursion in Polynomzeit und -raum berücksichtigt ". Du hast das Einfache verpasst , was das Beispiel offensichtlich viel klarer macht :).
Studgeek

Antworten:

353

Memoisierung bezieht sich effektiv auf das Erinnern ("Memoisieren" → "Memorandum" → Erinnern) an Ergebnisse von Methodenaufrufen basierend auf den Methodeneingaben und das anschließende Zurückgeben des gespeicherten Ergebnisses, anstatt das Ergebnis erneut zu berechnen. Sie können sich das als Cache für Methodenergebnisse vorstellen. Weitere Einzelheiten finden Sie auf Seite 387 für die Definition in Einführung in Algorithmen (3e), Cormen et al.

Ein einfaches Beispiel für die Berechnung von Fakultäten mithilfe der Memoisierung in Python wäre etwa das Folgende:

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]

Sie können komplizierter werden und den Memoisierungsprozess in einer Klasse zusammenfassen:

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]

Dann:

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

factorial = Memoize(factorial)

In Python 2.4 wurde eine als " Dekorateure " bekannte Funktion hinzugefügt, mit der Sie jetzt einfach Folgendes schreiben können, um dasselbe zu erreichen:

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

Die Python Decorator Library verfügt über einen ähnlichen Decorator memoized, der etwas robuster ist als die Memoizehier gezeigte Klasse.

Jason
quelle
2
Danke für diesen Vorschlag. Die Memoize-Klasse ist eine elegante Lösung, die ohne großen Umbau problemlos auf vorhandenen Code angewendet werden kann.
Kapitän Lepton
10
Die Memoize-Klassenlösung ist fehlerhaft und funktioniert nicht wie die factorial_memo, da das factorialInnere def factorialimmer noch die alte Unmemoize aufruft factorial.
Adamsmith
9
Übrigens kann man auch schreiben if k not in factorial_memo:, was besser liest als if not k in factorial_memo:.
ShreevatsaR
5
Sollte das wirklich als Dekorateur tun.
Emlyn O'Regan
3
@ durden2.0 Ich weiß, dass dies ein alter Kommentar ist, aber argsein Tupel. def some_function(*args)macht Argumente zu einem Tupel.
Adam Smith
232

Neu in Python 3.2 ist functools.lru_cache. Standardmäßig speichert es nur die 128 zuletzt verwendeten Anrufe, aber man kann das Set maxsizeauf , Noneum anzuzeigen , dass der Cache sollte nie ablaufen:

import functools

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

Diese Funktion ist an sich sehr langsam. Versuchen fib(36)Sie es und Sie müssen ungefähr zehn Sekunden warten.

Durch Hinzufügen von lru_cacheAnmerkungen wird sichergestellt, dass die Funktion, wenn sie kürzlich für einen bestimmten Wert aufgerufen wurde, diesen Wert nicht neu berechnet, sondern ein zwischengespeichertes vorheriges Ergebnis verwendet. In diesem Fall führt dies zu einer enormen Geschwindigkeitsverbesserung, während der Code nicht mit den Details des Cachings überfüllt ist.

Flimm
quelle
2
Versuchte fib (1000), bekam RecursionError: maximale Rekursionstiefe im Vergleich überschritten
X Æ A-12
5
@Andyk Das Standard-Py3-Rekursionslimit beträgt 1000. Beim ersten fibAufruf muss der Basisfall wiederholt werden, bevor eine Memoisierung durchgeführt werden kann. Ihr Verhalten ist also fast zu erwarten.
Quelklef
1
Wenn ich mich nicht irre, wird es nur zwischengespeichert, bis der Prozess nicht beendet ist, oder? Oder wird es zwischengespeichert, unabhängig davon, ob der Prozess abgebrochen wurde? Angenommen, ich starte mein System neu. Werden die zwischengespeicherten Ergebnisse weiterhin zwischengespeichert?
Kristada673
1
@ Kristada673 Ja, es ist im Speicher des Prozesses gespeichert, nicht auf der Festplatte.
Flimm
2
Beachten Sie, dass dies sogar den ersten Durchlauf der Funktion beschleunigt, da es sich um eine rekursive Funktion handelt und eigene Zwischenergebnisse zwischengespeichert werden. Könnte gut sein, um eine nicht rekursive Funktion zu veranschaulichen, die von Natur aus nur langsam ist, um Dummies wie mir klarer zu machen. : D
Endolith
61

Die anderen Antworten decken ab, was es ganz gut ist. Ich wiederhole das nicht. Nur einige Punkte, die für Sie nützlich sein könnten.

Normalerweise ist das Auswendiglernen eine Operation, die Sie auf jede Funktion anwenden können, die etwas (teures) berechnet und einen Wert zurückgibt. Aus diesem Grund wird es oft als Dekorateur implementiert . Die Implementierung ist unkompliziert und es wäre ungefähr so

memoised_function = memoise(actual_function)

oder als Dekorateur ausgedrückt

@memoise
def actual_function(arg1, arg2):
   #body
Noufal Ibrahim
quelle
18

Beim Speichern werden die Ergebnisse teurer Berechnungen beibehalten und das zwischengespeicherte Ergebnis zurückgegeben, anstatt es kontinuierlich neu zu berechnen.

Hier ist ein Beispiel:

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

Eine ausführlichere Beschreibung finden Sie im Wikipedia-Eintrag zum Auswendiglernen .

Bryan Oakley
quelle
Hmm, wenn das nun richtig wäre, würde Python rocken, aber es scheint nicht ... okay zu sein, also ist "Cache" kein Diktat? Denn wenn es so ist, sollte es sein if input not in self.cache und self.cache[input] ( has_keyist veraltet seit ... zu Beginn der 2.x-Serie, wenn nicht 2.0 self.cache(index). War nie korrekt. IIRC)
Jürgen A. Erhard
15

Vergessen wir nicht die eingebaute hasattrFunktion für diejenigen, die handwerklich arbeiten möchten. Auf diese Weise können Sie den Mem-Cache innerhalb der Funktionsdefinition behalten (im Gegensatz zu einem 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]
Karel Kubat
quelle
Dies scheint eine sehr teure Idee zu sein. Für jedes n werden nicht nur die Ergebnisse für n zwischengespeichert, sondern auch für 2 ... n-1.
Codeforester
15

Ich fand das äußerst nützlich

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
quelle
Unter docs.python.org/3/library/functools.html#functools.wraps finden Sie Informationen zur Verwendung functools.wraps.
Anishpatel
1
Muss ich das manuell löschen, memodamit Speicher freigegeben wird?
Nr.
Die ganze Idee ist, dass die Ergebnisse innerhalb einer Sitzung in einem Memo gespeichert werden. Dh nichts wird geklärt wie es ist
mr.bjerre
6

Durch das Auswendiglernen werden im Wesentlichen die Ergebnisse früherer Operationen gespeichert, die mit rekursiven Algorithmen ausgeführt wurden, um die Notwendigkeit zu verringern, den Rekursionsbaum zu durchlaufen, wenn dieselbe Berechnung zu einem späteren Zeitpunkt erforderlich ist.

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

Beispiel für eine 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]
Romaine Carter
quelle
2
Um die Leistung Ihres Fibcaches mit den ersten bekannten Werten vorab zu steigern, können Sie die zusätzliche Logik für die Behandlung aus dem "Hot Path" des Codes entfernen.
Fliegen
5

Memoization ist die Umwandlung von Funktionen in Datenstrukturen. Normalerweise möchte man, dass die Konvertierung schrittweise und träge erfolgt (auf Anfrage eines bestimmten Domänenelements - oder "Schlüssels"). In faulen Funktionssprachen kann diese verzögerte Konvertierung automatisch erfolgen, und somit kann die Memoisierung ohne (explizite) Nebenwirkungen implementiert werden.

Conal
quelle
5

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

Es ist nur eine Methode, um Speicher gegen Zeit zu tauschen. Denken Sie an die Multiplikationstabelle .

Die Verwendung eines veränderlichen Objekts als Standardwert in Python wird normalerweise als schlecht angesehen. Aber wenn Sie es mit Bedacht einsetzen, kann es tatsächlich nützlich sein, a zu implementieren memoization.

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

Unter Verwendung einer veränderlichen dictFunktion in der Funktionsdefinition können die berechneten Zwischenergebnisse zwischengespeichert werden (z. B. können bei der Berechnung factorial(10)nach der Berechnung factorial(9)alle Zwischenergebnisse wiederverwendet werden).

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

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 Objekt erweitert werden kann, indem Sie Ihre eigene Hash-Funktion als Sonderfall in handle_item implementieren. Damit dieser Ansatz beispielsweise für eine Funktion funktioniert, die eine Menge als Eingabeargument verwendet, können Sie handle_item Folgendes hinzufügen:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
RussellStewart
quelle
1
Netter Versuch. Ohne zu jammern, kann ein listArgument von [1, 2, 3]fälschlicherweise als dasselbe wie ein anderes setArgument mit einem Wert von angesehen werden {1, 2, 3}. Außerdem sind Mengen wie Wörterbücher ungeordnet, so dass sie es auch sein müssten sorted(). Beachten Sie auch, dass ein rekursives Datenstrukturargument eine Endlosschleife verursachen würde.
Martineau
Ja, Sets sollten durch ein spezielles Gehäuse handle_item (x) und Sortieren behandelt werden. Ich hätte nicht sagen sollen, dass diese Implementierung Mengen behandelt, weil dies nicht der Fall ist - aber der Punkt ist, dass sie leicht durch ein spezielles Gehäuse handle_item erweitert werden kann und dasselbe für jede Klasse oder jedes iterierbare Objekt funktioniert, solange Sie sind bereit, die Hash-Funktion selbst zu schreiben. Der knifflige Teil - der Umgang mit mehrdimensionalen Listen oder Wörterbüchern - wird hier bereits behandelt. Daher habe ich festgestellt, dass diese Memoize-Funktion als Basis viel einfacher zu bearbeiten ist als die einfachen Typen "Ich nehme nur hashbare Argumente".
RussellStewart
Das Problem, das ich erwähnt habe, ist auf die Tatsache zurückzuführen, dass lists und sets in dasselbe "tupleisiert" werden und daher nicht mehr voneinander zu unterscheiden sind. Der setsin Ihrem neuesten Update beschriebene Beispielcode zum Hinzufügen von Unterstützung vermeidet dies leider nicht. Dies kann leicht gesehen werden, indem Sie eine Testfunktion "meroize" d separat übergeben [1,2,3]und {1,2,3}als Argument dafür verwenden, ob sie zweimal aufgerufen wird, wie es sein sollte oder nicht.
Martineau
Ja, ich habe dieses Problem gelesen, aber ich habe es nicht angesprochen, weil ich denke, dass es viel kleiner ist als das andere, das Sie erwähnt haben. Wann haben Sie das letzte Mal eine gespeicherte Funktion geschrieben, bei der ein festes Argument entweder eine Liste oder eine Menge sein kann und die beiden zu unterschiedlichen Ausgaben führten? Wenn Sie auf einen so seltenen Fall stoßen würden, würden Sie handle_item einfach neu schreiben, um es voranzustellen. Sagen Sie eine 0, wenn das Element eine Menge ist, oder eine 1, wenn es eine Liste ist.
RussellStewart
Eigentlich ist es ein ähnliches Problem mit lists und dicts , weil es möglich für eine listgenau die gleichen drin zu haben , die von Aufrufen Folge make_tuple(sorted(x.items()))für ein Wörterbuch. Eine einfache Lösung für beide Fälle wäre, den type()Wert von in das erzeugte Tupel aufzunehmen. Ich kann mir einen noch einfacheren Weg vorstellen, um speziell mit sets umzugehen , aber er verallgemeinert nicht.
Martineau
3

Lösung, die sowohl mit Positions- als auch mit Schlüsselwortargumenten funktioniert, unabhängig von der Reihenfolge, in der die Schlüsselwortargumente übergeben wurden (mithilfe von 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

Ähnliche Frage: Das Identifizieren äquivalenter Varargs-Funktionen erfordert das Speichern in Python

ndpu
quelle
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
quelle
4
Sie könnten if n not in cachestattdessen einfach verwenden. using cache.keyswürde eine unnötige Liste in Python 2
erstellen
2

Die Python Decorator-Bibliothek wollte nur die bereits bereitgestellten Antworten ergänzen und verfügt über einige einfache, aber nützliche Implementierungen, die im Gegensatz zu "nicht verwischbaren Typen" auch "nicht verwischbare Typen" speichern können functools.lru_cache.

Sid
quelle
1
Dieser Dekorateur merkt sich keine "nicht zerlegbaren Typen" ! Es geht nur darum, die Funktion ohne Memoisierung aufzurufen. Gegen das Explizite zu verstoßen ist besser als implizit Dogma.
Ostrokach