Memoization

Memoization

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 wo 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

fib(n) {
   if n is 1 or 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(n) 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;
fib(n) {
   if memo[n] is not zero, return memo[n];
   memo[n] = fib(n-1) + fib(n-2);
   return memo[n];
}

Geschichte

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

Literatur

  • Peter Norvig: Paradigms of Artificial Intelligence Programming. 1. Auflage. Morgan Kaufmann, 1991, ISBN 1558601910, S. 269–275. 
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd ed. MIT Press & McGraw-Hill. ISBN 0-262-03293-7. S. 347ff.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Memoization — Mémoization En informatique, la mémoization est une technique d optimisation de code consistant à réduire le temps d exécution d une fonction en mémorisant ses résultats d une fois sur l autre. Bien que liée à la notion de cache, la mémoization… …   Wikipédia en Français

  • Memoization — Not to be confused with Memorization. In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.… …   Wikipedia

  • Mémoization — En informatique, la mémoization est une technique d optimisation de code consistant à réduire le temps d exécution d une fonction en mémorisant ses résultats d une fois sur l autre. Bien que liée à la notion de cache, la mémoization désigne une… …   Wikipédia en Français

  • memoization — noun A technique in which partial results are recorded (forming a memo) and then can be re used later without having to recompute them …   Wiktionary

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Password cracking — is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password. The purpose of password cracking might be to help a user recover a… …   Wikipedia

  • Memory bound function — Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of available memory to hold data. In other words, the limiting factor of solving a given problem is the memory… …   Wikipedia

  • Camlp4 — is a software system for writing extensible parsers for programming languages. It provides a set of Objective Caml libraries that are used to define grammars as well as loadable syntax extensions of such grammars. Camlp4 stands for Caml… …   Wikipedia

  • Longest common subsequence problem — Not to be confused with longest common substring problem. The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). Note that subsequence is different from a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”