foldRight Verimliliği?

Question

foldLeft işlemlerinin çoğunda çok daha etkili olduğunu duydum, ancak Scala School (Twitter'dan) aşağıdaki örneği verdi. Birisi verimliliğinin bir analizini verebilir ve foldLeft kullanarak aynı işlemi yapalım mı?

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

Dokümanlardan görebileceğiniz gibi, List 'un foldRight ve foldLeft yöntemleri, LinearSeqOptimized'da tanımlanmıştır. Yani kaynağında bir göz atın:

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

Yani foldLeft bir süre-döngü kullanır ve foldRight basit-özyinelemeli yöntemini kullanır. Özellikle kuyruk özyineli değildir. Bu nedenle, foldRight, yeni yığın çerçeveleri yaratmanın ek yüküne sahiptir ve uzun bir listede denerseniz yığının taşma eğilimine sahiptir (örneğin, ((1 to 10000).toList :\ 0)(_+_). Bom! Ama toList olmadan çalışır, çünkü Range 'foldRight tarafından çalışır. katlamayı sola döndürme).

Neden her zaman foldLeft'u kullanmıyorsunuz? Bağlı listeler için, doğru bir kat daha doğal bir işlevdir, çünkü bağlantılı listeler ters sırada yapılmalıdır. Yukarıdaki yöntem için foldLeft'u kullanabilirsiniz, ancak sonunda çıktıyı reverse yapmanız gerekir. (Karmaşıklık O (n-kare olduğu gibi), bir sol kıvrımında Listelerine ekleme çalışmayın.)

olarak kendisi için daha hızlı pratikte ise, foldRight veya + reversefoldLeft, basit bir testi yaptı ve foldRight olduğunu Listeler için daha hızlı% 10 ile% 40 arasında. Listenin foldRight'ın neden böyle uygulandığını anlamanız gerekir.

Answer 2

foldRight, listeyi tersine çevirir ve foldLeft uygulamasına uygulanır.