sam*_*est 93 reduce functional-programming scala fold scalding
为什么Scala和像Spark和Scalding这样的框架都有reduce和foldLeft？那么reduce和之间的区别是fold什么？
sam*_*est 251
在与该主题相关的任何其他stackoverflow答案中没有提到的一个很大的区别是,reduce应该给出一个可交换的monoid,即一个可交换和关联的操作.这意味着操作可以并行化.
这种区别对于大数据/ MPP /分布式计算非常重要,reduce也是存在的全部原因.可以对集合进行切割,并且reduce可以对每个块进行操作,然后可以对每个块reduce的结果进行操作 - 实际上,块的级别不需要停止一个级别.我们也可以砍掉每一块.这就是为什么如果给定无限数量的CPU,则对列表中的整数求和为O(log N).
如果你只看一下签名就没有理由reduce存在,因为你可以reduce通过一个实现一切foldLeft.功能foldLeft大于功能reduce.
但是你不能并行化a foldLeft,所以它的运行时总是O(N)(即使你输入一个可交换的monoid).这是因为假设操作不是可交换的幺半群,因此累积值将通过一系列顺序聚合来计算.
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 /数学根源的地方,并且解释起来有点棘手.Reduce正式定义为MapReduce范例的一部分,MapReduce范例处理无序集合(multisets),Fold在递归方面正式定义(参见catamorphism),因此假定集合的结构/序列.
fold在Scalding中没有方法,因为在(严格)Map Reduce编程模型下我们无法定义,fold因为块没有排序,fold只需要关联性,而不是交换性.
简而言之,reduce没有累积顺序的工作,fold需要累积的顺序,并且累积的顺序需要零值而不是存在区分它们的零值.严格来说,reduce 应该处理一个空集合,因为它的零值可以通过取一个任意值x然后求解来推导出来x op y = x,但这不适用于非交换操作,因为可以存在一个左右零值,它们是不同的(即x op y != y op x).当然Scala并不打算弄清楚这个零值是什么,因为它需要做一些数学(可能是不可计算的),所以只抛出异常.
似乎(在词源学中经常出现这种情况)这种原始的数学意义已经丢失,因为编程中唯一明显的区别就是签名.结果是它reduce已成为同义词fold,而不是保留MapReduce的原始含义.现在,这些术语通常可以互换使用,并且在大多数实现中表现相同(忽略空集合).我们现在要解决的问题就像Spark中的特殊情况一样加剧了怪异.
因此Spark 确实有fold,但是子结果(每个分区一个)组合的顺序(在编写时)与任务完成的顺序相同 - 因此是非确定性的.感谢@CafeFeed指出fold使用runJob,在阅读完代码之后,我发现它是非确定性的.Spark有一个treeReduce但没有treeFold.
应用于非空序列之间存在差异reduce,fold甚至应用于非空序列.前者被定义为具有任意顺序的集合的MapReduce编程范例的一部分(http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf),并且应该假设运算符是可交换的关联以给出确定性结果.后者根据catomorphisms定义,并要求集合具有序列概念(或递归定义,如链表),因此不需要可交换运算符.
在实践中由于编程的非数学性质,reduce并且fold倾向于以相同的方式表现,正确(如在Scala中)或不正确(如在Spark中).
我的观点是,如果fold在Spark中完全放弃使用该术语,则可以避免混淆.至少spark确实在他们的文档中有一个注释:
这与在Scala等函数语言中为非分布式集合实现的折叠操作有所不同.
Mis*_*hal 10
如果我没有弄错,即使Spark API不需要它,折叠也要求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("")(_ + _))
}
打印:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcghituvjklmwxyzqrsdefnop
defghinopjklmqrstuvabcwxyz