在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，所以顺序在这里并不重要。

- Finkelson

Answer 1

它们何时产生相同的结果

就像Lionel已经指出的那样，reduceLeft和reduceRight只有在您使用的组合元素函数是可结合的情况下才会产生相同的结果（这并不总是正确的，请参见我在底部的注释）。例如，当使用函数(a: Int, b: Int) => a - b将其应用于Seq(1,2,3)上运行reduceLeft和reduceRight时，您会得到不同的结果。

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使用尾递归实现，因此在操作非常大的集合（甚至可能是无限的）时，它将不会导致堆栈溢出。但是reduceRight没有进行尾递归优化，因此当处理足够大的集合时，它会产生堆栈溢出。

例如，在我的计算机上，如果运行以下代码，将会得到一个内存不足错误：

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，简而言之，您正在进行缩减操作的函数需要是可交换的和可结合的，才能在所有集合类型中获得相同的结果。

- isomarcte

---

这个模式解释了一切。太好了。 - Abdullah Khan

很好的解释！谢谢！ - Onur Tokat

Answer 2

将左侧缩减并不总是等同于右侧缩减。考虑一下在数组上使用非对称函数。

假设结果相同，性能是一个明显的区别。

请参见性能特征

该数据结构具有对头部和尾部的恒定访问时间。反向迭代对于大型列表的性能较差。

- Lionel Port

---

异或（XOR）...你想说的是list reduceLeft {_ ^ _}和list reduceRight {_ ^ _}不一样吗？ - Finkelson

是的，异或运算是个不好的例子，但像 { _ - _ } 这样的非对称函数会给出不同的结果。例如，列表 reduceLeft { _ - _ } = -2 和列表 reduceRight { _ - _ } = 0。 - Lionel Port

Answer 3

最好的方法是阅读library/scala/collection/LinearSeqOptimized.scala中的源代码，以了解它们之间的区别。

  def reduceLeft[B >: A](f: (B, A) => B): B =
    ......
    tail.foldLeft[B](head)(f)

  def reduceRight[B >: A](op: (A, B) => B): B =
    ...... 
    op(head, tail.reduceRight(op))

  def foldLeft[B](z: B)(f: (B, A) => B): B = {
    var acc = z 
    var these = this              
    while (!these.isEmpty) {      
      acc = f(acc, these.head)    
      these = these.tail          
    }                             
    acc
  } 

以上是代码的一些关键部分，你可以看到 reduceLeft 是基于 foldLeft 实现的，而 reduceRight 则是通过递归实现的。

我猜 reduceLeft 的性能更好。

- Binzi Cao