Рекурсивный хвост Стиль продолжения Quicksort в Scala

Question

Я пытаюсь написать хвостохранилище в Scala, которое работает, создавая продолжение, без использования батута. До сих пор у меня есть следующий:

object QuickSort { 

    def sort[A: Ordering](toSort: Seq[A]): Seq[A] = { 
    val ordering = implicitly[Ordering[A]] 
    import ordering._ 

    @scala.annotation.tailrec 
    def step(list: Seq[A], conts: List[Seq[A] => Seq[A]]): Seq[A] = list match { 
     case s if s.length <= 1 => conts.foldLeft(s) { case (acc, next) => next(acc) } 
     case Seq(h, tail @ _*) => { 
     val (less, greater) = tail.partition(_ < h) 
     step(less, { sortedLess: Seq[A] => 
      /* 
      Can't use 

      step(greater, sortedGreater => (sortedLess :+ h) ++ sortedGreater) 

      and keep the tailrec annotation 
      */ 
      (sortedLess :+ h) ++ sort(greater) 
     } +: conts) 
     } 
    } 

    step(toSort, Nil) 
    } 

} 

Click for ScalaFiddle

На моем компьютере, выше реализация работает со случайной последовательностью, по меньшей мере, 4000000 элементов, но у меня есть сомнения по этому поводу. В частности, я хотел бы знать:

1. Безопасен ли он? Можем ли мы просто взглянуть на код? Он компилируется с @tailrec, но вызов sort(greater) выглядит несколько подозрительным.
2. Если ответ на (1) - «Нет», можно ли написать хвостовую рекурсивную быструю сортировку в стиле CPS в Scala, то есть без использования батута? Как ?

Чтобы было ясно, я смотрел на this related question, что говорит о том, как реализовать хвост рекурсивной быструю сортировку, используя батуты (который я знаю, как использовать) или собственный явный стек, но я определенно хочу знать, если и как это можно сделать по-другому.

Answer 1

1. Ваш код является рекурсивным, поэтому он должен быть безопасным для стека. Призыв к sort(greater) припаркован в продолжении, он живет на куче, а не на стеке. Учитывая достаточно большую проблему неправильной формы, вы можете взорвать кучу, но это занимает гораздо больше, чем выдувание стека.

Answer 2

Нет, ваш код не является безопасным для стека. sort звонки step и step звонки sort снова в большей части, поэтому он не безопасен для стека.

Для cps, давайте начнем с нормальной форме:

def sort(list: Seq[A]): Seq[A] = list match { 
    case s if s.length <= 1 => s 
    case Seq(h, tail @ _*) => { 
    val (less, greater) = tail.partition(_ < h) 
    val l = sort(less) 
    val g = sort(greater) 
    (l :+ Seq(h)) ++ g 
    } 
} 

Затем перевести его на сП, очень проста:

def sort(list: Seq[A], cont: Seq[A] => Unit): Unit = list match { 
    case s if s.length <= 1 => cont(s) 
    case Seq(h, tail @ _*) => { 
    val (less, greater) = tail.partition(_ < h) 
    sort(less, { l => 
     sort(greater, { g => 
     cont((l :+ Seq(h)) ++ g) 
     }) 
    }) 
    } 
} 

Примечание:

• функция CPS всегда возвращают Unit
• Продолжение alweays return Unit
• Каждый рекурсивный вызов становится вызовом self с операторами while, завернутыми в продолжение.
• возврат стать звоните в продолжение

Наконец, завернуть его в нормальной форме:

def quicksort(list: Seq[A]): Seq[A] = { 
    var result 
    sort(list, { r => result = r }) 
    result 
} 

Примечание: КПС преобразование делает каждую функцию хвостом вызова (NOT хвост-Rec), в Скале Безразлично «т поддержки Оптимизировать хвост вызова, так что вам нужно сделать Оптимизировать хвост вызова вручную:

trait TCF[T] { 
    def result: Option[T] 
    def apply(): TCF[T] 
} 
private def tco[T](f: => TCF[T]): TCF[T] = new TCF[T] { 
    def result = None 
    def apply() = f 
} 

