foldRight 效率? [英] foldRight Efficiency?

问题描述

我听说 foldLeft 在大多数操作中效率更高，但 Scala School(来自 Twitter)给出了以下示例.谁能分析一下它的效率，我们是否应该使用foldLeft来实现相同的操作?

I heard foldLeft is much more efficient in most of operations, but Scala School (from Twitter) gave the following example. Can someone give an analysis of its efficiency and should we achieve the same operation using 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)

推荐答案

从文档中可以看出，List 的 foldRight 和 foldLeft 方法在 LinearSeqOptimized 中定义.所以看一下源码:

As you can see from the docs, List's foldRight and foldLeft methods are defined in LinearSeqOptimized. So take a look at the source:

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 有效通过向左反转折叠).

So foldLeft uses a while-loop and foldRight uses a simple-recursive method. In particular it is not tail-recursive. Thus foldRight has the overhead of creating new stack frames and has a tendency to overflow the stack if you try it on a long list (try, for example ((1 to 10000).toList :\ 0)(_+_). Boom! But it works fine without the toList, because Range's foldRight works by reversing the folding left).

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

So why not always use foldLeft? For linked lists, a right fold is arguably a more natural function, because linked lists need to be built in reverse order. You can use foldLeft for your method above, but you need to reverse the output at the end. (Do not try appending to Lists in a left fold, as the complexity is O(n-squared).)

至于在实践中哪个更快，foldRight 或 foldLeft + reverse，我运行了一个简单的测试和 foldRight 对于 Lists 来说快了 10% 到 40%.这一定就是为什么 List 的 foldRight 被这样实现的原因.

As for which is quicker in practice, foldRight or foldLeft + reverse, I ran a simple test and foldRight is faster for Lists by between 10 and 40 %. This must be why List's foldRight is implemented the way it is.

这篇关于foldRight 效率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！