Memoisation - de.LinkFang.org

Memoisation

Memoisation ist eine Technik, um Computerprogramme zu beschleunigen, indem Rückgabewerte von Funktionen zwischengespeichert anstatt neu berechnet werden. Memoisation ähnelt Dynamischer Programmierung, bewahrt jedoch im Gegensatz zu dieser die grundlegende Vorgehensweise des zu beschleunigenden Verfahrens.

Funktionen können nur memoisiert werden, wenn sie referenziell transparent sind, d. h., sie geben bei gleichen Eingaben immer dieselben Ausgaben zurück. Operationen, die nicht referenziell transparent sind, aber bei denen Abweichungen in der Ausgabe relativ selten zu erwarten sind, können mit anderen Methoden (wie Cache) zwischengespeichert werden. Generell haben memoisierte Ausgaben kein Ablaufdatum und müssen nicht neu berechnet werden, wie das bei Caches im Allgemeinen der Fall ist. In imperativen Programmiersprachen wird Memoisation üblicherweise in Form eines assoziativen Arrays implementiert.

In einer funktionalen Programmiersprache ist es möglich eine Funktion höherer Ordnung memoize für jede referenziell transparente Funktion zu konstruieren. In Sprachen ohne die Möglichkeit einer Funktion höherer Ordnung muss die Memoisation separat in jede Funktion implementiert werden, die davon Gebrauch macht.

Inhaltsverzeichnis

Etymologie


Memoisation ist aus dem lateinischen Wort Memorandum abgeleitet, was so viel wie „das zu Erinnernde“ bedeutet. Im allgemeinen Sprachgebrauch wird Memorandum auch Memo genannt und man kann Memoisation als eine Funktion in eine Memo umwandeln verstehen.

Das Wort Memoisation wird oft mit dem englischen Wort Memorization verwechselt, welches eine ähnliche Bedeutung aufweist.

Beispiel


Ein einfaches Programm, das die Fibonacci-Zahlen berechnet, ist

function fib(n)
    if (n <= 2)
        return 1
    return fib(n-1) + fib(n-2)

(Dieses Beispiel soll keine effiziente Implementierung darstellen. Es dient ausschließlich der Illustration der Memoisation.)

Weil fib mit denselben Parametern mehrmals aufgerufen wird, ist die Laufzeit der Funktion größer als O(1.6n). Falls man die Werte von fib bei der ersten Berechnung memoisiert und die Speicherreservierung und -initialisierung in O(n) vorgenommen werden kann, sinkt die Laufzeit auf O(n).

Speicher für Memo-Array memo reservieren und alle Werte darin auf 0 setzen.
Initialisiere memo[1] und memo[2] auf 1.function fib(n)
    if (memo[n] ≠ 0) return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Anstelle eines Arrays soll nun ein assoziatives Array zur Verwendung stehen. Bietet die Programmiersprache die Möglichkeit zur Formulierung von Closures, so lässt sich eine Funktion memoize schreiben, die das Prinzip der Memoisation von fib abstrahiert.

function memoize(f)
    var memo = { }
    return function(n)
        if (n not in memo) memo[n] = f(n)
        return memo[n]fib = memoize(fib)

Zusätzlich zur Memoisation tritt bei diesem Beispiel gleichzeitig Rekursion auf. Hierbei ist zu beachten, dass fib auch innerhalb ihrer eigenen Definition eine Variable sein muss, deren Inhalt mit der memoisierten Version überschrieben wurde. Wenn das nicht möglich ist, kann man die Memoisation alternativ in den Fixpunkt-Kombinator einbauen. Dieser ist zunächst gegeben durch:

function fix(F)
    return function f(n)
        return F(f,n)

Der modifizierte Algorithmus beinhaltet nun das zuvor beschriebene Verfahren:

function fix(F)
    var memo = { }
    return function f(n)
        if (n not in memo) memo[n] = F(f,n)
        return memo[n]fib = fix(function(f,n))
    return 1 if n <= 2 else f(n-1) + f(n-2))

Geschichte


Das englische Wort memoization entstand 1968 durch Donald Michie aus seinem Artikel Memo functions and machine learning in der Zeitschrift Nature.

Literatur


Weblinks





Kategorien: Optimierung

Werbung:


Quelle: Wikipedia - https://de.wikipedia.org/wiki/Memoisation (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 04.03.2020 09:08:07 CET - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.