Memoisation

Autor: Leandro Alegsa Erstellungsdatum: 3. November 2020

Memoisierung (oder Memoisation) ist eine Technik aus der Computerprogrammierung zur Optimierung eines Computerprogramms. Computerprogramme rufen Funktionen auf. Jede Funktion berechnet ein Ergebnis, das sie zurückgibt. Die Memoisierung ist einfach: Bevor der Wert vom Funktionsaufruf zurückgegeben wird, wird er in einer Tabelle (oder einem assoziativen Array) gespeichert. Wie ein Cache kann dieses Array nur eine begrenzte Anzahl f von Ergebnissen speichern. Die Funktion kann dann so geändert werden, dass sie versucht, den Wert der Eingabe in ihrer Nachschlagetabelle nachzuschlagen. Dieses Nachschlagen ist viel kostengünstiger als eine erneute Berechnung. Auch wie ein Cache: Die Datentabelle wird regelmäßig bereinigt, z.B. werden die Werte, die eine bestimmte Zeit lang nicht nachgeschlagen wurden, entfernt.

Obwohl sie mit dem Caching zusammenhängt, bezieht sich die Memoisierung auf einen speziellen Fall dieser Optimierung und unterscheidet sie von Formen des Caching wie Pufferung oder Seitenersetzung. Im Zusammenhang mit einigen logischen Programmiersprachen wird die Memoisierung auch als Tabling bezeichnet; siehe auch Nachschlagetabelle.

Fragen und Antworten

F: Was ist Memoisierung?

A: Memoisierung ist eine Technik in der Computerprogrammierung, mit der Programme optimiert werden, indem die Ergebnisse von Funktionsaufrufen in einer Tabelle oder einem assoziativen Array gespeichert werden.

F: Wie funktioniert die Memoisierung?

A: Bevor ein Wert von einem Funktionsaufruf zurückgegeben wird, wird er in einer Nachschlagetabelle gespeichert. Später wird die Funktion den Wert der Eingabe in der Nachschlagetabelle nachschlagen, anstatt ihn neu zu berechnen, was wesentlich kostengünstiger ist.

F: Was sind die Vorteile der Memoisierung?

A: Die Memoisierung kann die Programmleistung verbessern, indem sie die Anzahl der erforderlichen Berechnungen reduziert. Es handelt sich außerdem um eine einfache Optimierungstechnik, die auf viele Programme angewendet werden kann.

F: Wie funktioniert die Nachschlagetabelle?

A: Die Nachschlagetabelle speichert die von den Funktionsaufrufen zurückgegebenen Werte. Wie ein Cache hat sie eine Begrenzung, wie viele Ergebnisse sie speichern kann, und sie wird regelmäßig geleert, indem Werte entfernt werden, auf die eine Zeit lang nicht zugegriffen wurde.

F: Was unterscheidet die Memoisierung von anderen Formen der Zwischenspeicherung?

A: Memoisierung ist ein spezieller Fall von Caching, der sich auf die Speicherung der Ergebnisse von Funktionsaufrufen bezieht. Sie unterscheidet sich von anderen Formen der Zwischenspeicherung wie Pufferung oder Seitenersetzung.

F: Wird die Memoisierung in logischen Programmiersprachen verwendet?

A: Ja, Memoisierung ist in einigen logischen Programmiersprachen auch als Tabling bekannt.

F: Was ist die Beziehung zwischen Memoisierung und einer Nachschlagetabelle?

A: Bei der Memoisierung wird eine Nachschlagetabelle verwendet, um die Ergebnisse von Funktionsaufrufen zu speichern. Die Funktion kann die Werte in der Tabelle nachschlagen, anstatt sie neu zu berechnen.