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

Lösung, die sowohl mit Positions- als auch mit Schlüsselwortargumenten arbeitet, unabhängig von der Reihenfolge, in der die Schlüsselwortargumente übergeben wurden (mit 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: Identifizierung äquivalenter varargs-Funktionsaufrufe für die Memoisierung in Python

Answer 2

Ich wollte nur zu den bereits gegebenen Antworten hinzufügen, dass die Python-Dekorator-Bibliothek hat einige einfache aber nützliche Implementierungen, die auch "unhashable types" memoisieren können, im Gegensatz zu functools.lru_cache .

Answer 3

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]

Answer 4

Wenn Geschwindigkeit eine Rolle spielt:

• @functools.cache y @functools.lru_cache(maxsize=None) sind gleich schnell und benötigen 0,122 Sekunden (bester von 15 Durchläufen) für eine Million Schleifen auf meinem System
• eine globale Cache-Variable ist wesentlich langsamer und benötigt auf meinem System 0,180 Sekunden (beste von 15 Durchläufen) für eine Million Schleifen.
• a self.cache Die Klassenvariable ist immer noch etwas langsamer und benötigt auf meinem System 0,214 Sekunden (beste von 15 Durchläufen) für die Schleife von einer Million Mal

Die beiden letztgenannten sind ähnlich implementiert, wie es in der derzeit meistgewählte Antwort .

Dies geschieht ohne Speichererschöpfung zu verhindern, d.h. ich habe keinen Code in der class o global Methoden, um die Größe des Caches zu begrenzen, ist dies wirklich die Standardimplementierung. Die lru_cache Methode hat das kostenlos, wenn Sie das brauchen.

Eine offene Frage für mich wäre, wie man etwas testen kann, das eine functools Dekorateur. Ist es möglich, den Cache irgendwie zu leeren? Unit-Tests scheinen am saubersten zu sein, wenn man die Klassen-Methode verwendet (wo man eine neue Klasse für jeden Test instanziieren kann) oder, in zweiter Linie, die globale Variablen-Methode (da man die yourimportedmodule.cachevariable = {} um sie zu leeren).