scala - 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不是尾递归的，所以给定一个足够大的集合，它会产生堆栈溢出。

例如，在我的机器上，如果我运行以下命令，则会出现内存不足错误，

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，但简而言之，您要减少的函数需要同时具有可交换性和关联性，以便为所有集合类型获得相同的结果。