scala - preferencia - girar a la izquierda en carretera

¿Diferencia entre reducir y doblar hacia la izquierda/doblar en la programación funcional(especialmente las API de Scala y Scala)?

Question

¿Por qué Scala y frameworks como Spark y Scalding tienen tanto foldLeft como foldLeft ? Entonces, ¿cuál es la diferencia entre reduce y fold ?

Answer 1

reducir vs foldLeft

Una gran diferencia, que no se menciona en ninguna otra respuesta de stackoverflow relacionada con este tema, es que se debe dar un monoide conmutativo , es decir, una operación conmutativa y 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 cual reduce incluso existe. La colección puede dividirse y la reduce puede operar en cada porción, luego la reduce puede operar en los resultados de cada porción; de hecho, el nivel de fragmentación no necesita detenerse en un nivel profundo. Podríamos cortar cada pedazo también. Esta es la razón por la suma de enteros en una lista es O (log N) si se le da un número infinito de CPU.

Si solo mira las firmas, no hay ninguna razón para que exista reduce porque puede lograr todo lo que pueda con reduce con foldLeft . La funcionalidad de foldLeft es mayor que la funcionalidad de reduce .

Pero no puede paralelizar un foldLeft , por lo que su tiempo de ejecución siempre es O (N) (incluso si alimenta en un monoide conmutativo). Esto se debe a que se supone que la operación no es un monoide conmutativo, por lo que 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 lo que hace que la acumulación sea fácil porque el orden no es importante (por lo que no importa qué orden se agregue a cada uno de los resultados de cada uno de los fragmentos). Estrictamente hablando, la conmutatividad no es necesaria para la paralelización, por ejemplo, los algoritmos de ordenación distribuidos, simplemente hace que la lógica sea más fácil, ya que no es necesario que ordene a sus trozos.

Si echa un vistazo a la documentación de Spark para reduce , dice específicamente "... operador binario conmutativo y asociativo"

http://spark.apache.org/docs/1.0.0/api/scala/index.html#org.apache.spark.rdd.RDD

Aquí hay una 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 es donde se acerca un poco más a las raíces matemáticas / FP, y un poco más complicado de explicar. Reducir se define formalmente como parte del paradigma MapReduce, que trata con colecciones sin orden (multisectos), Fold se define formalmente en términos de recursión (ver catamorfismo) y asume una estructura / secuencia para las colecciones.

No hay fold método de fold en Scalding porque bajo el (estricto) modelo de programación Map Reduce no podemos definir fold porque los trozos no tienen un orden y fold solo requiere asociatividad, no conmutatividad.

En pocas palabras, reduce obras sin un orden de acumulación, el fold requiere un orden de acumulación y es ese orden de acumulación lo que necesita un valor cero, NO la existencia del valor cero que los distingue. Estrictamente hablando, reduce debería funcionar en una colección vacía, porque su valor cero puede deducirse tomando un valor arbitrario x luego resolviendo x op y = x , pero eso no funciona con una operación no conmutativa, ya que puede existir una izquierda y el valor cero derecho que son distintos (es decir, x op y != y op x ). Por supuesto, Scala no se molesta en determinar cuál es este valor cero ya que eso requeriría hacer algunas matemáticas (que probablemente no sean computables), por lo que solo arroja 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 ha convertido en un sinónimo de fold , en lugar de preservar su significado original de MapReduce. Ahora, estos términos se usan indistintamente y se comportan igual en la mayoría de las implementaciones (ignorando 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 que los resultados secundarios (uno para cada partición) se combinan (en el momento de redactarse) es el mismo orden en el que se completan las tareas, y por lo tanto no es determinista. Gracias a @CafeFeed por señalar que fold utiliza runJob , que después de leer el código me di cuenta de que no es determinista. Se crea una mayor confusión cuando Spark 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 de MapReduce en colecciones con un orden arbitrario ( http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf ) y se debe suponer que los operadores son conmutativos además de ser asociativo para dar resultados deterministas. Este último se define en términos de catomorfismos y requiere que las colecciones tengan una noción de secuencia (o se definan recursivamente, como 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 Spark

Mi opinión es que la confusión se evitaría si el uso del término fold fuera completamente eliminado en Spark. Al menos spark tiene una nota en su documentación:

Esto se comporta de forma algo diferente de las operaciones de fold implementadas para colecciones no distribuidas en lenguajes funcionales como Scala.

Answer 2

Otra diferencia para Scalding es el uso de combinadores en Hadoop.

Imagine que su operación es conmutativa monoide, con reduce , se aplicará en el lado del mapa también en lugar de barajar / clasificar todos los datos en 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 monoide en escaldado.

Answer 3

Si no me equivoco, aunque la API Spark no lo requiera, fold también requiere que f sea conmutativa. Porque el orden en 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:

ABCDEFGHIJKLMNOPQRSTU VWXYZ

abcghituvjklmwxyzqrsdefnop

defghinopjklmqrstuvabcwxyz

Answer 4

fold en Apache Spark no es lo mismo que fold colecciones no distribuidas. De hecho , requiere la función conmutativa para producir resultados deterministas:

Esto se comporta de forma algo diferente de las operaciones de fold implementadas para colecciones no distribuidas en lenguajes funcionales como Scala. Esta operación de plegado se puede aplicar a las particiones de forma individual, 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 las funciones que no son conmutativas, el resultado puede diferir del de un pliegue aplicado a una colección no distribuida.

Esto ha sido demostrado por y sugerido por Make42 en su comentario .

Se ha sugerido que el comportamiento observado está relacionado con HashPartitioner cuando, en realidad, parallelize no se mezcla 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 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 partición y los resultados 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) implementados por reduceLeft y foldLeft en TraversableOnce .

Conclusión: fold on RDD no puede depender del orden de los trozos y necesita conmutatividad y asociatividad .