foldRight Hiệu quả?

Question

Tôi nghe foldLeft hiệu quả hơn nhiều trong hầu hết các hoạt động, nhưng trường Scala (từ Twitter) đưa ra ví dụ sau. Ai đó có thể đưa ra một phân tích về hiệu quả của nó và chúng ta có nên đạt được cùng một hoạt động bằng cách sử dụng foldLeft không?

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

Như bạn có thể nhìn thấy từ tài liệu, số lần xem và gấp nếp của số trang List được xác định trong LinearSeqOptimized. Vì vậy, hãy nhìn vào các nguồ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)) 

Vì vậy foldLeft sử dụng một vòng lặp while và foldRight sử dụng một phương pháp đơn giản-đệ quy. Đặc biệt nó không phải là đệ quy đuôi. Như vậy foldRight có phí của việc tạo ra các khung stack mới và có xu hướng tràn ngăn xếp nếu bạn thử nó trên một danh sách dài (thử, ví dụ ((1 to 10000).toList :\ 0)(_+_). Boom! Nhưng nó hoạt động tốt mà không có sự toList, vì Range 's foldRight tác phẩm của đảo chiều gấp bên trái).

Vậy tại sao không phải lúc nào cũng sử dụng foldLeft? Đối với các danh sách liên kết, một nếp gấp bên phải được cho là một hàm tự nhiên hơn, bởi vì các danh sách liên kết cần phải được xây dựng theo thứ tự ngược lại. Bạn có thể sử dụng foldLeft cho phương pháp của mình ở trên, nhưng bạn cần phải reverse đầu ra ở cuối. (Đừng cố gắng phụ thêm vào danh sách trong một lần trái, như mức độ phức tạp là O (n-squared).)

Đối với đó là nhanh hơn trong thực tế, foldRight hoặc foldLeft + reverse, tôi chạy một thử nghiệm đơn giản và foldRight là nhanh hơn cho Danh sách từ 10 đến 40%. Đây phải là lý do tại sao foldRight của List được thực hiện theo cách của nó.

Answer 2

foldQuay lại danh sách và áp dụng gấpLeft.