foldl ist Schwanz rekursiv, so wie kommt foldr läuft schneller als foldl?

StackOverflow https://stackoverflow.com/questions/3429634

Frage

wollte ich Test foldl vs foldr. Von dem, was ich gesehen habe Sie foldl über foldr verwenden sollten, wann immer Sie können bis zum Schwanz reccursion Optimierung durch.

Das macht Sinn. Doch nach diesem Test ausführt Ich bin verwirrt:

foldr (nimmt 0.057s, wenn die Zeit-Befehl): 

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (nimmt 0.089s, wenn die Zeit-Befehl): 

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

Es ist klar, dass dieses Beispiel ist trivial, aber ich bin verwirrt, warum foldr foldl schlägt. Sollte dies nicht ein klarer Fall, wo foldl gewinnt sein?

War es hilfreich?

Lösung

Willkommen in der Welt von lazy evaluation.

Wenn man darüber nachdenkt im Hinblick auf die strenge Bewertung, foldl sieht „gut“ und foldr sieht „schlecht“, weil foldl ist Schwanz rekursiv, aber foldr würde einen Turm im Stapel zu bauen, so dass es zunächst das letzte Element verarbeiten kann .

Allerdings stellt faul Auswertung der Tabellen. Nehmen wir zum Beispiel die Definition der Kartenfunktion: 

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Das wäre nicht so gut, wenn Haskell strenge Bewertung verwendet, da sie den Schwanz zuerst berechnen müsste, dann schreibe das Element (für alle Elemente in der Liste). Der einzige Weg, um es effizient die Elemente in umgekehrter Reihenfolge zu bauen zu tun wäre, so scheint es.

Doch dank Haskells lazy evaluation, diese Map-Funktion ist tatsächlich effizient. Listen in Haskell können als Generatoren gedacht werden, und diese Map-Funktion generiert sein erstes Element von f auf das erste Elemente der Eingabeliste anwenden. Wenn es ein zweites Element braucht, tut es nur die gleiche Sache wieder (ohne zusätzlichen Raum verwendet wird).

Es stellt sich heraus, dass map kann in Bezug auf foldr beschrieben werden: 

map f xs = foldr (\x ys -> f x : ys) [] xs

Es ist schwer, indem man es zu sagen, aber faul Auswertung Tritte in, weil foldr geben kann f erstes Argument sofort: 

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

Da die f durch map definiert ist, kann das erste Element der Ergebnisliste zurückkehrt nur den ersten Parameter verwendet, kann die Falte träge in konstantem Raum betrieben werden.

Nun lazy evaluation tut beißen zurück. Zum Beispiel versuchen laufende Summe [1..1000000]. Es ergibt sich ein Stapelüberlauf. Warum sollte es? Es sollte bewerten, nur von links nach rechts, nicht wahr?

Schauen wir uns an, wie Haskell wertet sie aus: 

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

Haskell ist zu faul, um die Ergänzungen durchzuführen, wie es geht. Stattdessen endet es mit einem Turm von unevaluierten Thunks up, die eine Reihe gezwungen werden müssen, um zu bekommen. Der Stapelüberlauf tritt bei dieser Bewertung, da sie tief Rekursion hat alle Thunks zu bewerten.

Glücklicherweise gibt es eine spezielle Funktion in Data.List genannt foldl', die streng arbeitet. foldl' (+) 0 [1..1000000] nicht Stack-Überlauf. (Anmerkung: Ich habe versucht, foldl mit foldl' in Ihrem Test zu ersetzen, aber es machte es tatsächlich laufen langsamer.)

Andere Tipps

EDIT:. Bei wieder auf dieses Problem suchen, denke ich, alle aktuellen Erklärungen etwas nicht ausreichen, damit ich eine längere Erklärung geschrieben habe

Der Unterschied liegt darin, wie foldl und foldr gelten ihre Reduktionsfunktion. Mit Blick auf die foldr Fall, können wir es erweitern, wie 

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

Diese Liste wird von sum verarbeitet, die es verbraucht wie folgt: 

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

Ich habe die Details der Liste Verkettung weggelassen, aber das ist, wie die Reduktion verläuft. Der wichtigste Teil ist, dass alles in Ordnung Liste Querungen zu minimieren verarbeitet wird. Die foldr überquert nur die Liste einmal, die Verkettungen erfordern keine fortlaufende Liste Querungen und sum verbraucht schließlich die Liste in einem Durchgang. Entscheidend ist, ist der Kopf der Liste von foldr sofort sum zur Verfügung, so sum kann beginnen sofort mit der Arbeit und Werte können gc'd werden, wie sie erzeugt werden. Mit Fusion-Frameworks wie vector, auch die Zwischenlisten wahrscheinlich fusioniert entfernt werden.

Vergleichen Sie das mit der foldl Funktion: 

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

Beachten Sie, dass jetzt der Kopf der Liste nicht verfügbar ist, bis foldl beendet hat. Dies bedeutet, dass die gesamte Liste muss vor sum im Speicher aufgebaut werden kann, um Arbeit beginnen. Das ist viel weniger effizient insgesamt. Laufen die beiden Versionen mit +RTS -s zeigt miserable Garbage Collection Leistung aus der foldl Version.

Dies ist auch ein Fall, in dem foldl' wird nicht helfen. Das zugegebene Strikt von foldl' ändert nicht die Art und Weise der Zwischenliste erstellt wird. Der Kopf der Liste bleibt nicht verfügbar, bis foldl‘beendet ist, so noch das Ergebnis langsamer sein wird als mit foldr.

Ich verwende die folgende Regel die beste Wahl von fold bestimmen

  • Für Falten, die ein sind Reduktion , sondern foldl' (zum Beispiel wird dies das sein nur / Abschluss Traversal)
  • Sonst Verwendung foldr.
  • Verwenden Sie foldl nicht.

In den meisten Fällen foldr ist die beste Falzfunktion, da die Durchlaufrichtung für faule Auswertung von Listen optimal ist. Es ist auch die einzige in der Lage unendliche Listen zu verarbeiten. Die zusätzliche Strenge foldl' kann es in einigen Fällen schneller machen, aber dies ist davon abhängig, wie Sie diese Struktur verwenden werden und wie faul ist.

Ich glaube nicht, dass jemand gesagt, tatsächlich die richtige Antwort auf diese ein noch, es sei denn ich etwas fehle (was wohl wahr sein kann und mit downvotes begrüßt).

Ich denke, die größte anders in diesem Fall ist, dass foldr die Liste wie folgt erstellt:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

Während foldl baut die Liste wie folgt aus:

((([0] ++ [1]) ++ [2]) ++ ...) ++ [999888]) ++ [999999]) ++ [1000000]

