Memoisierung

Memoisierung, auch Memoization, ist eine Optimierungstechnik der Informatik, die darauf abzielt, wiederholte Aufrufe einer teuren Funktion durch das Speichern ihrer Ergebnisse zu beschleunigen. Wird ein Funktionsaufruf mit bestimmten Argumenten einmal berechnet, wird das Ergebnis in einem Cache abgelegt. Bei späteren Aufrufen mit denselben Argumenten wird das gespeicherte Ergebnis direkt zurückgegeben, ohne die Funktion erneut auszuführen.

In der Praxis wird ein Schlüssel aus den Funktionsargumenten gebildet, der typischerweise hashbar ist. Der Cache kann eine einfache Datenstruktur wie ein Wörterbuch oder eine spezialisierte Struktur sein. Memoisierung ist eine Form des Cachings und wird oft innerhalb einer Funktion oder eines Objekts implementiert, zum Beispiel als Decorator in Python.

Anwendungsfälle liegen vor allem bei rekursiven Algorithmen mit überlappenden Teilproblemen oder bei kostenintensiven reinen Funktionen. Gegenüber dem Bottom-up-Ansatz (Tabulation) bietet Top-down-Memoisierung Nachladeverhalten nach Bedarf, wodurch man nur Speicher für tatsächlich genutzte Zwischenresultate reserviert. Nachteile sind erhöhter Speicherbedarf, zusätzlicher Overhead durch Cache-Verwaltung und potenzielle Probleme bei der Synchronisation in Mehrprozess- oder Mehrthread-Umgebungen.

Beispiele: In Programmiersprachen lassen sich Memoisierungstechniken oft über eingebaute Mechanismen realisieren, etwa Python-Decorators wie lru_cache oder benutzerdefinierte Cache-Strukturen. Typische Anwendungsfälle umfassen die Beschleunigung rekursiver Funktionen, dynamische Programmierung und Situationen mit vielen wiederholten Teilergebnissen.