Ich spielte mit Definitionen herum, um das Bewertungsmodell besser zu verstehen, und schrieb zwei für die Länge einer Liste.
Die naive Definition:
%Vor%Die strikte (und tail-rekursive) Definition:
%Vor% len [1..10000000] dauert etwa 5-6 Sekunden.
slen [1..10000000] 0 dauert etwa 3-4 Sekunden.
Ich bin neugierig warum. Bevor ich die Performances überprüfte, war ich mir sicher, dass sie ungefähr dasselbe tun würden, weil len höchstens einen Thunk haben sollte, der am besten bewertet werden kann. Zu Demonstrationszwecken:
Und
%Vor% Was macht slen merklich schneller?
P.S. Ich habe auch eine tail-rekursive Lazy-Funktion (genau wie slen , aber faul) als Versuch geschrieben, näher auf den Grund einzugehen - vielleicht weil es tail-rekursiv war -, aber es hat ungefähr die gleiche Wirkung wie die naive Definition .
Der letzte Schritt von len ist nicht O (1). Es ist O (n), n Zahlen zusammenzufassen. len verwendet auch O (n) Speicher, während slen O (1) Speicher verwendet.
Der Grund für die Verwendung von O (n) Speicher ist, dass jeder Thunk etwas Speicher verbraucht. Also wenn du so etwas hast:
%Vor% Es gibt fünf unbewertete Thunks (einschließlich len [] )
In GHCi können wir dieses thunk-Verhalten mit dem Befehl :sprint ein wenig einfacher untersuchen. Der Befehl :sprint gibt den angegebenen Wert aus, ohne das Auswerten von Thunks zu erzwingen (Sie können mehr von :help erfahren). Ich werde Conseys ( (:) ) verwenden, da wir jeden einzelnen Thunk besser einzeln auswerten können, aber das Prinzip ist das gleiche.
Nicht bewertete Thunks werden durch _ repräsentiert und Sie können sehen, dass in der ursprünglichen ys 4 Thunks ineinander geschachtelt sind, eine für jeden Teil der Liste (einschließlich [] ).
Es gibt keinen guten Weg, den ich in Int sehen kann, weil seine Auswertung mehr alles oder nichts ist, aber es baut immer noch ein verschachteltes Thunk auf die gleiche Weise auf. Wenn Sie es so sehen könnten, würde seine Bewertung in etwa so aussehen:
David Youngs Antwort gibt die richtige Erklärung für den Unterschied in der Bewertungsreihenfolge. Sie sollten über Haskell-Evaluierung in der Art denken, die er skizziert.
Lassen Sie mich Ihnen zeigen, wie Sie den Unterschied im Kern sehen können. Ich denke, es ist bei Optimierungen tatsächlich sichtbarer, weil die Auswertung als explizite case -Anweisung endet. Wenn Sie noch nie zuvor mit Core gespielt haben, lesen Sie die kanonische SO-Frage zum Thema: Reading GHC Core .
Generieren Sie die Kernausgabe mit ghc -O2 -ddump-simpl -dsuppress-all -ddump-to-file SO27392665.hs . Sie werden sehen, dass GHC sowohl len als auch slen in eine rekursive "worker" -Funktion, $wlen oder $wslen , und eine nichtrekursive "wrapper" -Funktion aufteilt. Da die meiste Zeit in den rekursiven "Arbeitern" verbracht wird, konzentrieren Sie sich auf sie:
Sie können sehen, dass $wslen nur ein case hat, während $wlen zwei hat. Wenn Sie sich Davids Antwort ansehen, können Sie verfolgen, was in $wlen passiert: Sie führt ihre Fallanalyse für den Konstruktor der äußersten Liste durch ( [] / : ) und führt den rekursiven Aufruf zu $wlen xs_as0 (dh len xs ), die es auch case s, dh erzwingt das angesammelte Thunk.
In $wslen hingegen gibt es nur die eine case -Anweisung. Im rekursiven Zweig gibt es einfach einen ungeboxten Zusatz, (+# ww_sP0 1) , der keinen Thunk erzeugt.
(Hinweis: In einer früheren Version dieser Antwort wurde angegeben, dass% GHC% -O nicht aber $wslen auf nicht gehackte $wlen s spezialisieren könnte. Dies ist nicht der Fall.)
Tags und Links haskell ghc performance evaluation lazy-evaluation