foldRight Effizienz?

Question

Ich habe gehört, dass foldLeft in den meisten Operationen viel effizienter ist, aber Scala School (von Twitter) gab das folgende Beispiel. Kann jemand eine Analyse der Effizienz geben und sollten wir die gleiche Operation mit foldLeft erreichen?

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

Wie Sie aus den Unterlagen ersehen können, List Die Methoden foldRight und foldLeft sind definiert in LinearSeqOptimized . Werfen Sie also einen Blick auf die Quelle:

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))

Also foldLeft verwendet eine while-Schleife und foldRight verwendet eine einfach-rekursive Methode. Insbesondere ist sie nicht tail-rekursiv. Daher foldRight hat den Overhead, neue Stack-Frames zu erzeugen und neigt dazu, den Stack überlaufen zu lassen, wenn Sie es mit einer langen Liste versuchen (versuchen Sie z.B. ((1 to 10000).toList :\ 0)(_+_) . Bumm! Aber es funktioniert auch ohne die toList denn Range 's foldRight funktioniert durch Umklappen nach links).

Warum also nicht immer foldLeft ? Für verknüpfte Listen ist eine rechte Faltung wohl die natürlichere Funktion, da verknüpfte Listen in umgekehrter Reihenfolge aufgebaut werden müssen. Sie können verwenden foldLeft für Ihre obige Methode, aber Sie müssen reverse die Ausgabe am Ende. (Versuchen Sie nicht, an Listen in einer linken Faltung anzuhängen, da die Komplexität O(n-quadratisch) ist).

Was die Frage betrifft, was in der Praxis schneller ist, foldRight o foldLeft + reverse habe ich einen einfachen Test durchgeführt und foldRight ist für Listen um 10 bis 40 % schneller. Dies muss der Grund dafür sein, dass List's foldRight so implementiert ist, wie es ist.

Answer 2

FoldRight kehrt die Liste um und wendet foldLeft an.