9

我听说 foldLeft 在大多数操作中效率更高，但 Scala School（来自 Twitter）给出了以下示例。有人可以分析它的效率吗？我们是否应该使用 foldLeft 实现相同的操作？

val numbers = List(1,2,3,4,5,...10)
def ourMap(numbers: List[Int], fn: Int => Int): List[Int] = {
    numbers.foldRight(List[Int]()) { (x: Int, xs: List[Int]) =>
    fn(x) :: xs
  }
}

scala> ourMap(numbers, timesTwo(_))
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
4

2 回答 2

15

正如您从文档中看到的那样，List的 foldRight 和 foldLeft 方法定义在LinearSeqOptimized. 所以看一下源码：

override /*TraversableLike*/
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
}

override /*IterableLike*/
def foldRight[B](z: B)(f: (A, B) => B): B =
  if (this.isEmpty) z
  else f(head, tail.foldRight(z)(f))

所以foldLeft使用一个while循环并foldRight使用一个简单的递归方法。特别是它不是尾递归的。因此foldRight，如果您在长列表上尝试它会产生创建新堆栈帧的开销并且有溢出堆栈的趋势（例如尝试((1 to 10000).toList :\ 0)(_+_). Boom！但是没有 , 它可以正常工作toList，因为Range'foldRight通过反转向左折叠来工作） .

那么为什么不总是使用foldLeft呢？对于链表，右折叠可以说是一种更自然的功能，因为链表需要以相反的顺序构建。您可以使用foldLeft上面的方法，但最后需要reverse输出。（不要尝试在左折叠中追加列表，因为复杂度是 O(n-squared)。）

至于哪个在实践中更快，foldRight或者foldLeft+ reverse，我进行了一个简单的测试，foldRight列表的速度提高了 10% 到 40%。这一定是为什么 List 的 foldRight 是这样实现的。

于 2012-06-12T22:47:14.867 回答
-2

foldRight 反转列表并应用 foldLeft。

于 2012-06-12T21:18:03.770 回答