Memoization in Haskell

nachtfeuer

Schreib doch einfach mal die genannten Funktionen und Abläufe jeweils im Vergleich in Einzelschritten auf.

Das hilft dem Verständnis oft sehr gut auf die Sprünge, wie halt beim Austüfteln von Algorithmen mit Bleistift und Papier.

Und wie weit kommst du bei der Fibonacci-Berechnung im Kopf?

nachtfeuer schrieb:

Schreib doch einfach mal die genannten Funktionen und Abläufe jeweils im Vergleich in Einzelschritten auf.

Hab ich im oberen Post versucht. Das Ergebnis ist das richtige, nicht aber die Laufzeitkomplexität.

Kannst du meinen Denkfehler aufzeigen?

knivil

(map fib [0 ..] !!)

Das ist deine Closure. Sie besitzt intern eine lazy Liste mit alle Fibonacci-Zahlen. Elemente die bis dahin noch nicht benoetigt wurden, sind auch noch nicht berechnet. Prinzipiell eine unendliche Datenstruktur mit einer Indirektion.

Etwas einfacher ohne Indirektion:

ones ::[Integer]
ones = 1:ones

Um das Beispiel zu verstehen, muss lazyness, closures und unendlich Datenstrukturen verstanden sein.

Bashar

knivil schrieb:

(map fib [0 ..] !!)
Das ist deine Closure. Sie besitzt intern eine lazy Liste mit alle Fibonacci-Zahlen. Elemente die bis dahin noch nicht benoetigt wurden, sind auch noch nicht berechnet. Prinzipiell eine unendliche Datenstruktur mit einer Indirektion.

Ich glaub das hat hier jeder verstanden. Die Frage war, warum die schon berechneten Ergebnisse der Liste behalten werden, so dass man den Memoization-Effekt hat, und nicht einfach weggeworfen und bei Bedarf neu berechnet werden.

knivil

Genau deswegen:

memoized_fib = (map fib [0 ..] !!)

Mal in der Sprache C++. memoized_fib als globaler Funktionszeiger zeigt auf den Funktor (map fib [0 ..] !!) . Das ist ein Objekt. Also warum geht dieser Funktor/Objekt nicht einfach nach dem Aufruf weg? Na weil der globale Zeiger memoized_fib immernoch drauf zeigt und das Objekt demnach nicht vom Garbage collector abgeraeumt wird.

Zeus

knivil schrieb:

Genau deswegen:
memoized_fib = (map fib [0 ..] !!)
Mal in der Sprache C++. memoized_fib als globaler Funktionszeiger zeigt auf den Funktor (map fib [0 ..] !!) . Das ist ein Objekt. Also warum geht dieser Funktor/Objekt nicht einfach nach dem Aufruf weg? Na weil der globale Zeiger memoized_fib immernoch drauf zeigt und das Objekt demnach nicht vom Garbage collector abgeraeumt wird.

Ist das wirklich global, ich hätte gedacht, dass der Zeiger/Reference bist zum Call Site propagiert wird.

knivil

dass der Zeiger/Reference bist zum Call Site propagiert wird.

Kannst du das naeher ausfuehren, ich Weiss nicht wie und was du damit meinst.

Zeus

knivil schrieb:

dass der Zeiger/Reference bist zum Call Site propagiert wird.

Kannst du das naeher ausfuehren, ich Weiss nicht wie und was du damit meinst.

Eigentlich intressiert mich, ob Haskell das nun wirklich global anlegt oder auch kürzere Lebenszeiten gibt. Unter der JVM würden indirekte Referenze langen. fib und memoized_fib sind "Funktoren", während memoized_fib noch die Map referenziert. Solange der Aufrufer die Referenz von memoized_fib hat, lebt auch das Closure-Objekt,d.h. es könnte Garbage werden, wenn der Stack abgearbeitet wurde.

Es scheint tatsächlich am Closure zu liegen.

closureless_fib :: Int -> Integer
closureless_fib = \n -> map fib [0 ..] !! n
  where fib 0 = 0
        fib 1 = 1
        fib n = closureless_fib (n-2) + closureless_fib (n-1)

Dieser Code ist enorm langsam.

Die explizit memoizierte Variante ist dagegen wieder schnell:

yetanother_fib :: Int -> Integer
yetanother_fib = make_use_of table
 where table = map fib [0 ..]
       make_use_of dat n = dat !! n
       fib 0 = 0
       fib 1 = 1
       fib n = yetanother_fib (n-2) + yetanother_fib (n-1)

Es geht also darum, die Daten in einer partiell angewendeten Funktion zu speichern.

Jetzt verstehe ich auch die Wiki-Seite besser. Danke knivil!

knivil

Solange der Aufrufer die Referenz von memoized_fib hat, lebt auch das Closure-Objekt,d.h. es könnte Garbage werden, wenn der Stack abgearbeitet wurde.

Die Referenz ist global, genau wie in C beispielsweise jede Funktion. Sie wird einmal bei Programmstart angelegt.