scala - Scala中的reduceLeft和reduceRight有什么区别？

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中，因此此处的顺序无关紧要。

最佳答案

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

正如Lionel已经指出的那样，如果您用来组合元素的函数是关联的，则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，但简而言之，要减少的功能需要可交换和可关联，以便为所有集合类型获得相同的结果。