StackOverflowError для mergesort в scala

Question

Я реализовал нижеследующий код слияния. Но я получаю stackOverFlowError в процедуре слияния алгоритма, когда число целых чисел достигает 100000. Я использую сопоставление шаблонов с рекурсией для процедуры слияния. Я понимаю, что использование рекурсии для процедуры слияния не является оптимальным, учитывая, что глубина для этого входа будет достигать 50000. Но поскольку я использую scala, я ожидал некоторой оптимизации компилятора, чтобы сделать рекурсивные вызовы итеративными, поскольку это хвостовые рекурсивные вызовы , Не могли бы вы помочь мне понять, почему я все еще получаю StackOverFlowerror в приведенном ниже коде? Просьба представить информацию о том, как я могу написать это более эффективно в scala? Ниже приведен код:

package common 

object Merge { 
    def main(args: Array[String]) = { 
    val source = scala.io.Source.fromFile("IntegerArray.txt") 
    val data = source.getLines.map {line => line.toInt}.toList 
    println(data.length) 
    val res = mergeSort(data) 
    println(res) 
    } 
    def mergeSort(data: List[Int]): List[Int] = { 
    if(data.length <= 1) {data } 
    else { 
     val mid = (data.length)/2 
     val (l, r) = data.splitAt(mid) 
     val l1 = mergeSort(l) 
     val l2 = mergeSort(r) 
     merge(l1, l2) 
    } 
    } 

    def merge(l: List[Int], r: List[Int]): List[Int] = { 
    l match { 
     case List() => r 
     case x::xs => { 
     r match { 
      case List() => l 
      case y::ys => { 
      if(x<y) { 
       x :: merge(xs, r) 
      } else { 
       y :: merge(l, ys) 
      } 
      } 
     } 
     } 
    } 
    } 
} 

Ниже исключение я получаю:

Exception in thread "main" java.lang.StackOverflowError 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:30) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:32) 
    at common.Merge$.merge(Merge.scala:30) 

Answer 1

Merge сортировка должна быть рекурсивными, но это не проблема, так как это O (журнал N). Метод merge должен быть оптимизирован для цикла, так как он равен O (n).

Оптимизация TailRec работает только тогда, когда рекурсивный вызов является последней командой, в последнем случае последней командой является конкатенация списка (или добавление).

Вы можете добавить аннотацию @tailrec. Компилятор всегда будет пытаться оптимизировать, но таким образом он даст вам знать, не может ли он этого сделать.

merge(l1, l2, Nil) 
    ... 

    @tailrec 
    def merge(l: List[Int], r: List[Int], acc: List[Int]): List[Int] = { 
    l match { 
     case List() => acc ::: r 
     case x::xs => { 
     r match { 
      case List() => acc ::: l 
      case y::ys => { 
      val (item, lTail, rTail) = 
       if(x<y) (x, xs, r) 
       else (y, l, ys) 
      merge(lTail, rTail, acc:::List(item)) 
      } 
     } 
     } 
    } 
    } 

Стратегия заключается в использовании аккумулятора для результата и в базовом случае вернуть аккумулятор вместо списка Nil. Таким образом, компилятор может сделать оптимизацию TailRec.

Также рассмотреть написание кода, как это:

@tailrec 
    def merge(l: List[Int], r: List[Int], acc: List[Int]): List[Int] = { 
    if (l.isEmpty) acc ::: r 
    else if (r.isEmpty) acc ::: l 
    else { 
     val (item, lTail, rTail) = 
     if (l.head<r.head) (l.head, l.tail, r) 
     else (r.head, l, r.tail) 
     merge(lTail, rTail, acc:::List(item)) 
    } 
    } 

Я нахожу этот способ проще и легче понять.

Также обратите внимание, что хвостовой рекурсивный вызов не должен быть только одним в конце, как показано в предыдущих примерах, поэтому вы можете вернуться к своим предыдущим вызовам if-else, пока рекурсивные вызовы являются последними каждая ветвь:

@tailrec 
    def merge(l: List[Int], r: List[Int], acc: List[Int]): List[Int] = { 
    if (l.isEmpty) acc ::: r 
    else if (r.isEmpty) acc ::: l 
    else { 
     if (l.head < r.head) 
     merge(l.tail, r, acc ::: List(l.head)) 
     else 
     merge(l, r.tail, acc ::: List(r.head)) 
    } 
    } 

Answer 2

вы можете также соответствовать кортежей:

def merge(l: List[Int], r: List[Int], acc: List[Int]): List[Int] = (l,r) match { 
    case (lh :: lt, rh :: rt) => 
     if (lh < rh) 
      merge(lt, r, lh :: acc) 
     else 
      merge(l, rt, rh :: acc) 
    case _ => acc.reverse ::: l ::: r 
} 

Если вы набираете в обратном направлении, ваше время работы не будет зависеть от того, насколько эффективным ::: реализуется, и вы получите ваш O(n)