Các phương pháp đệ quy để tạo Luồng trong Scala

Question

Đây là bước tiếp theo để my previous question.

Khi tôi understand phương pháp sau đây để tính số Fibonacci không hiệu quả vì phương pháp fib được gọi cho mỗi số Fibonacci và mỗi lần được gọi là tạo một luồng mới.

def fib:Stream[Int] = 
    Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))

Mở Mặt khác đuôi đệ quy phương pháp (như trong here) trông khá hiệu quả và tính toán mỗi số Fibonacci trong O(1)

def fib(a:Int, b:Int):Stream[Int] = Stream.cons(a, fib(b, a+b));

Bây giờ tôi kết luận rằng phương pháp đệ quy mà tạo Streams có hiệu quả nếu và chỉ khi chúng có đuôi đệ quy. Nó có đúng không?

Answer 1

Tôi đã cố gắng để cải thiện trên Andy 's answer, nhưng ông khá nhiều đóng đinh nó. Giải pháp đầu tiên là tạo hình chóp suối - mỗi cuộc gọi tới fib tạo ra một luồng mã vạch khác và mỗi luồng mới này sẽ tự tạo luồng mới, v.v.

Để được rõ ràng, có ba suối kết quả từ một cuộc gọi đến fib:

• Một tạo ra bởi fib trong fib zip fib.tail
• Một tạo ra bởi fib.tail trong fib zip fib.tail
• Một tạo ra bởi map (hãy nhớ, map tạo bộ sưu tập mới)

Vì hai người đầu tiên gọi tới fib, họ sẽ tạo ba luồng mỗi lần, v.v.

Dưới đây là một "hình ảnh" thô của nó:

      1 
          1 
      1    2    1 
      1    3  1  2  1 
    1  2  1  5  1  3 1 2 1 
    1  3 1 2 1 8 1 2 1 5 1 3 1 2 1       

Và điều này đi và về. Luồng giữa được tính bằng cách sử dụng các luồng cao nhất bên trái và bên phải (fib và fib.tail). Mỗi người trong số họ được tính bằng cách sử dụng các luồng thấp hơn trên của họ bên trái và bên phải. Mỗi luồng dưới được tính bằng các luồng được hiển thị trên dòng cuối cùng.

Chúng tôi có thể tiếp tục điều này, nhưng bạn có thể thấy rằng, vào thời điểm chúng tôi tính toán 8, chúng tôi đã có 14 dòng mã nguồn khác đang diễn ra.

Nếu bạn thay đổi nó def-val, tất cả những con suối mới biến mất, bởi vì fib và fib.tail sẽ đề cập đến một dòng hiện thay vì tạo dòng mới. Và do không có luồng mới nào được tạo nên sẽ không có thêm cuộc gọi nào tới fib và fib.tail.

Bây giờ, nếu bạn nhìn vào câu trả lời thứ hai, bạn sẽ nhận thấy rằng có một cuộc gọi fib duy nhất và không map hoặc phương pháp tương tự, vì vậy không có hiệu ứng nhân.

Answer 2

Không, đuôi đệ quy là để giúp trình biên dịch looping thay vì xếp chồng (trên toàn cầu), đó là một tối ưu hóa thời gian biên dịch.

Sự cố đến từ lần triển khai đầu tiên trong đó một số cuộc gọi đến fib dẫn đến một số công trình Xây dựng luồng, do đó việc tính toán giống nhau được thực hiện lặp đi lặp lại.

fib zip fib.tail 
//if we are at the 1000, it will compute million Streams 

Nếu bạn muốn nhìn thấy nó hãy thử như sau

var i = 0 
def fib:Stream[Int] = { 
    i = i + 1 
    println("new Stream : " + i) 
    Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y})) 
}