In der aktuellen Übungsaufgabe des Functional Programming-Kurses, den ich mache, müssen wir eine Memo-Version einer bestimmten Funktion machen. Um die Memoisierung zu erklären, wird folgendes Beispiel gegeben:
%Vor%Aber ich verstehe nicht ganz, wie das funktioniert.
Nennen wir fibm 3 .
Aus anderen Fragen / Antworten und Googeln habe ich gelernt, dass die ausgewertete Fibliste irgendwie zwischen Anrufen geteilt wird.
Bedeutet dies, dass zum Beispiel für fiblist !! 2 + fiblist !! 1 die Listenwerte nur einmal für fiblist !! 2 berechnet und dann nur für fiblist !! 1 wiederverwendet werden?
Dann werden die zwei Fibonacci-Nummern nur einmal pro Aufruf berechnet, also keine exponentielle Anzahl von Aufrufen. Aber was ist mit den "niedrigeren" Ebenen des Aufrufs in der Funktion fiblist ? Wie profitieren sie von der berechneten fiblist im ursprünglichen fibm Aufruf?
Der entscheidende Teil hier ist, dass die Liste faul ausgewertet wird, was bedeutet, dass das Element nicht berechnet wird, bis es das erste Mal angefordert wird. Sobald es ausgewertet wurde, ist es für etwas anderes da, um nachzuschlagen. In deinem Beispiel hast du recht damit, dass die Werte nur einmal für fiblist !! 2 berechnet und dann für fiblist !! 1 wiederverwendet werden.
Die 'unteren Ebenen' der Fiblisten-Funktion funktionieren auf die gleiche Weise. Beim ersten Aufruf von fiblist !! 1 wird dies durch Aufruf von fibm 1 ausgewertet, was nur 1 ist, und dieser Wert bleibt dann in der Liste. Wenn Sie versuchen, eine höhere Fibonacci-Zahl zu erreichen, ruft fiblist fibm auf, was diese Werte in niedrigeren - und möglicherweise bereits ausgewerteten - Positionen von fiblist nachschlägt.
Gehen wir Schritt für Schritt durch die Auswertung. Zusätzlich zum aktuellen Ausdruck zeigen wir den aktuellen Status der Auswertung von fiblist im Speicher an. Dort schreibe ich <expr> , um einen unbewerteten Ausdruck zu bezeichnen (oft Thunk genannt), und >expr< , um einen unausgewerteten Ausdruck zu bezeichnen, der gerade ausgewertet wird. Sie können eine faule Bewertung in Aktion sehen. Die Liste wird nur so weit wie gewünscht ausgewertet, und abgeschlossene Subcomputationen werden für die zukünftige Wiederverwendung freigegeben.
Da fiblist eine globale Konstante ist (oft als CAF für "constant applicative form" bezeichnet), wird der teilweise ausgewertete Status der Liste beibehalten und zukünftige Aufrufe von fibm werden bereits ausgewertete Elemente der Liste wiederverwenden. Die Liste wird jedoch immer größer und verbraucht immer mehr Speicher.
Tags und Links haskell fibonacci memoization