danh Xếp Scala

Question

Với đoạn mã sau:

import scala.util.Random 

object Reverser { 

    // Fails for big list 
    def reverseList[A](list : List[A]) : List[A] = { 
    list match { 
     case Nil => list 
     case (x :: xs) => reverseList(xs) ::: List(x) 
    } 
    } 

    // Works 
    def reverseList2[A](list : List[A]) : List[A] = { 
    def rlRec[A](result : List[A], list : List[A]) : List[A] = { 
     list match { 
     case Nil => result 
     case (x :: xs) => { rlRec(x :: result, xs) } 
     } 
    } 
    rlRec(Nil, list) 
    } 

    def main(args : Array[String]) : Unit = { 
    val random = new Random 
    val testList = (for (_ <- 1 to 2000000) yield (random.nextInt)).toList 
    // val testListRev = reverseList(testList) <--- Fails 
    val testListRev = reverseList2(testList) 
    println(testList.head) 
    println(testListRev.last) 
    } 
} 

Tại sao phiên bản đầu tiên của hàm thất bại (vì những đóng góp lớn), trong khi biến thể thứ hai hoạt động. Tôi nghi ngờ đó là một cái gì đó liên quan đến đệ quy đuôi, nhưng tôi không chắc chắn lắm. Ai đó có thể vui lòng cho tôi lời giải thích "cho người giả" không?

Answer 1

Ok để tôi thử đuôi đệ quy cho núm vú cao su

Nếu bạn làm theo những gì đã được thực hiện với reverseList, bạn sẽ nhận được

reverseList(List(1,2,3, 4)) 
reverseList(List(2,3,4):::List(1) 
(reverseList(List(3,4):::List(2)):::List(1) 
((reverseList(List(4):::List(3)):::List(2)):::List(1) 
Nil:::List(4):::List(3):::List(2):::List(1) 
List(4,3,2,1) 

Với rlRec, bạn có

rlRec(List(1,2,3,4), Nil) 
rlRec(List(2,3,4), List(1)) 
rlREc(List(3,4), List(2,1)) 
rlRec(List(4), List(3,2,1)) 
rlRec(Nil, List(4,3,2,1)) 
List(4,3,2,1) 

Các sự khác biệt là trong trường hợp đầu tiên, việc viết lại tiếp tục nhận được lâu hơn. Bạn phải nhớ điều cần làm sau khi cuộc gọi đệ quy cuối cùng đến reverseList sẽ hoàn thành: các phần tử cần thêm vào kết quả. Ngăn xếp được sử dụng để ghi nhớ điều đó. Khi điều này đi quá xa, bạn sẽ bị tràn ngăn xếp. Ngược lại, với rlRec, việc viết lại có cùng kích thước với nhau. Khi cuối cùng rlRec hoàn tất, kết quả có sẵn. Không có gì khác để làm, không có gì để nhớ, không cần cho ngăn xếp. Điều quan trọng là trong rlRec, cuộc gọi đệ quy là return rlRec(something else) trong khi ở reverseList nó là return f(reverseList(somethingElse)), với f beging _ ::: List(x). Bạn cần phải nhớ đến bạn sẽ phải gọi f (mà ngụ ý nhớ x quá) (trở không cần thiết trong scala, chỉ cần thêm vào cho rõ ràng. Cũng lưu ý rằng val a = recursiveCall(x); doSomethingElse() cũng giống như doSomethingElseWith(recursiveCall(x)), vì vậy nó không phải là một cuộc gọi đuôi)

khi bạn có một đệ quy đuôi gọi

def f(x1,...., xn) 
    ... 
    return f(y1, ...yn) 
    ... 

có thực sự là không cần phải nhớ bối cảnh của f đầu tiên cho khi một giây sẽ trở lại. Vì vậy, nó có thể được viết lại

def f(x1....xn) 
start: 
    ... 
    x1 = y1, .... xn = yn 
    goto start 
    ... 

Đó là những gì trình biên dịch thực hiện, do đó bạn tránh tràn ngăn xếp.

Tất nhiên, chức năng f cần phải quay lại đâu đó mà không phải là cuộc gọi đệ quy. Đó là nơi vòng lặp được tạo bởi goto start sẽ thoát, giống như khi chuỗi cuộc gọi đệ quy dừng lại.

Answer 2

Phương pháp đầu tiên không phải là đệ quy đuôi. Xem:

case (x :: xs) => reverseList(xs) ::: List(x) 

Hoạt động cuối cùng gọi là :::, không phải là cuộc gọi đệ quy reverseList. Một trong những khác là đuôi đệ quy.

Answer 3

Chức năng được gọi là tail recursive khi nó tự gọi là hành động cuối cùng của nó. Bạn có thể kiểm tra xem hàm có là tail recursive bằng cách thêm chú thích @tailrec.

Answer 4

Như những người khác đã đề cập, loại bỏ cuộc gọi đuôi tránh phát triển ngăn xếp khi không cần thiết. Nếu bạn tò mò về việc tối ưu hóa làm gì, bạn có thể chạy

scalac -Xprint:tailcalls MyFile.scala 

...để hiển thị trình biên dịch trung gian của trình biên dịch sau giai đoạn loại bỏ. (. Lưu ý rằng bạn có thể làm được điều này sau khi bất kỳ giai đoạn, và bạn có thể in danh sách các giai đoạn với scala -Xshow-giai đoạn)

Ví dụ, đối với, đuôi-đệ quy chức năng bên trong của bạn rlRec, nó mang lại cho tôi:

Không bao giờ có công cụ tổng hợp, điều quan trọng là _rlRec là nhãn (mặc dù nó trông giống như hàm) và "cuộc gọi" thành _rlRec trong nhánh thứ hai của khớp mẫu sẽ được biên dịch thành nhảy vào bytecode.

Answer 5

Bạn có thể làm cho đuôi-đệ quy của bạn phiên bản đơn giản như các phiên bản không-đuôi-đệ quy bằng cách sử dụng một đối số mặc định để đưa ra một giá trị ban đầu cho kết quả:

def reverseList[A](list : List[A], result: List[A] = Nil) : List[A] = list match { 
    case Nil => result 
    case (x :: xs) => reverseList(xs, x :: result) 
} 

Mặc dù bạn có thể sử dụng này giống như cách khác, ví dụ: reverseList(List(1,2,3,4)), rất tiếc bạn đang hiển thị chi tiết triển khai với thông số result tùy chọn. Hiện tại dường như không có cách nào để che giấu nó. Điều này có thể hoặc không thể lo lắng cho bạn.

Answer 6

def reverse(n: List[Int]): List[Int] = { 
    var a = n 
    var b: List[Int] = List() 
    while (a.length != 0) { 
    b = a.head :: b 
    a = a.tail 
    } 
    b 
} 

Khi bạn gọi hàm gọi nó là như thế này,

reverse(List(1,2,3,4,5,6)) 

sau đó nó sẽ cho câu trả lời như thế này,

res0: List[Int] = List(6, 5, 4, 3, 2, 1)