Diferencia entre reducir y foldLeft / fold en programación funcional (particularmente Scala y Scala APIs)?
¿Por qué Scala y frameworks como Spark y Scalding tienen reduce y foldLeft? Entonces, ¿cuál es la diferencia entre reduce y fold?
4 answers
Reducir vs foldLeft
Una gran diferencia, no mencionada en ninguna otra respuesta de stackoverflow relacionada con este tema claramente, es que reduce se debe dar un monoide conmutativo, es decir, una operación que es tanto conmutativa como asociativa. Esto significa que la operación puede ser paralelizada.
Esta distinción es muy importante para Big Data / MPP / computación distribuida, y toda la razón por la que reduce incluso existe. La colección se puede cortar y el reduce puede operar en cada fragmento, entonces el reduce puede operar en los resultados de cada fragmento - de hecho, el nivel de fragmentación no tiene por qué detener un nivel profundo. Podríamos cortar cada trozo también. Esta es la razón por la que sumar enteros en una lista es O(log N) si se le da un número infinito de CPU.
Si solo miras las firmas no hay razón para que reduce exista porque puedes lograr todo lo que puedas con reduce con un foldLeft. La funcionalidad de foldLeft es mayor que la funcionalidad de reduce.
Pero no se puede paralelizar a foldLeft, por lo que su tiempo de ejecución es siempre O(N) (incluso si se alimenta un monoide conmutativo). Esto se debe a que se asume que la operación es no un monoide conmutativo y, por lo tanto, el valor acumulado se calculará mediante una serie de agregaciones secuenciales.
foldLeft no asume conmutatividad ni asociatividad. Es la asociatividad que da la capacidad de cortar la colección, y es la conmutatividad que hace que la acumulación sea fácil porque el orden no es importante (por lo que no importa qué orden agregar cada uno de los resultados de cada uno de los trozos). Estrictamente hablando, la conmutatividad no es necesaria para la paralelización, por ejemplo, los algoritmos de ordenación distribuidos, solo hace que la lógica sea más fácil porque no necesita dar un orden a sus trozos.
Si echas un vistazo a la documentación de Spark para reduce dice específicamente "... binario conmutativo y asociativo operador"
Http://spark.apache.org/docs/1.0.0/api/scala/index.html#org.apache.spark.rdd.RDD
Aquí está la prueba de que reduce NO es solo un caso especial de foldLeft
scala> val intParList: ParSeq[Int] = (1 to 100000).map(_ => scala.util.Random.nextInt()).par
scala> timeMany(1000, intParList.reduce(_ + _))
Took 462.395867 milli seconds
scala> timeMany(1000, intParList.foldLeft(0)(_ + _))
Took 2589.363031 milli seconds
Reducir vs doblar
Ahora bien, aquí es donde se acerca un poco más a las raíces FP / matemáticas, y un poco más difícil de explicar. Reducir se define formalmente como parte del paradigma MapReduce, que se ocupa de colecciones sin orden (multisets), Fold se define formalmente en términos de recursión (ver catamorfismo) y por lo tanto asume una estructura / secuencia a las colecciones.
No existe un método fold en el escaldado porque bajo el modelo de programación (estricto) Map Reduce no podemos definir fold porque los trozos no tienen un orden y fold solo requiere asociatividad, no conmutatividad.
En pocas palabras, reduce funciona sin un orden de acumulación, fold requiere un orden de acumulación y es ese orden de acumulación el que requiere un valor cero NO la existencia del valor cero que los distingue. Estrictamente hablando reduce debe trabajar en una colección vacía, porque su valor cero puede deducirse tomando un valor arbitrario x y luego resolviendo x op y = x, pero eso no funciona con una operación no conmutativa ya que puede existir un valor cero izquierdo y derecho que son distintos (es decir, x op y != y op x). Por supuesto, Scala no se molesta en averiguar cuál es este valor cero, ya que requeriría hacer algunas matemáticas (que probablemente sean ), por lo que solo lanza una excepción.
Parece (como suele ser el caso en etimología) que este significado matemático original se ha perdido, ya que la única diferencia obvia en la programación es la firma. El resultado es que reduce se ha convertido en un sinónimo de fold, en lugar de preservar su significado original de MapReduce. Ahora bien, estos términos se usan indistintamente y se comportan de la misma manera en la mayoría de las implementaciones (ignorando las colecciones vacías). La rareza se ve exacerbada por peculiaridades, como en Spark, que ahora abordaremos.
Así que Spark tiene un fold, pero el orden en el que se combinan los resultados secundarios (uno para cada partición) (en el momento de escribir) es el mismo orden en el que se completan las tareas, y por lo tanto no determinista. Gracias a @CafeFeed por señalar que fold usa runJob, que después de leer el código me di cuenta de que no es determinista. Más confusión se crea por Chispa que tiene un treeReduce pero no treeFold.
Conclusión
Hay una diferencia entre reduce y fold incluso cuando se aplica a secuencias no vacías. El primero se define como parte del paradigma de programación MapReduce en colecciones con orden arbitrario ( http://theory.stanford.edu/~sergei/papers / soda10-mrc.pdf) y uno debe asumir que los operadores son conmutativos además de asociativos para dar resultados deterministas. Este último se define en términos de catomorfismos y requiere que el las colecciones tienen una noción de secuencia (o se definen recursivamente, como las listas enlazadas), por lo que no requieren operadores conmutativos.
En la práctica, debido a la naturaleza no matemática de la programación, reduce y fold tienden a comportarse de la misma manera, ya sea correctamente (como en Scala) o incorrectamente (como en Spark).
Extra: Mi Opinión Sobre la API de Spark
Mi opinión es que se evitaría la confusión si el uso del término fold se abandonara completamente en Chispa. Menos spark tiene una nota en su documentación:
Esto se comporta de manera algo diferente de las operaciones de plegado implementadas para colecciones no distribuidas en lenguajes funcionales como Scala.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-11-24 16:23:11
Si no me equivoco, aunque la API de Spark no lo requiera, fold también requiere que la f sea conmutativa. Porque el orden en el que se agregarán las particiones no está asegurado. Por ejemplo, en el siguiente código solo se ordena la primera impresión:
import org.apache.spark.{SparkConf, SparkContext}
object FoldExample extends App{
val conf = new SparkConf()
.setMaster("local[*]")
.setAppName("Simple Application")
implicit val sc = new SparkContext(conf)
val range = ('a' to 'z').map(_.toString)
val rdd = sc.parallelize(range)
println(range.reduce(_ + _))
println(rdd.reduce(_ + _))
println(rdd.fold("")(_ + _))
}
Imprimir:
Abcdefghijklmnopqrstuvwxyz
Abcghituvjklmwxyzqrsdefnop
Defghinopjklmqrstuvabcwxyz
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-03-16 16:24:58
Otra diferencia para el escaldado es el uso de combinadores en Hadoop.
Imagine que su operación es monoide conmutativo, con reducir se aplicará en el lado del mapa también en lugar de barajar/ordenar todos los datos a los reductores. Con foldLeft este no es el caso.
pipe.groupBy('product) {
_.reduce('price -> 'total){ (sum: Double, price: Double) => sum + price }
// reduce is .mapReduceMap in disguise
}
pipe.groupBy('product) {
_.foldLeft('price -> 'total)(0.0){ (sum: Double, price: Double) => sum + price }
}
Siempre es una buena práctica definir sus operaciones como monoides en Escaldado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-07 23:53:17
fold en Apache Spark no es lo mismo que fold en colecciones no distribuidas. De hecho se requiere la función conmutativa para producir resultados deterministas:
Esto se comporta de manera algo diferente de las operaciones de plegado implementadas para no distribuidas colecciones en lenguajes funcionales como Scala. Esta operación de plegado se puede aplicar a particiones individualmente, y luego doblar esos resultados en el resultado final, en lugar de aplicar el pliegue a cada elemento secuencialmente en algún orden definido. Para funciones que no son conmutativos, el resultado puede diferir del de un pliegue aplicado a un colección no distribuida.
Este ha demostrado por Misael Rosenthal y sugerido por Make42{[19] {} en[32]}su comentario.
Se ha sugerido que el comportamiento observado está relacionado con HashPartitioner cuando de hecho parallelize no baraja y no usa HashPartitioner.
import org.apache.spark.sql.SparkSession
/* Note: standalone (non-local) mode */
val master = "spark://...:7077"
val spark = SparkSession.builder.master(master).getOrCreate()
/* Note: deterministic order */
val rdd = sc.parallelize(Seq("a", "b", "c", "d"), 4).sortBy(identity[String])
require(rdd.collect.sliding(2).forall { case Array(x, y) => x < y })
/* Note: all posible permutations */
require(Seq.fill(1000)(rdd.fold("")(_ + _)).toSet.size == 24)
Explicado:
Estructura de fold para RDD
def fold(zeroValue: T)(op: (T, T) => T): T = withScope {
var jobResult: T
val cleanOp: (T, T) => T
val foldPartition = Iterator[T] => T
val mergeResult: (Int, T) => Unit
sc.runJob(this, foldPartition, mergeResult)
jobResult
}
Es lo mismo que la estructura de reduce para RDD:
def reduce(f: (T, T) => T): T = withScope {
val cleanF: (T, T) => T
val reducePartition: Iterator[T] => Option[T]
var jobResult: Option[T]
val mergeResult = (Int, Option[T]) => Unit
sc.runJob(this, reducePartition, mergeResult)
jobResult.getOrElse(throw new UnsupportedOperationException("empty collection"))
}
Donde runJob se realiza sin tener en cuenta el orden de la partición y resulta en la necesidad de la función conmutativa.
foldPartition y reducePartition son equivalentes en términos de orden de procesamiento y efectivamente (por herencia y delegación) implementadas por reduceLeft y foldLeft on TraversableOnce.
Conclusión: folden RDD no puede depender del orden de los trozos y las necesidades conmutatividad y asociatividad.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:34:53