Python-Programme beschleunigen mittels Memoisation!

Manchmal gibt es Funktionen für Berechnungen, die ewig laufen - was unter anderem oft bei rekursiven Berechnungen wie zum Beispiel bei der klassischen Fibonacci-Folge, der Fall ist.

Bei solchen Funktionen kann Memoisation (engl. memoization) der Booster sein, den du benötigst. Dabei wird der Rückgabewert dem Eingabewert der Funktion zugewiesen und wird beim nächsten Abrufen der Funktion mit demselben Eingabewert direkt zurückgegeben, ohne noch einmal die Funktion rechnen zu lassen.

Der Ablauf noch einmal verschriftlicht:

1. Die Funktion und der Wert x werden in das Memoisation-Konzept geworfen.
2. Es wird geprüft, ob für x der Übergabeparameter schon einen Rückgabewert in einer Datenstruktur besitzt.
3. Falls das der Fall ist, wird der Wert zurückgegeben; in unserem Fall der Rückgabewert 10.
4. Falls nun noch kein Rückgabewert gespeichert wurde, wird nun die Funktion foo() ausgeführt.
5. Dieses Wertepaar von Rückgabewert und Übergabeparameter wird nun für den nächsten Funktionsabruf gespeichert.
6. Abschließend wird der Rückgabewert 10 zurückgegeben.

Unsere Basis für die nachfolgenden Anleitungen

Nun eine kurze Erklärung zu unserer Code-Basis. Auf diese werde ich im Nachhinein nicht mehr im Detail eingehen, da ich diese Basis unverändert nutze. In unserem Beispiel beziehe ich mich auf Python 3 (meine Version beim Ausführen war 3.8.1 unter MacOS)

from time import sleep # Um die Funktion zu Verzögern
import timeit # Zur Zeitmessung

# Funktion Eingabe ist ein Str und Ausgabe ist auch ein Str
def foo(var: int) -> int:
    sleep(10)
    return 2*var

# Häufigkeit des Funktions Abruf
# Später für die Zeit Berechnung Relevant
loops = 1

start = timeit.default_timer() # Zeit Berechnung

for i in range(0,loops):
    print(foo(5));

stop = timeit.default_timer() # Zeit Berechnung

print('Time: ', (stop - start) / loops) # Zeit Berechnung

Unsere Basis, die wir mit verschieden Varianten der Memoisation ausstatten.

Am Anfang stehen unsere Import Statements; einmal time und timeit. Diese benötigen wir primär für die Zeitberechnung und das Verzögern unserer Testfunktion.

Einmal haben wir hier unsere Testfunktion, die wir "foo" nennen. Sie hat eine Zeitverzögerung von 10 Sekunden, um den Effekt der Memoisation zu verdeutlichen - in einer reellen Anwendung wäre das eine sehr aufwändige Berechnung.

Nun kommt noch der Teil, wo wir die Funktion x-mal ausführen und davon die Zeit messen. Mehr brauchen wir nicht für unseren Testaufbau!

Memoisation (memoization) als Dekorateure

Decorator-Funktionen sind ein Design Pattern um eine ursprüngliche Funktion mit einer neuen Decorator-Funktion zu verzieren und zu modifizieren, ohne die ursprüngliche Funktion zu ändern.

Der Vorteil dieses Designkonzepts ist, dass wir die Memoisation nicht in jeder Funktion aufrufen müssen. Wir müssen lediglich der Funktion einen Dekorateur zuweisen.

So können wir die Memoisation auch jeder Zeit wieder deaktivieren - ohne aufwändigere Code-Änderung.

Funktionsdekorateure für die Memoisation (memoization)

In dem folgenden Beispiel sehen wir nun unsere Memoisation-Funktion. Diese erwartet als Übergabeparameter die Funktion, welche in der memorywrap-Funktion abgerufen wird - falls die args nicht bereits im memory definiert wurden. Zum Schluss wird die Funktion zurückgegeben.

Die args sind ein Tuple mit allen Übergabeparametern. Zum Entpacken in der Funktion nutzen wir den *-Operator, der das Tuple entpackt.

def hc_memoization(function):
    memory = {}

    def memoryWrap(*args):
        if args not in memory:    
            memory[args] = function(*args)

        return memory[args]

    return memoryWrap

Wichtig: Da unsere Memory ein Dictionary ist, dürfen wir nur immutable Datentypen als Argumente übergeben.

Beim Arbeiten mit der Funktion solltest du das Wissen im Hintergrund behalten. Wir könnten aber z.B. die Liste in einen str konverieren. Du kannst einmal in den Artikel "Typumwandlung in Python" schauen, dort findest du einen Ansatz wie du das lösen kannst.

Der Fehler, den wir erzeugen, wenn wir nun foo mit einer Liste aufrufen, sieht wie folgt aus:

