Merge sort từ "Lập trình Scala" gây ra stack overflow

Question

Một cắt trực tiếp và dán của thuật toán sau đây:

def msort[T](less: (T, T) => Boolean) 
      (xs: List[T]): List[T] = { 
    def merge(xs: List[T], ys: List[T]): List[T] = 
    (xs, ys) match { 
     case (Nil, _) => ys 
     case (_, Nil) => xs 
     case (x :: xs1, y :: ys1) => 
     if (less(x, y)) x :: merge(xs1, ys) 
     else y :: merge(xs, ys1) 
    } 
    val n = xs.length/2 
    if (n == 0) xs 
    else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs)) 
    } 
} 

gây ra một StackOverflowError trên 5000 danh sách dài.

Có cách nào để tối ưu hóa điều này để điều này không xảy ra không?

Answer 1

Nó đang làm điều này bởi vì nó không phải là đệ quy đuôi. Bạn có thể khắc phục điều này bằng cách sử dụng một bộ sưu tập không nghiêm ngặt hoặc bằng cách làm cho nó trở nên đệ quy.

Giải pháp thứ hai đi như thế này:

def msort[T](less: (T, T) => Boolean) 
      (xs: List[T]): List[T] = { 
    def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] = 
    (xs, ys) match { 
     case (Nil, _) => ys.reverse ::: acc 
     case (_, Nil) => xs.reverse ::: acc 
     case (x :: xs1, y :: ys1) => 
     if (less(x, y)) merge(xs1, ys, x :: acc) 
     else merge(xs, ys1, y :: acc) 
    } 
    val n = xs.length/2 
    if (n == 0) xs 
    else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs), Nil).reverse 
    } 
} 

Sử dụng không nghiêm minh liên quan đến một trong hai truyền tham số theo tên, hoặc sử dụng các bộ sưu tập không nghiêm ngặt như Stream. Các mã sau đây sử dụng Stream chỉ để ngăn chặn tràn ngăn xếp, và List nơi khác:

def msort[T](less: (T, T) => Boolean) 
      (xs: List[T]): List[T] = { 
    def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match { 
    case (x :: xs, y :: ys) if less(x, y) => Stream.cons(x, merge(xs, right)) 
    case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys)) 
    case _ => if (left.isEmpty) right.toStream else left.toStream 
    } 
    val n = xs.length/2 
    if (n == 0) xs 
    else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs)).toList 
    } 
} 

Answer 2

Chỉ trong trường hợp giải pháp Daniel đã không làm cho nó rõ ràng đủ, vấn đề là đệ quy của hợp nhất đó là như sâu như độ dài của danh sách và nó không phải là đệ quy đuôi nên nó không thể được chuyển đổi thành lặp lại.

Scala có thể chuyển đổi giải pháp hợp nhất đuôi-đệ quy Daniel vào một cái gì đó tương đương với điều này:

def merge(xs: List[T], ys: List[T]): List[T] = { 
    var acc:List[T] = Nil 
    var decx = xs 
    var decy = ys 
    while (!decx.isEmpty || !decy.isEmpty) { 
    (decx, decy) match { 
     case (Nil, _) => { acc = decy.reverse ::: acc ; decy = Nil } 
     case (_, Nil) => { acc = decx.reverse ::: acc ; decx = Nil } 
     case (x :: xs1, y :: ys1) => 
     if (less(x, y)) { acc = x :: acc ; decx = xs1 } 
     else { acc = y :: acc ; decy = ys1 } 
    } 
    } 
    acc.reverse 
} 

nhưng nó theo dõi tất cả các biến cho bạn.

(Phương pháp đệ quy đuôi là phương thức chỉ tự gọi để nhận được câu trả lời hoàn chỉnh để trả về; nó không bao giờ tự gọi và sau đó thực hiện điều gì đó với kết quả trước khi truyền lại. không thể được sử dụng nếu phương pháp này có thể đa hình, vì vậy nó thường chỉ hoạt động trong các đối tượng hoặc với các lớp được đánh dấu cuối cùng.)

Answer 3

Chỉ cần chơi xung quanh với sốcủa scala (hỗ trợ trampolining). câu hỏi ban đầu được đặt ra. Đây là phiên bản không thể thay đổi đệ quy của quá trình hợp nhất trong Rex's answer.

import scala.util.control.TailCalls._ 

def merge[T <% Ordered[T]](x:List[T],y:List[T]):List[T] = { 

    def build(s:List[T],a:List[T],b:List[T]):TailRec[List[T]] = { 
    if (a.isEmpty) { 
     done(b.reverse ::: s) 
    } else if (b.isEmpty) { 
     done(a.reverse ::: s) 
    } else if (a.head<b.head) { 
     tailcall(build(a.head::s,a.tail,b)) 
    } else { 
     tailcall(build(b.head::s,a,b.tail)) 
    } 
    } 

    build(List(),x,y).result.reverse 
} 

Chạy cũng nhanh như các phiên bản có thể thay đổi vào độ lớn List[Long] s trên Scala 2.9.1 trên 64bit OpenJDK (Debian/Bóp amd64 trên một i7).