[SCALA] "스칼라 프로그래밍"에서 일종의 병합은 스택 오버 플로우가 발생합니다

"스칼라 프로그래밍"에서 일종의 병합은 스택 오버 플로우가 발생합니다

직접 컷은 다음의 알고리즘 붙여 넣기 :

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))
  }
}

5000 개 긴 목록에 StackOverflowError가 발생합니다.

이 발생하지 않도록이 문제를 최적화 할 수있는 방법이 있습니까?

해결법

1. ==============================

   1.이 꼬리 재귀되지 않습니다 때문에이 일을한다. 당신은 나에게 꼬리 재귀함으로써 비 엄격한 컬렉션을 사용하거나이 문제를 해결할 수 있습니다.

   이 꼬리 재귀되지 않습니다 때문에이 일을한다. 당신은 나에게 꼬리 재귀함으로써 비 엄격한 컬렉션을 사용하거나이 문제를 해결할 수 있습니다.

   후자의 솔루션은 다음과 같이 간다 :

   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
     } 
   } 
   

   에 의해 이름 매개 변수를 전달하거나 비 엄격를 포함하여, 또는 스트림과 같은 비 엄격한 컬렉션을 사용. 다음 코드는 다른 곳에서 스택 오버 플로우 및 목록을 방지하기 위해 스트림을 사용합니다 :

   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
     } 
   }
   

2. ==============================

   2.그냥 나는이 질문이 처음 제기되었을 때 주위 아니었다 의심 스칼라의 TailCalls (트램펄린 지원), 놀아. 여기 렉스의 대답에 병합의 재귀 불변의 버전입니다.

   그냥 나는이 질문이 처음 제기되었을 때 주위 아니었다 의심 스칼라의 TailCalls (트램펄린 지원), 놀아. 여기 렉스의 대답에 병합의 재귀 불변의 버전입니다.

   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
   }
   

   실행 단지 빨리 큰 목록에서 변경 가능한 버전은 [긴] (AN I7에 데비안 / 짜기 AMD64) 64 비트 오픈 JDK에 스칼라 2.9.1에이야한다.

3. ==============================

   3.이런 경우에 다니엘의 솔루션은 분명히 충분하지 않았다, 문제는 병합의 재귀 깊은리스트의 길이와 같다이며, 그것이 반복으로 변환 할 수 있도록 꼬리 재귀 아니다.

   이런 경우에 다니엘의 솔루션은 분명히 충분하지 않았다, 문제는 병합의 재귀 깊은리스트의 길이와 같다이며, 그것이 반복으로 변환 할 수 있도록 꼬리 재귀 아니다.

   스칼라는이 약 상응하는 무언가로 다니엘의 꼬리 재귀 병합 솔루션을 변환 할 수 있습니다 :

   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
   }
   

   그러나 그것은 당신을 위해 모든 변수를 추적합니다.

   (A 꼬리 재귀 방법은 방법은 다시 전달하는 완전한 답을 얻기 위해 자신을 호출 하나입니다. 그것은 자신을 호출하지 다음 다시 전달하기 전에 결과로 무언가를 결코 또한, 꼬리 재귀 경우 사용할 수 없습니다 그것은 일반적으로 개체 만 또는 최종 표시 클래스와 함께 작동하도록 방법은 다형성 수 있습니다.)

from https://stackoverflow.com/questions/2201472/merge-sort-from-programming-scala-causes-stack-overflow by cc-by-sa and MIT license