Ich habe gerade Python gestartet und habe keine Ahnung, was Memoisierung ist und wie man sie verwendet. Darf ich auch ein vereinfachtes Beispiel haben?
python
memoization
blur959
quelle
quelle
Antworten:
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:
Sie können komplizierter werden und den Memoisierungsprozess in einer Klasse zusammenfassen:
Dann:
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:
Die Python Decorator Library verfügt über einen ähnlichen Decorator
memoized
, der etwas robuster ist als dieMemoize
hier gezeigte Klasse.quelle
factorial_memo
, da dasfactorial
Inneredef factorial
immer noch die alte Unmemoize aufruftfactorial
.if k not in factorial_memo:
, was besser liest alsif not k in factorial_memo:
.args
ein Tupel.def some_function(*args)
macht Argumente zu einem Tupel.Neu in Python 3.2 ist
functools.lru_cache
. Standardmäßig speichert es nur die 128 zuletzt verwendeten Anrufe, aber man kann das Setmaxsize
auf ,None
um anzuzeigen , dass der Cache sollte nie ablaufen: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_cache
Anmerkungen 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.quelle
fib
Aufruf muss der Basisfall wiederholt werden, bevor eine Memoisierung durchgeführt werden kann. Ihr Verhalten ist also fast zu erwarten.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
oder als Dekorateur ausgedrückt
quelle
Beim Speichern werden die Ergebnisse teurer Berechnungen beibehalten und das zwischengespeicherte Ergebnis zurückgegeben, anstatt es kontinuierlich neu zu berechnen.
Hier ist ein Beispiel:
Eine ausführlichere Beschreibung finden Sie im Wikipedia-Eintrag zum Auswendiglernen .
quelle
if input not in self.cache
undself.cache[input]
(has_key
ist veraltet seit ... zu Beginn der 2.x-Serie, wenn nicht 2.0self.cache(index)
. War nie korrekt. IIRC)Vergessen wir nicht die eingebaute
hasattr
Funktion 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).quelle
Ich fand das äußerst nützlich
quelle
functools.wraps
.memo
damit Speicher freigegeben wird?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:
quelle
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.
quelle
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
dict
Funktion in der Funktionsdefinition können die berechneten Zwischenergebnisse zwischengespeichert werden (z. B. können bei der Berechnungfactorial(10)
nach der Berechnungfactorial(9)
alle Zwischenergebnisse wiederverwendet werden).quelle
Hier ist eine Lösung, die mit Argumenten vom Typ Liste oder Diktat funktioniert, ohne zu jammern:
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:
quelle
list
Argument von[1, 2, 3]
fälschlicherweise als dasselbe wie ein anderesset
Argument 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üsstensorted()
. Beachten Sie auch, dass ein rekursives Datenstrukturargument eine Endlosschleife verursachen würde.list
s undset
s in dasselbe "tupleisiert" werden und daher nicht mehr voneinander zu unterscheiden sind. Dersets
in 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.list
s unddict
s , weil es möglich für einelist
genau die gleichen drin zu haben , die von Aufrufen Folgemake_tuple(sorted(x.items()))
für ein Wörterbuch. Eine einfache Lösung für beide Fälle wäre, dentype()
Wert von in das erzeugte Tupel aufzunehmen. Ich kann mir einen noch einfacheren Weg vorstellen, um speziell mitset
s umzugehen , aber er verallgemeinert nicht.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 ):
Ähnliche Frage: Das Identifizieren äquivalenter Varargs-Funktionen erfordert das Speichern in Python
quelle
quelle
if n not in cache
stattdessen einfach verwenden. usingcache.keys
würde eine unnötige Liste in Python 2Die 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
.quelle