scala - spark - foldLeft v. foldRight-¿Importa?
foldleft spark (5)
Anteriormente, Nicolas Rinaudo respondió mi pregunta sobre el Plegado de la Lista de Scala ¿Siempre utilizando foldLeft?
Al estudiar Haskell actualmente, entiendo que foldRight
debe preferirse a foldLeft
en los casos en que ::
(prepend) se puede usar sobre ++
(append).
El motivo, según entiendo, es el rendimiento: el primero ocurre en O(1)
, es decir, se agrega un elemento al frente, el tiempo constante. Mientras que el último requiere O(N)
, es decir, pasar por la lista completa y agregar un elemento.
En Scala, dado que foldLeft
se implementa en términos de foldRight
, ¿el beneficio de usar :+
sobre ++
con foldRight
importa incluso desde que foldRight
se invierte, y luego foldLeft''d
?
Como ejemplo, considere esta simple operación de fold..
para simplemente devolver los elementos de una lista en orden.
foldLeft
pliega sobre cada elemento, agregando cada elemento a la lista a través de :+
.
scala> List("foo", "bar").foldLeft(List[String]()) {
(acc, elem) => acc :+ elem }
res9: List[String] = List(foo, bar)
foldRight
realiza un operador foldLeft with ::
en cada elemento, pero luego invierte.
scala> List("foo", "bar").foldRight(List[String]()) {
(elem, acc) => elem :: acc }
res10: List[String] = List(foo, bar)
En realidad, ¿importa en Scala qué foldLeft
o foldRight
usar dado que foldRight
usa foldRight
?
La respuesta de @Rein Henrichs es irrelevante para Scala, porque la implementación de foldLeft
y foldRight
por parte de Scala es completamente diferente (para empezar, Scala tiene una evaluación entusiasta).
foldLeft
y foldRight
tienen muy poco que ver con el rendimiento de su programa. Ambos son (liberalmente hablando) O (n * c_f) donde c_f es la complejidad de una llamada a la función f
que se da. foldRight
es más lento por un factor constante debido al reverse
adicional, sin embargo.
Entonces, el factor real que diferencia uno de otro es la complejidad de la función anónima que usted brinda. A veces, es más fácil escribir una función eficiente diseñada para funcionar con foldLeft
, y algunas veces para foldRight
. En su ejemplo, la versión de foldRight
es la mejor, porque la función anónima que le da a foldRight
es O (1). Por el contrario, la función anónima que le das a foldLeft
es O (n) en sí (amortizada, que es lo que importa aquí), porque acc
sigue creciendo de 0 a n-1, y añadiendo a una lista de n elementos es O (n )
Por lo tanto, realmente importa si elige foldLeft
o foldRight
, pero no debido a estas funciones en sí mismas, sino debido a las funciones anónimas que se les otorgan. Si ambos son equivalentes, elija foldLeft
por defecto.
No soy un experto en Scala, pero en Haskell, una de las características diferenciadoras más importantes entre foldl''
(que realmente debería ser el doblez predeterminado) y foldr
es que foldr
funcionará en estructuras de datos infinitas, donde foldl''
colgará indefinidamente.
Para entender por qué esto es así, recomiendo visitar foldl.com y foldr.com , expandir las evaluaciones un par de veces y reconstruir el árbol de llamadas. Verás rápidamente dónde foldr
es apropiado versus foldl''
.
Puedo proporcionar una respuesta para Haskell, pero dudo que sea relevante para Scala:
Comencemos con la fuente para ambos,
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Ahora, veamos dónde aparece la llamada recursiva a foldl o foldr en el lado derecho. Para foldl, es más externo. Para foldr, está dentro de la aplicación de f. Esto tiene un par de implicaciones importantes:
Si
f
es un constructor de datos, ese constructor de datos será el más a la izquierda, el más externo con foldr. Esto significa que foldr implementa la recursión protegida , de modo que lo siguiente es posible:> take 5 . foldr (:) [] $ [1..] [1,2,3,4]
Esto significa que, por ejemplo, foldr puede ser un buen productor y un buen consumidor para la fusión de atajo . (Sí,
foldr (:) []
es un morfismo de identidad para listas).Esto no es posible con foldl porque el constructor estará dentro de la llamada recursiva a foldl y no se puede emparejar el patrón.
Por el contrario, debido a que la llamada recursiva a foldl está en la posición extrema más a la izquierda, se reducirá mediante evaluación diferida y no ocupará espacio en la pila de coincidencia de patrones. Combinado con la anotación de rigor adecuada (por ejemplo,
foldl''
), esto permite que funciones comosum
olength
ejecuten en espacio constante.
Para más información sobre esto, vea Lazy Evaluation of Haskell .
De hecho, importa si usa foldLeft
o foldRight
en Scala, al menos con listas, al menos en la implementación predeterminada. Sin embargo, creo que esta respuesta no es válida para bibliotecas como Scalaz.
Si observa el código fuente de foldLeft
y foldRight
para LinearSeqOptimized , verá que:
-
foldLeft
se implementa con un bucle y variables mutables locales, y se ajusta en un marco de pila. -
foldRight
es recursivo, pero no recursivo de cola, y por lo tanto consume un marco de pila por elemento en la lista.
foldLeft
es seguro, mientras que foldRight
puede foldRight
desbordamiento para listas largas.
Editar Para completar mi respuesta, ya que solo hace referencia a una parte de su pregunta: también importa cuál use según lo que pretenda hacer.
Para tomar su ejemplo, lo que considero la solución óptima es usar foldLeft
, foldLeft
resultados a su acumulador, e reverse
el resultado.
De esta manera:
- toda la operación es O (n)
- no desbordará la pila, independientemente del tamaño de la lista
Esto es esencialmente lo que pensaste que estabas haciendo con foldRight
al asumir que se implementó en términos de foldLeft
.
Si usa foldRight
, obtendrá una implementación un poco más rápida (bueno, ligeramente ... el doble de rápido, realmente, pero aún O (n)) a costa de la seguridad.
Se podría argumentar que, si sabes que tus listas serán lo suficientemente pequeñas, no hay problemas de seguridad y puedes usar foldRight
. Siento, pero eso es solo una opinión, que si tus listas son lo suficientemente pequeñas para que no tengas que preocuparte por tu stack, son lo suficientemente pequeñas para que no tengas que preocuparte por el rendimiento.
Depende, considere lo siguiente:
scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)
scala> l.foldLeft(List.empty[Int]) { (acc, ele) => ele :: acc }
res0: List[Int] = List(3, 2, 1)
scala> l.foldRight(List.empty[Int]) { (ele, acc) => ele :: acc }
res1: List[Int] = List(1, 2, 3)
Como puede ver, foldLeft
atraviesa la lista desde la head
hasta el último elemento. foldRight
por otro lado, lo atraviesa desde el último elemento hasta la head
.
Si usa plegado para la agregación, no debería haber diferencia:
scala> l.foldLeft(0) { (acc, ele) => ele + acc }
res2: Int = 6
scala> l.foldRight(0) { (ele, acc) => ele + acc }
res3: Int = 6