foldRight效率？

Question

我听说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)

Answer 1

正如您从文档中看到的那样,ListfoldRight和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)(_+_).轰!但它没有的工作正常toList,因为它Range的foldRight工作是通过反转左折叠) .

那么为什么不总是使用foldLeft？对于链表,右侧折叠可以说是更自然的功能,因为链接列表需要以相反的顺序构建.您可以使用foldLeft上面的方法,但最后需要reverse输出.(不要尝试在左侧折叠中附加列表,因为复杂度为O(n平方).)

至于哪个在实践中更快,foldRight或者foldLeft+ reverse,我进行了一个简单的测试,并且foldRight列表的速度提高了10%到40%.这必然是List的foldRight以其实现的方式实现的原因.