Scala中reduceLeft和reduceRight之间的区别是什么？

Question

Scala中reduceLeft和reduceRight之间的区别是什么？

  val list = List(1, 0, 0, 1, 1, 1)

  val sum1 = list reduceLeft  {_ + _}   
  val sum2 = list reduceRight {_ + _}

  println { sum2 == sum2 }

在我的代码段sum1= sum2= 4,所以这里的顺序无关紧要.

Answer 1

它们何时产生相同的结果

由于梅西已经指出,reduceLeft并且reduceRight只产生相同的结果,如果你正在使用的元素相结合的功能是联想(这并不总是正确的,看到我的笔记在底部).运行时,比如reduceLeft和reduceRight上Seq(1,2,3)与功能(a: Int, b: Int) => a - b你会得到不同的结果.

scala> Seq(1,2,3)
res0: Seq[Int] = List(1, 2, 3) 

scala> res0.reduceLeft(_ - _)
res5: Int = -4

scala> res0.reduceRight(_ - _)
res6: Int = 2

如果我们看一下如何在列表中应用每个函数,为什么会发生这种情况.

因为reduceRight这是我们打开它们时调用的样子.

(1 - (2 - 3))
(1 - (-1))
2

因为reduceLeft序列是从左边开始建立的,

((1 - 2) - 3)
((-1) - 3)
(-4)

尾递归

进一步因为reduceLeft使用Tail Recursion实现,在非常大的集合(甚至可能是无限的)上运行时它不会堆栈溢出.reduceRight不是尾递归,所以给定一个足够大的集合,它会产生堆栈溢出.

例如,在我的机器上,如果我运行以下内容,我会收到Out of Memory错误,

scala> (0 to 100000000).reduceRight(_ - _)
java.lang.OutOfMemoryError: GC overhead limit exceeded
  at java.lang.Integer.valueOf(Integer.java:832)
  at scala.runtime.BoxesRunTime.boxToInteger(BoxesRunTime.java:65)
  at scala.collection.immutable.Range.apply(Range.scala:61)
  at scala.collection.IndexedSeqLike$Elements.next(IndexedSeqLike.scala:65)
  at scala.collection.Iterator$class.foreach(Iterator.scala:742)
  at scala.collection.AbstractIterator.foreach(Iterator.scala:1194)
  at scala.collection.TraversableOnce$class.reversed(TraversableOnce.scala:99)
  at scala.collection.AbstractIterator.reversed(Iterator.scala:1194)
  at scala.collection.TraversableOnce$class.reduceRight(TraversableOnce.scala:197)
  at scala.collection.AbstractIterator.reduceRight(Iterator.scala:1194)
  at scala.collection.IterableLike$class.reduceRight(IterableLike.scala:85)
  at scala.collection.AbstractIterable.reduceRight(Iterable.scala:54)
  ... 20 elided

但如果我计算reduceLeft我没有得到OOM,

scala> (0 to 100000000).reduceLeft(_ - _)
res16: Int = -987459712

根据您的JVM默认内存设置,您的系统可能会得到略微不同的结果.

喜欢左侧版本

因此,由于尾递归,如果您知道reduceLeft并且reduceRight将产生相同的值,您应该更喜欢reduceLeft变体.这通常持有的其他左/右功能,如真正的foldRight和foldLeft(这只是较为笼统的reduceRight和reduceLeft).

他们什么时候真的总是产生相同的结果

关于reduceLeft和你正在使用的函数reduceRight的关联属性的小注释.我说过,如果运算符是关联的reduceRight,reduceLeft则只产生相同的结果.对于所有集合类型,并非总是如此.这在某种意义上是另一个话题了,所以咨询ScalaDoc,但在很短的功能您正在使用的需求减少是双方交换和关联,以获得相同的结果的所有集合类型.