imported>Engi25: englische Schreibweise ergänzt

2023-07-15T18:13:52Z

englische Schreibweise ergänzt

Neue Seite

'''Memoisation''' (engl.: '''Memoization''') oder '''Memoisierung''' ist eine Technik, um [[Computerprogramm]]e zu beschleunigen, indem Rückgabewerte von Funktionen zwischengespeichert anstatt neu berechnet werden. Memoisation ähnelt [[Dynamische Programmierung|Dynamischer Programmierung]], bewahrt jedoch im Gegensatz zu dieser die grundlegende Vorgehensweise des zu beschleunigenden Verfahrens.

Funktionen können nur memoisiert werden, wenn sie [[Referenzielle Transparenz|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 [[Imperative Programmierung|imperativen Programmiersprachen]] wird Memoisation üblicherweise in Form eines [[Assoziatives Array|assoziativen Arrays]] implementiert.

In einer [[Funktionale Programmierung|funktionalen Programmiersprache]] ist es möglich, eine [[Funktion höherer Ordnung]] <code>memoize</code> 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.

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

Memoisation ist aus dem [[Latein|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 <code>fib</code> mit denselben Parametern mehrmals aufgerufen wird, ist die Laufzeit der Funktion größer als [[O-Notation|O]](1.6<sup>n</sup>). Falls man die Werte von <code>fib</code> bei der ersten Berechnung memoisiert und die Speicherreservierung und -initialisierung in [[O-Notation|O]](n) vorgenommen werden kann, sinkt die Laufzeit auf [[O-Notation|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 [[Closure (Funktion)|Closures]], so lässt sich eine Funktion memoize schreiben, die das Prinzip der Memoisation von <code>fib</code> 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 <code>fib</code> 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))

== Literatur ==

* {{Literatur
|Autor = Peter Norvig
|Titel = Paradigms of Artificial Intelligence Programming
|Auflage = 1.
|Verlag = Morgan Kaufmann
|Jahr = 1991
|Seiten = 269–275
|ISBN = 1558601910
}}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] und [[Clifford Stein]], 2001. ''[[Introduction to Algorithms]].'' 2. Auflage, MIT Press & McGraw-Hill. ISBN 0-262-03293-7. S. 347ff.

== Weblinks ==
*[http://www.cliki.net/memoize Memoize] – Memoize ist eine kleine Bibliothek für Memoisation in Common Lisp. Es wurde von Tim Bradshaw geschrieben.
*[http://search.cpan.org/dist/Memoize/Memoize.pm Memoize.pm] – ein [[Perl (Programmiersprache)|Perl]]-Modul, welches memoisierte Unterroutinen enthält.
*[http://www.onjava.com/pub/a/onjava/2003/08/20/memoization.html Java Memoisation] – ein Beispiel in Java, welches eine dynamische Proxyklasse benutzt.
*[http://raa.ruby-lang.org/project/memoize/ memoize] – ein [[Ruby (Programmiersprache)| Ruby]]-Modul mit Memoise-Methoden.
*[http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201 Python Memoisation] – ein Beispiel der Memoisation in Python.

[[Kategorie:Optimierung]]

Memoisation - Versionsgeschichte

imported>Engi25: englische Schreibweise ergänzt