Kann jemand das Konzept hinter Haskells Memoisierung erklären?

12

(Beachten Sie, dass ich die Frage hier stelle, da es sich eher um die konzeptionelle Mechanik als um ein Codierungsproblem handelt.)

Ich arbeite an einem kleines Programm, das eine Folge von Fibonacci - Zahlen in seinem equasion Verwendung wurde, aber ich merkte , dass , wenn ich eine bestimmte Anzahl überwindet es quälend langsam bekam, googeln um ein wenig ich auf eine Technik , die in Haskell als bekannt gestolpert Memoization, Sie zeigten Code, der so funktioniert:

-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

Meine Frage an euch ist also, wie oder warum funktioniert das?

Liegt es daran, dass es irgendwie gelingt, den größten Teil der Liste zu durchlaufen, bevor die Berechnung aufholt? Aber wenn Haskell faul ist, gibt es nicht wirklich eine Berechnung, die nachholen muss ... Also, wie funktioniert es?

Elektrischer Kaffee
quelle
1
Können Sie klarstellen, was Sie damit meinen the calculation catches up? Übrigens ist Memoization nicht spezifisch für Haskell: en.wikipedia.org/wiki/Memoization
Simon Bergot
Siehe meine Erklärung unter Killans Antwort
Electric Coffee
2
Liebe deine Frage; Nur eine kurze Anmerkung: Die Technik genannt wird Memo i sation, nicht memo ri sation.
Racheet

Antworten:

11

Nur um die Mechanik hinter dem eigentlichen Auswendiglernen zu erklären,

memo_fib = (map fib [1..] !!)

erzeugt eine Liste von "Thunks", nicht ausgewerteten Berechnungen. Denken Sie an diese wie ungeöffnete Geschenke, solange wir sie nicht anfassen, laufen sie nicht.

Sobald wir einen Thunk evaluieren, evaluieren wir ihn nie wieder. Dies ist tatsächlich die einzige Form der Mutation in "normalem" Haskell. Die Thunks mutieren, sobald sie ausgewertet wurden, zu konkreten Werten.

Zurück zu Ihrem Code, Sie haben eine Liste von Thunks, und Sie führen diese Baumrekursion immer noch durch, aber Sie rekursieren mit der Liste, und sobald ein Element in der Liste ausgewertet wurde, wird es nie wieder berechnet. So vermeiden wir die Baumrekursion in der naiven Fib-Funktion.

Als tangential interessanter Hinweis ist dies besonders schnell, wenn eine Reihe von Fibonnaci-Zahlen berechnet wird, da diese Liste nur einmal ausgewertet wird. Wenn Sie also memo_fib 10000zweimal rechnen , sollte das zweite Mal sofort erfolgen. Dies liegt daran, dass Haskell Argumente für Funktionen nur einmal ausgewertet hat und Sie eine Teilanwendung anstelle eines Lambdas verwenden.

TLDR: Durch das Speichern von Berechnungen in einer Liste wird jedes Element der Liste einmal ausgewertet, daher wird jede Fibonnacci-Zahl im gesamten Programm genau einmal berechnet.

Visualisierung:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Sie können also sehen, dass die Auswertung THUNK_4viel schneller ist, da die Unterausdrücke bereits ausgewertet wurden.

Daniel Gratzer
quelle
Können Sie ein Beispiel dafür geben, wie sich die Werte in der Liste für eine kurze Sequenz verhalten? Ich denke, es kann zu der Visualisierung beitragen, wie es funktionieren soll ... Und während es stimmt, dass wenn ich memo_fibzweimal mit dem gleichen Wert aufrufe, das zweite Mal sofort, aber wenn ich es mit einem Wert 1 höher aufrufe, ist es Es dauert immer noch ewig zu bewerten (wie sagen wir von 30 bis 31)
Electric Coffee
@ElectricCoffee Hinzugefügt
Daniel Gratzer
@ElectricCoffee Nein, das wird es nicht memo_fib 29und memo_fib 30es wird bereits ausgewertet. Es wird genau so lange dauern, bis diese beiden Zahlen addiert werden. :) Sobald etwas evaluiert wurde, bleibt es evaluiert.
Daniel Gratzer
1
@ElectricCoffee Ihre Rekursion muss durch die Liste gehen, sonst erhalten Sie keine Leistung
Daniel Gratzer
2
@ElectricCoffee Ja. Aber das 31. Element der Liste verwendet keine früheren Berechnungen, Sie merken sich ja, aber auf ziemlich nutzlose Weise. Wiederholte Berechnungen werden nicht zweimal berechnet, aber Sie haben immer noch eine Baumrekursion für jeden neuen Wert, der ist sehr, sehr langsam
Daniel Gratzer
1