TypeError: unhashable type: 'list' # Weil list ein mutable type ist!

Da wir unsere Funktion nun definiert haben, können wir diese "hc_memoization" unserer Funktion "foo" zuweisen. Das sieht wie folgt aus:

@hc_memoization
def foo(var: str) -> str:
    sleep(10)
    return "foo" + var

Nun braucht nur noch der erste Abruf einer Funktion mit immer demselben Parameter 10 Sekunden. Die anderen laufen nur so lange, wie es dauert die Daten aus dem memory-Dictionary herauszuholen.

Class Dekorateure für die Memoisation (memoization)

Im Folgenden haben wir noch einmal ein Beispiel mit einer Klasse - dabei wird auch wieder hc_memoization als Dekorator verwendet. Hier wird allerdings dann zuerst die init-Methode und dann die call-Methode aufgerufen. Von der Funktion her ist es dieselbe Logik wie die Variante mit den Funktionen. Der Vorteil dieser Variante zeigt sich, wenn man den objektorientierten Ansatz bevorzugt und/oder noch weitere Methoden definieren möchte.

class hc_memoization(object):

    def __init__(self, function):
        self.memory = {}
        self.function = function

    def __call__(self, *args):

        if args not in self.memory:
            self.memory[args] = self.function(*args)

        return self.memory[args];

Der finale, fertige Aufruf sieht genauso aus wie bei der Memoisation mittels der Funktion.

@hc_memoization
def foo(var: str) -> str:
    sleep(10)
    return "foo" + var

lru_cache für die Memoisation (memoization)

In den functools gibts eine Klasse "lru_cache". Diese arbeitet ähnlich wie unser Beispiel oben; der Unterschied ist, dass diese Methode deutlich mehr Optionen und Möglichkeiten bietet.

from functools import lru_cache

Als erstes müssen wir von funtools das lru_cache importieren. Wenn das passiert ist, können wir lru_cache als Dekorateur abrufen. Dabei ist zu beachten, dass man dort auch einen Parameter für die Anzahl der unterschiedlichen Paare, die man speichern will, übergeben kann.

Standardmäßig steht maxsize auf 128. Das kann auf jeden beliebigen Wert gesetzt werden oder auf None, für den Fall, dass nicht klar ist wie viele Werte gespeichert werden müssen.

@lru_cache(maxsize=128)
def foo(var: str) -> str:
    sleep(10)

    return "foo" + var

Des Weiteren gibt es noch eine coole Methode, die dir weitere Infos zu der laufenden Memoisation zurückgibt. Diese würde für unsere Funktion mit einem Durchlauf von 1000 wie folgt aussehen:

CacheInfo(hits=999, misses=1, maxsize=128, currsize=1)

Zur Verdeutlichung, hier noch einmal das ganze Code-Beispiel für lru_cache mit CacheInfo-Ausgabe.

# Laden der notwendigen Abhänigkeiten.

from functools import lru_cache
from time import sleep
import timeit

# lru_cache als Dekorator für foo definieren

@lru_cache
def foo(var: str) -> str:
    sleep(10)

    return "foo" + var

loops = 1000

start = timeit.default_timer()

# foo 1000 mal Aufrufen
for i in range(0,loops):
    foo("bar")

# CacheInfo von lru_cache
print(foo.cache_info())

stop = timeit.default_timer()

print('Time (lru_cache): ', (stop - start) / loops)
print('Complet Time',(stop - start))

Boosting über Memoisation - Zeitanalyse

Der Vorteil der Memoisation liegt auf der Hand: die Berechnung läuft deutlich schneller. Dieselbe foo-Funktion 1000 Mal abgerufen (ohne Memoisation) braucht 2 Stunden und 45 Minuten. Im Vergleich: eine Funktion der Memoisation-Variante braucht nur 10 Sekunden (gerundet).

So kann das in einer reellen Anwendung ein riesen Vorteil ausmachen. Ich habe im Nachfolgenden euch einmal eine Übersicht angelegt, wo ihr sehen könnt, welche Methode wie lange braucht; einmal für einen Abruf der Funktion und einmal für die 1000 Abrufe insgesamt.

*Diese Werte habe ich berechnet und nicht 1000 Mal die Funktion foo mit jeweils einem Delay von 10 Sekunden ausgeführt. Für die Berechnung habe ich die Werte von 10 Durchläufen genommen und daraus berechnet, wie lange jeweils einer dauert. Und dann entsprechend mit 1000 multipliziert.

Wann macht Memoisation Sinn? Und wann solltest du es lassen?

Memoisation macht immer nur dann Sinn, wenn in der Funktion keine Daten aus anderen Quellen geladen werden, sondern immer nur mit dem input der output berechnet wird, der jeweils nicht (wie Datenbank- oder Zeitabfragen oder andere Werte des Betriebssystems) von Faktoren in der Funktion abhänig ist.