Der Unterschied in der subtilen, aber feststellen, dass in der foldr Version ++ immer nur ein Listenelement als linkes Argument. Mit der foldl Version gibt es bis zu 999.999 Elemente in der linken Argument der ++ (im Durchschnitt rund 500000), aber nur ein Element in der rechten Argument.

Allerdings ++ braucht Zeit proportional zur Größe des linken Argument, wie es aber die gesamte linke Argument Liste am Ende auszusehen hat und repoint dann das letzte Element auf das erste Element des rechten Arguments (am besten, vielleicht es braucht eigentlich eine Kopie zu tun). Die richtige Argumentliste ist unverändert, so dass es keine Rolle, wie groß es ist.

Das ist, warum die foldl Version viel langsamer ist. Es hat nichts mit Faulheit meiner Meinung nach zu tun.

Das Problem ist, dass Endrekursion Optimierung eine Speicheroptimierung ist keine Ausführungszeit-Optimierung!

Endrekursion Optimierung vermeidet die Notwendigkeit, Werte für jeden rekursiven Aufruf zu erinnern.

Also, foldl ist in der Tat "gut" und foldr ist "schlecht".

Zum Beispiel, wenn man bedenkt, die Definitionen von foldr und foldl: 

foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)

Das ist, wie der Ausdruck "foldl (+) 0 [1,2,3]" ausgewertet: 

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

Beachten Sie, dass foldl erinnert sich nicht an die Werte 0, 1, 2 ..., aber die ganze Ausdruck übergeben (((0 + 1) + 2) + 3) als Argument träge und sie wertet es nicht, bis die letzte Bewertung der foldl, wo sie den Basisfall erreicht und gibt den Wert als zweiten Parameter (z) übergeben Weicht noch nicht ausgewertet wird.

Auf der anderen Seite, das ist, wie foldr funktioniert: 

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

Der wichtige Unterschied besteht darin, dass dort, wo foldl den gesamten Ausdruck in dem letzten Aufruf auswertet, die Notwendigkeit vermieden wird, zurückzukommen erinnerte Werte zu erreichen, kein foldr. foldr erinnere mich an eine ganze Zahl für jeden Anruf und führt eine Addition in jedem Aufruf.

ist wichtig zu bedenken, dass foldr und foldl sind nicht immer Äquivalente. Zum Beispiel versuchen, diese Ausdrücke in Umarmungen zu berechnen: 

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

foldr und foldl gleichwertig sind nur unter bestimmten Bedingungen beschrieben hier

(sorry für mein schlechtes Englisch)

Für ein, muss die [0.. 100000] Liste sofort erweitert werden, so dass foldr mit dem letzten Element beginnen. Dann wird, wie es Dinge zusammen faltet, die Zwischenergebnisse sind 

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

Weil niemand erlaubt ist, diese Liste Wert zu ändern (Haskell ist eine reine funktionale Sprache), ist der Compiler frei, den Wert wieder zu verwenden. Die Zwischenwerte, wie [99999, 100000] können auch anstelle von separaten Listen einfach Zeiger in die erweiterten [0.. 100000] Liste sein.

b, Blick auf den Zwischenwert: 

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

Jede dieser Zwischenlisten kann nicht wiederverwendet werden, denn wenn man das Ende der Liste zu ändern, dann haben Sie keine anderen Werte diesen Punkt, um es geändert. So haben Sie eine Reihe von zusätzlichen Listen erstellen, von Zeit zu bauen im Speicher nehmen. Also in diesem Fall verbringen Sie viel mehr Zeit, Aufteilung und in diesen Listen füllen die Zwischenwerte sind.

Da Sie nur eine Kopie der Liste zu machen, eine läuft schneller, weil es beginnt, indem die vollständige Liste zu erweitern und dann hält nur einen Zeiger von der Rückseite der Liste zu bewegen nach vorne.

Weder foldl noch foldr ist Schwanz optimiert. Es ist nur foldl'.

Aber in Ihrem Fall mit ++ mit foldl' ist nicht sinnvoll, da aufeinanderfolgende Auswertung von ++ wachsenden Speicher durchlaufen wird verursacht immer wieder.

Nun, lassen Sie mich umschreiben Ihre Funktionen in einer Weise, dass Unterschied offensichtlich sein sollte - 

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

Sie sehen, dass b ist komplexer als ein. Wenn Sie mögen, Schritt präzise a braucht man Reduktion auf seinen Wert berechnet werden, aber b brauchen zwei. Das macht die Zeitdifferenz Sie messen, zweimal im zweiten Beispiel, wie viele Reduzierungen durchgeführt werden müssen.

// edit:. Aber die Zeit Komplexität ist das gleiche, so würde ich nicht darüber viel Mühe

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top