Разница между сокращением и foldLeft / fold в функциональном программировании (в частности, Scala и Scala API)?

уменьшить vs foldLeft

Большая разница, не упомянутая в любом другом ответе stackoverflow, относящемся к этой теме, заключается в том, что reduce следует присваивать коммутативный monoид , то есть операцию, которая является коммутативной и ассоциативной. Это означает, что операция может быть распараллелена.

Это различие очень важно для Big Data / MPP / распределенных вычислений, и вся причина, почему reduce даже существует. Сбор можно расколоть, и reduce может работать на каждом куске, тогда reduce может работать на результатах каждого куска – фактически уровень отсечения не должен останавливаться на одном уровне. Мы могли бы нарезать каждый кусок. Вот почему суммирование целых чисел в списке – это O (log N), если задано бесконечное количество процессоров.

Если вы просто посмотрите на подписи, нет причин для reduce потому что вы можете добиться всего, что можете, с помощью foldLeft . Функциональность foldLeft больше, чем функциональность reduce .

Но вы не можете распараллелить foldLeft , поэтому его время выполнения всегда равно O (N) (даже если вы загружаете коммутативный monoид). Это связано с тем, что предполагается, что операция не является коммутативным monoидом, и поэтому кумулятивное значение будет вычисляться серией последовательных агрегаций.

foldLeft не предполагает коммутативности или ассоциативности. Это ассоциативность, которая дает возможность обрезать коллекцию, и это коммутативность, которая делает кумуляцию легкой, потому что порядок не важен (так что не имеет значения, какой порядок сводит каждый из результатов от каждого из кусков). Строго говоря, коммутативность не нужна для распараллеливания, например, распределенных алгоритмов сортировки, это просто делает логику проще, потому что вам не нужно давать вашим кускам заказ.

Если вы посмотрите на документацию Spark, чтобы reduce ее, это говорит «… коммутативный и ассоциативный двоичный оператор»,

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

Вот доказательство того, что reduce – это не просто частный случай 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 

уменьшить или свернуть

Теперь это то, где он немного приближается к FP / математическим корням, и немного сложнее объяснить. Сокращение определяется формально как часть парадигмы MapReduce, которая касается упорядоченных коллекций (мультимножеств), Fold формально определяется в терминах рекурсии (см. Катаморфизм) и, таким образом, принимает структуру / последовательность в коллекции.

В Scalding не существует метода fold потому что при (строгой) модели программирования Map Reduce мы не можем определить fold потому что куски не имеют упорядочения и fold требуют только ассоциативности, а не коммутативности.

Проще говоря, reduce работы без порядка кумуляции, fold требует порядка кумуляции, и именно этот порядок кумуляции требует нулевого значения NOT существования нулевого значения, которое их отличает. Строго говоря, reduce должно работать над пустой коллекцией, потому что его нулевое значение может быть выведено путем принятия произвольного значения x и затем решения x op y = x , но это не работает с некоммутативной операцией, так как может существовать левая и правое нулевое значение, отличное (т.е. x op y != y op x ). Конечно, Scala не удосуживается понять, что это нулевое значение, так как это потребует выполнения некоторой математики (которая, вероятно, невычислима), поэтому просто генерирует исключение.

Кажется (как это часто бывает в этимологии), что этот оригинальный математический смысл был утрачен, поскольку единственным очевидным различием в программировании является подпись. В результате reduce стало синонимом fold , а не сохранением его первоначального значения от MapReduce. Теперь эти термины часто используются взаимозаменяемо и ведут себя одинаково в большинстве реализаций (игнорируя пустые коллекции). Странность усугубляется особенностями, такими как Спарк, которые мы сейчас рассмотрим.

Таким образом, Spark имеет fold , но порядок, в котором субрезультаты (по одному для каждого раздела) объединяются (на момент написания), – это тот же порядок, в котором выполняются задачи, и, следовательно, не детерминирован. Благодаря @CafeFeed для указания того, что fold использует runJob , который после прочтения кода понял, что он недетерминирован. Дальнейшая путаница создается Spark, имеющим treeReduce но не treeFold .

Вывод

Существует разница между reduce и fold даже при применении к непустым последовательностям. Первый из них определяется как часть парадигмы программирования MapReduce для коллекций с произвольным порядком ( http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf ), и каждый должен предположить, что операторы являются коммутативными в дополнение к ассоциативно дать детерминированные результаты. Последнее определяется в терминах catomorphisms и требует, чтобы коллекции имели понятие последовательности (или определены рекурсивно, как связанные списки), поэтому не требуют коммутативных операторов.

На практике из-за не математического характера программирования reduce и сгибание ведут себя одинаково, либо правильно (например, в Scala), либо неправильно (например, в Spark).

Дополнительно: Мое мнение о API Spark

Мое мнение состоит в том, что путаницы можно было бы избежать, если бы использование слова « fold полностью было сброшено в Spark. По крайней мере, у искры есть заметка в их документации:

Это ведет себя несколько иначе, чем операции сброса, выполняемые для нераспределенных коллекций в функциональных языках, таких как Scala.

Если я не ошибаюсь, даже если API Spark не требует этого, fold также требует, чтобы f был коммутативным. Потому что порядок, в котором агрегаты будут агрегированы, не гарантируется. Например, в следующем коде сортируется только первый распечаток:

 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("")(_ + _)) } 

Распечатать:

АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ

abcghituvjklmwxyzqrsdefnop

defghinopjklmqrstuvabcwxyz

Еще одним отличием Scalding является использование комбинаторов в Hadoop.

Представьте, что ваша операция является коммутативной monoидой, а ее уменьшение будет применяться на стороне карты, а не перетасовки / сортировки всех данных на редукторы. С foldLeft это не так.

 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 } } 

Всегда хорошая практика – определять свои операции как monoиды в Scalding.

fold в Apache Spark – это не то же самое, что fold на нераспределенные коллекции. Фактически это требует коммутативной функции для получения детерминированных результатов:

Это ведет себя несколько иначе, чем операции сброса, выполняемые для нераспределенных коллекций в функциональных языках, таких как Scala. Эта операция сложения может применяться к разделам по отдельности, а затем сворачивать эти результаты в конечный результат, а не применять к каждому элементу последовательность последовательно в некотором определенном порядке. Для функций, которые не являются коммутативными, результат может отличаться от результата сложения, применяемого к нераспределенному набору.

Это было показано Мишалем Розенталем и предложено Make42 в его комментарии .

Было высказано предположение, что наблюдаемое поведение связано с HashPartitioner когда на самом деле parallelize не перемешивается и не использует 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) 

Разъяснение:

Структура fold для 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 } 

такая же, как структура reduce для 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")) } 

где runJob выполняется с пренебрежением порядком раздела и приводит к необходимости использования коммутативной функции.

foldPartition и reducePartition эквивалентны с точки зрения порядка обработки и эффективно (путем наследования и делегирования), реализуемых reduceLeft и foldLeft на TraversableOnce .

Вывод: fold на RDD не может зависеть от порядка кусков и необходимости коммутации и ассоциативности .