foldl è ricorsiva di coda, così come mai foldr corre più veloce di foldl?
https://stackoverflow.com/questions/3429634
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
ho voluto prova foldl vs foldr. Da quello che ho visto si dovrebbe usare foldl oltre foldr quando mai si può grazie all'ottimizzazione coda reccursion.
Questo ha un senso. Tuttavia, dopo l'esecuzione di questo test sono confuso:
foldr (prende 0.057s quando si utilizza il comando di tempo):
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
foldl (prende 0.089s quando si utilizza il comando di tempo):
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
E 'chiaro che questo esempio è banale, ma sono confuso sul motivo per cui foldr sta battendo foldl. Non dovrebbe essere questo un chiaro caso in cui vince foldl?
Soluzione
Benvenuti nel mondo di valutazione pigra.
Quando si pensa a questo proposito, in termini di rigorosa valutazione, sembra foldl "buono" e sguardi foldr "cattivi", perché foldl è ricorsiva di coda, ma foldr avrebbe dovuto costruire una torre nella pila in modo che possa elaborare prima l'ultimo elemento .
Tuttavia, la valutazione pigra ribalta la situazione. Prendiamo, ad esempio, la definizione della funzione di mappa:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Questo non sarebbe troppo bello se Haskell utilizzato la valutazione rigorosa, dal momento che avrebbe dovuto calcolare la coda, poi anteporre la voce (per tutti gli elementi della lista). L'unico modo per farlo in modo efficace sarebbe quello di costruire gli elementi in ordine inverso, a quanto pare.
Tuttavia, grazie alla valutazione pigra di Haskell, questa funzione mappa è in realtà efficiente. Elenchi a Haskell possono essere pensati come generatori, e questa funzione cartina genera la prima voce applicando f al primo elemento della lista in ingresso. Quando si ha bisogno di una seconda voce, semplicemente fa di nuovo la stessa cosa (senza utilizzare spazio extra).
Si scopre che map può essere descritto in termini di foldr:
map f xs = foldr (\x ys -> f x : ys) [] xs
E 'difficile da dire, cercando in essa, ma pigri calci di valutazione a causa foldr può dare f suo primo argomento subito:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Poiché il f definito da map può restituire il primo elemento della lista risultato utilizzando unicamente il primo parametro, la piega può operare pigramente nello spazio costante.
Ora, la valutazione pigra fa mordere di nuovo. Per esempio, provare a eseguire somma [1..1000000]. Si produce un overflow dello stack. Perché dovrebbe? Si deve solo valutare da sinistra a destra, giusto?
Diamo un'occhiata a come Haskell lo valuta:
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 è troppo pigro per eseguire le aggiunte come va. Invece, si finisce con una torre di thunk non valutate che devono essere costretti ad ottenere un numero. L'overflow dello stack si verifica durante questa valutazione, dal momento che ha la ricorsione profondamente per valutare tutte le thunk.
Per fortuna, c'è una funzione speciale in Data.List chiamato foldl' che opera rigorosamente. foldl' (+) 0 [1..1000000] non impilare troppo pieno. (Nota: Ho provato a sostituire foldl con foldl' nel test, ma in realtà ha fatto correre più lento.)
Altri suggerimenti
EDIT:. Al momento guardando a questo problema ancora una volta, credo che tutte le spiegazioni correnti sono un po 'insufficienti così ho scritto una spiegazione più
La differenza sta nel modo in cui foldl e foldr applicano la loro funzione di riduzione. Guardando il caso foldr, possiamo espandere come
foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...
Questo elenco viene elaborato da sum, che consuma come segue:
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])
...
ho lasciato fuori i dettagli della concatenazione, ma questo è come la riduzione procede. La parte importante è che tutto ciò che viene processato al fine di minimizzare lista attraversamenti. L'foldr attraversa solo l'elenco una volta, le concatenazioni non necessitano di attraversamenti elenco continuo, e, infine, sum consuma la lista in una sola passata. Criticamente, la testa della lista è disponibile da foldr immediatamente sum, così sum può iniziare a lavorare immediatamente e valori possono essere gc'd appena vengono generati. Con quadri di fusione, come vector, anche le liste intermedie saranno probabilmente fuse via.
Contrasto questo per la funzione foldl:
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]
...
Si noti che ora il capo della lista non è disponibile fino foldl è terminata. Ciò significa che l'intero elenco deve essere costruito in memoria prima sum possono cominciare a lavorare. Questo è molto meno efficiente nel complesso. Esecuzione di due versioni con spettacoli +RTS -s miserabile prestazioni raccolta dei rifiuti dalla versione foldl.
Questo è anche un caso in cui foldl' non aiuterà. Il rigore aggiunto di foldl' non cambia il modo in cui viene creata la lista intermedia. Il capo della lista rimane disponibile fino foldl' ha finito, quindi il risultato sarà ancora più lento di quello con foldr.
Io uso la seguente regola per determinare la migliore scelta di fold
- Per pieghe che sono un riduzione , uso
foldl'(ad esempio questo sarà l'unico / attraversamento finale) - In caso contrario, l'uso
foldr. - Non utilizzare
foldl.
Nella maggior parte dei casi foldr è la migliore funzione di piegatura perché la direzione di attraversamento è ottimale per la valutazione pigra delle liste. E 'anche l'unico in grado di elaborare infinite liste. Il rigore supplementare di foldl' può renderlo più veloce, in alcuni casi, ma questo dipende da come userete quella struttura e come pigri sia.
Non credo che nessuno in realtà ha detto che la vera risposta su questo ancora, a meno che non mi manca qualcosa (che può anche essere vero e accolto con downvotes).
Credo che il più grande differente in questo caso è che foldr costruisce la lista come questa:
[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))
considerando che foldl crea l'elenco in questo modo:
((([0] ++ [1]) ++ [2]) ++ ...) ++ [999.888]) ++ [999999]) ++ [1000000]
La differenza sottile, a meno di notare che nella versione foldr ++ ha sempre un solo elemento della lista come argomento a sinistra. Con la versione foldl, ci sono fino a 999999 elementi in argomento a sinistra di ++ (in media circa 500000), ma solo un elemento in all'argomento a destra.
Tuttavia, ++ richiede tempo proporzionale alla dimensione dell'argomento sinistra, come si deve guardare se l'intera lista degli argomenti di sinistra alla fine e poi repoint che ultimo elemento al primo elemento dell'argomento a destra (nella migliore delle ipotesi, forse in realtà ha bisogno di fare una copia). La lista degli argomenti di destra è invariata, quindi non importa quanto grande sia.
Questo è il motivo per cui la versione foldl è molto più lento. Non ha niente a che fare con la pigrizia a mio parere.
Il problema è che l'ottimizzazione ricorsione in coda è un'ottimizzazione della memoria, non un ottimizzazione dei tempi di esecuzione!
ottimizzazione ricorsione in coda evita la necessità di ricordare i valori per ogni chiamata ricorsiva.
Quindi, foldl è infatti "buono" e foldr è "cattivo".
Per esempio, considerando le definizioni di foldr e 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)
E 'così che l'espressione "foldl (+) 0 [1,2,3]" viene valutata:
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
Si noti che foldl non ricorda i valori 0, 1, 2 ..., ma passa l'intera espressione (((0 + 1) 2) 3) come argomento pigramente e non lo valuta fino a quando il ultima valutazione di foldl, dove raggiunge il caso base e restituisce il valore passato come parametro secondo (z) goduto non è ancora valutata.
D'altra parte, è così che funziona foldr:
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
La differenza importante è che dove foldl valuta l'intera espressione nella ultima chiamata, evitando la necessità di tornare a raggiungere valori ricordati, foldr no. foldr ricordare un intero per ogni chiamata ed esegue un'addizione in ogni chiamata.
È importante tenere a mente che foldr e foldl non sono sempre equivalenti. Per esempio, provate a calcolare questo espressioni in abbracci:
foldr (&&) True (False:(repeat True))
foldl (&&) True (False:(repeat True))
foldr e foldl sono equivalenti solo in determinate condizioni descritte qui
(dispiace per il mio cattivo inglese)
Per un, la lista [0.. 100000] deve essere ampliato subito in modo che foldr può iniziare con l'ultimo elemento. Poi, come si piega insieme le cose, i risultati intermedi sono
[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list
Perché nessuno è permesso di modificare questo valore lista (Haskell è un linguaggio funzionale puro), il compilatore è libero di riutilizzare il valore. I valori intermedi, come [99999, 100000] può anche essere semplicemente puntatori nella lista [0.. 100000] espansa invece di liste separate.
Per b, sguardo ai valori intermedi:
[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]
Ciascuna di tali elenchi intermedi non può essere riutilizzato, perché se si modifica la fine della lista, allora hai cambiato tutti gli altri valori che punto ad esso. Quindi, si sta creando un gruppo di liste extra che vorrà tempo per costruire in memoria. Quindi, in questo caso si spende molto più tempo alla ripartizione e compilando in questi elenchi che sono i valori intermedi.
Dal momento che si sta solo facendo una copia della lista, a corre più veloce perché inizia espandendo l'elenco completo e poi basta continua a muoversi un puntatore dalla parte posteriore della lista alla parte anteriore.
Né foldl né foldr è ottimizzato coda. E 'solo foldl'.
Ma nel tuo caso utilizzando ++ con foldl' non è una buona idea, perché la valutazione successiva ++ causerà attraversare ancora e ancora in crescita accumulatore.
Bene, mi permetta di riscrivere le funzioni in un modo che differenza dovrebbe essere ovvio -
a :: a -> [a] -> [a]
a = (:)
b :: [b] -> b -> [b]
b = flip (:)
Si vede che B è più complessa di una. Se si vuole essere precisi a ha bisogno di una fase di riduzione per il valore da calcolare, ma b ha bisogno di due. Che fa la differenza di tempo si sta misurando, in secondo esempio il doppio devono essere eseguite molto riduzioni.
// edit:. Ma il tempo della complessità è lo stesso, in modo da non preoccuparsi molto