def quicksort[A: Ordering](list: Seq[A]): Seq[A] = { 
    case class Result(r: Seq[A]) extends Exception 
    Iterator.iterate(sort(list, { r: Seq[A] => 
    new TCF[Seq[A]] { 
     def result = Some(r) 
     def apply() = throw new RuntimeException("unreachable") 
    } 
    }))(c => c()).dropWhile(_.result == None).next().result.get 
} 

private def sort[A: Ordering](list: Seq[A], cont: Seq[A] => TCF[Seq[A]]): TCF[Seq[A]] = { 
    val ordering = implicitly[Ordering[A]] 
    import ordering._ 
    list match { 
    case s if s.length <= 1 => tco(cont(s)) 
    case Seq(h, tail@_*) => { 
     val (less, greater) = tail.partition(_ < h) 
     tco(sort(less, { l: Seq[A] => 
     tco(sort(greater, { g: Seq[A] => 
      tco(cont((l :+ h) ++ g)) 
     })) 
     })) 
    } 
    } 
} 

Попробуйте here.

Answer 3

Я решил использовать JVisualVM, чтобы взглянуть на дерево вызовов для реализации, которое у меня было в вопросе, и обнаружил, что он ест стек в результате вызова ++ step(greater). Я думаю, что было очень сложно добраться до того места, где мы будем переполнять поток, потому что список делится каждый раз наполовину, а меньшая половина сортируется хвостом-рекурсивно хвостовым рекурсивным, безопасным стеком.

Подумав об этом немного, я подошел со следующим пересмотренным раствором (попробовать его here)

object QuickSort { 

    def sort[A: Ordering](toSort: Seq[A]): Seq[A] = { 
    val ordering = implicitly[Ordering[A]] 
    import ordering._ 

    // Aliasing allows us to be tail-recursive 
    def step2(list: Seq[A], conts: Vector[Seq[A] => Seq[A]]): Seq[A] = step(list, conts) 

    @scala.annotation.tailrec 
    def step(list: Seq[A], conts: Vector[Seq[A] => Seq[A]]): Seq[A] = list match { 
     case s if s.length <= 1 => conts.foldLeft(s) { case (acc, next) => next(acc) } 
     case Seq(h, tail @ _*) => { 
     val (less, greater) = tail.partition(_ < h) 
     val nextConts: Vector[Seq[A] => Seq[A]] = 
      { sortedLess: Seq[A] => 
      sortedLess :+ h 
      } +: { appendedLess: Seq[A] => 
      step2(greater, Vector({ sortedGreater => appendedLess ++ sortedGreater })) 
      } +: conts 
     step(less, nextConts) 
     } 
    } 
    step(toSort, Vector.empty) 
    } 

} 

Основные отличия:

• Использование step2 псевдоним для step сохранить @tailrec аннотация счастливы.
• Вместо того, чтобы ссылаться на step(greater) в качестве продолжения для сортировки меньшего раздела, мы просто добавляем еще одно продолжение для запуска в накопитель conts, где мы добавляем отсортированный меньший раздел в отсортированный больший раздел. Я полагаю, вы могли бы утверждать, что этот аккумулятор просто стек на куче ..

Интересно, что это решение оказывается довольно быстро, побив решение батуте Scalaz в linked question. Сравнивая его с решением с половинным стеком выше, он был примерно на 30 нс медленнее при сортировке 1 миллиона элементов, но это было ошибкой.

[info] Benchmark        (sortLength) Mode Cnt  Score Error Units 
[info] SortBenchmarks.sort       100 avgt 30  0.034 ± 0.001 ms/op 
[info] SortBenchmarks.sort       10000 avgt 30  6.258 ± 0.072 ms/op 
[info] SortBenchmarks.sort      1000000 avgt 30 1016.849 ± 23.572 ms/op 
[info] SortBenchmarks.scalazSort      100 avgt 30  0.070 ± 0.001 ms/op 
[info] SortBenchmarks.scalazSort     10000 avgt 30 10.426 ± 0.092 ms/op 
[info] SortBenchmarks.scalazSort     1000000 avgt 30 1635.693 ± 68.068 ms/op