Der Punkt, an dem Sie sich merken müssen, ist, niemals dieselbe Funktion zweimal zu berechnen - dies ist äußerst nützlich, um Berechnungen zu beschleunigen, die rein funktional sind, dh ohne Nebenwirkungen, da bei diesen der Prozess vollständig automatisiert werden kann, ohne die Korrektheit zu beeinträchtigen. Dies ist insbesondere dann erforderlich , für Funktionen wie fibo, die zu führen Baumrekursion , das heißt exponentiellen Aufwand, wenn naiv implementiert. (Dies ist ein Grund, warum die Fibonacci-Zahlen eigentlich ein sehr schlechtes Beispiel für das Unterrichten von Rekursion sind - fast alle Demo-Implementierungen, die Sie in Tutorials oder Büchern finden, sind für große Eingabewerte unbrauchbar.)

Wenn Sie den Ablauf der Ausführung verfolgen, werden Sie feststellen, dass im zweiten Fall der Wert für fib ximmer verfügbar fib x+1ist, wenn er ausgeführt wird, und das Laufzeitsystem kann ihn einfach aus dem Speicher lesen und nicht über einen anderen rekursiven Aufruf, während der Die erste Lösung versucht, die größere Lösung zu berechnen, bevor die Ergebnisse für kleinere Werte verfügbar sind. Dies liegt letztendlich daran, dass der Iterator [0..n]von links nach rechts ausgewertet wird und daher mit beginnt 0, während die Rekursion im ersten Beispiel mit beginnt nund erst dann nachfragt n-1. Dies führt zu den vielen, vielen unnötigen doppelten Funktionsaufrufen.

Kilian Foth
quelle
oh, ich verstehe den Sinn davon, ich habe einfach nicht verstanden, wie es funktioniert, wie aus dem Code hervorgeht, dass, wenn Sie memorized_fib 20zum Beispiel schreiben , Sie tatsächlich nur schreiben map fib [0..] !! 20, es immer noch das berechnen müsste gesamter Nummernkreis bis 20, oder fehlt mir hier etwas?
Electric Coffee
1
Ja, aber nur einmal für jede Nummer. Die naive Implementierung kalkuliert fib 2so oft, dass sich Ihr Kopf dreht - schreiben Sie den Aufrufbaum für einen kleinen Wert wie auf n==5. Sie werden das Auswendiglernen nie wieder vergessen, wenn Sie gesehen haben, was es Sie rettet.
Kilian Foth
@ElectricCoffee: Ja, es wird ein Wert von 1 bis 20 berechnet. Sie profitieren von diesem Anruf nicht. Versuchen Sie nun, fib 21 zu berechnen, und Sie werden feststellen, dass Sie anstelle von 1-21 nur 21 berechnen können, da Sie bereits 1-20 berechnet haben und es nicht erneut tun müssen.
Phoshi
Ich versuche, den Anrufbaum für aufzuschreiben n = 5, und ich bin gerade an dem Punkt angelangt, an dem ich n == 3bisher so gut war, aber vielleicht ist es nur mein zwingender Verstand, dies zu denken, aber bedeutet das nicht nur, dass n == 3man es einfach bekommt map fib [0..]!!3? was geht dann in den fib nzweig des programms ... wo genau bekomme ich die vorteile von vorberechneten daten?
Electric Coffee
1
Nein, memoized_fibist in Ordnung. Es ist das slow_fib, was dich zum Weinen bringt, wenn du es verfolgst.
Kilian Foth