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

Memoisierung bedeutet, dass die Ergebnisse von Methodenaufrufen auf der Grundlage der Methodeneingaben gespeichert werden ("Memoisierung", "Memorandum") und dann das gespeicherte Ergebnis zurückgegeben wird, anstatt das Ergebnis erneut zu berechnen. Man kann es sich als einen Cache für Methodenergebnisse vorstellen. Weitere Einzelheiten finden Sie auf Seite 387, wo die Definition in Einführung in Algorithmen (3e), Cormen et al.

Ein einfaches Beispiel für die Berechnung von Fakultäten mit Hilfe von Memoisierung in Python wäre etwa so:

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 auch komplizierter vorgehen und den Memoisierungsprozess in einer Klasse kapseln:

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)

Ein Merkmal, das als " Dekorateure " wurde in Python 2.4 hinzugefügt, so dass Sie jetzt einfach das Folgende schreiben können, um dasselbe zu erreichen:

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

En Python-Dekorator-Bibliothek hat einen ähnlichen Dekorator namens memoized die etwas robuster ist als die Memoize Klasse, die hier gezeigt wird.

Answer 2

functools.cache Dekorateur:

Mit Python 3.9 wurde eine neue Funktion functools.cache . Es speichert das Ergebnis einer Funktion, die mit einem bestimmten Satz von Argumenten aufgerufen wurde, im Speicher, was eine Memoisierung darstellt. Es ist einfach zu benutzen:

import functools
import time

@functools.cache
def calculate_double(num):
    time.sleep(1) # sleep for 1 second to simulate a slow calculation
    return num * 2

Das erste Mal, dass Sie anrufen caculate_double(5) dauert es eine Sekunde und gibt 10 zurück. Wenn Sie die Funktion ein zweites Mal mit demselben Argument aufrufen calculate_double(5) wird sofort 10 zurückgegeben.

Hinzufügen der cache Dekorator stellt sicher, dass die Funktion, wenn sie kürzlich für einen bestimmten Wert aufgerufen wurde, diesen Wert nicht neu berechnet, sondern ein zwischengespeichertes früheres Ergebnis verwendet. In diesem Fall führt dies zu einer enormen Geschwindigkeitssteigerung, während der Code nicht mit den Details der Zwischenspeicherung überladen ist.

( Editer (Das vorherige Beispiel berechnete eine Fibonacci-Zahl mit Hilfe von Rekursion, aber ich habe das Beispiel geändert, um Verwirrung zu vermeiden, daher die alten Kommentare).

functools.lru_cache Dekorateur:

Wenn Sie ältere Versionen von Python unterstützen müssen, functools.lru_cache funktioniert in Python 3.2+. Standardmäßig werden nur die 128 zuletzt verwendeten Aufrufe zwischengespeichert, aber Sie können die maxsize a None um anzugeben, dass der Cache nie ablaufen soll:

@functools.lru_cache(maxsize=None)
def calculate_double(num):
    # etc

---

Answer 3

Die anderen Antworten beschreiben recht gut, worum es sich handelt. Ich werde das nicht wiederholen. Nur einige Punkte, die für Sie nützlich sein könnten.

Normalerweise ist die Memoisierung eine Operation, die Sie auf jede Funktion anwenden können, die etwas (Teures) berechnet und einen Wert zurückgibt. Aus diesem Grund wird sie oft als eine Tapezierer . Die Umsetzung ist einfach und würde etwa so aussehen

memoised_function = memoise(actual_function)

oder als Dekorator ausgedrückt

@memoise
def actual_function(arg1, arg2):
   #body

Answer 4

Ich habe dies als äußerst nützlich empfunden

from functools import wraps

def memoize(function):    
    memo = {}

    @wraps(function)
    def wrapper(*args):

        # add the new key to dict if it doesn't exist already  
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper

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

fibonacci(25)

Answer 5

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]