foldRight效率？

我聽說foldLeft在大多數操作中效率更高，但斯卡拉學校（來自Twitter）給出了下面的例子。有人可以分析其效率，並且我們是否應該使用foldLeft來實現相同的操作？foldRight效率？

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)

來源

2012-06-12 chen

正如您從文檔中看到的，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平方）。）

至於這是在實踐中更快，foldRight或foldLeft + reverse，我跑了一個簡單的測試和foldRight是列表的速度在10％到40％之間更快。這必定是爲什麼List的foldRight按照這種方式實施的原因。

來源

2012-06-12 22:47:14

我可以澄清你對上次陳述的回答嗎？ foldRight通常比foldLeft快10％-40％，但是如果包含反向操作，那麼這種差異是可以預料的。在左右摺疊之間進行選擇時，正確摺疊所需的堆疊框架的成本可能很高，但反向摺疊的高成本會反向使用foldLeft。如果foldLeft（沒有反向）是一個選項，它似乎是整體的首選。 –

請注意，我相信'List'的'foldRight'只是在最近版本的Scala中左對齊+反轉，可能是爲了避免堆棧溢出 –

-2

foldRight顛倒列表並應用foldLeft。

來源

2012-06-12 21:18:03

foldRight效率？

回答

相關問題