Как вы пишете идиоматическую функцию Scala Quicksort?

Недавно я ответил на question с попыткой написать функцию quicksort в Scala, я видел что-то вроде кода, написанного где-то.

def qsort(l: List[Int]): List[Int] = {
  l match {
    case Nil         => Nil
    case pivot::tail => qsort(tail.filter(_ < pivot)) ::: pivot :: qsort(tail.filter(_ >= pivot))
  }
}

Мой ответ получил некоторую конструктивную критику, указывающую на то, что List был плохим выбором коллекции для быстрой сортировки, а во-вторых, что вышеупомянутое не было хвостом рекурсивным.

Я попытался переписать выше в хвостовой рекурсивной манере, но не имел большой удачи. Можно ли написать хвостовую рекурсивную quicksort? или, если нет, как это можно сделать в функциональном стиле? Также, что можно сделать для максимизации эффективности реализации?

Ответ 1

Несколько лет назад я потратил некоторое время на оптимизацию функциональной быстрой сортировки, насколько мог. Следующее - это то, что я придумал для vanilla List[A]:

def qsort[A : Ordering](ls: List[A]) = {
  import Ordered._

  def sort(ls: List[A])(parent: List[A]): List[A] = {
    if (ls.size <= 1) ls ::: parent else {
      val pivot = ls.head

      val (less, equal, greater) = ls.foldLeft((List[A](), List[A](), List[A]())) {
        case ((less, equal, greater), e) => {
          if (e < pivot)
            (e :: less, equal, greater)
          else if (e == pivot)
            (less, e :: equal, greater)
          else
            (less, equal, e :: greater)
        }
      }

      sort(less)(equal ::: sort(greater)(parent))
    }
  }
  sort(ls)(Nil)
}

Я смог сделать еще лучше с пользовательской структурой List. Эта настраиваемая структура в основном отслеживала идеальную (или почти идеальную) опорную точку для списка. Таким образом, я мог бы получить гораздо лучший опорный момент в постоянное время, просто получив доступ к этому специальному свойству списка. На практике это было намного лучше, чем стандартный функциональный подход к выбору головы.

Как бы то ни было, вышеупомянутое все еще довольно быстро. Это "половина" хвоста рекурсивно (вы не можете делать хвостовую рекурсивную сортировку без получения уродливости). Что еще более важно, он сначала восстанавливается с конца хвоста, так что результаты значительно меньше промежуточных списков, чем обычный подход.

Важно отметить, что это не самый элегантный или самый идиоматический способ делать quicksort в Scala, он просто работает очень хорошо. Вероятно, у вас будет больше успеха при создании слияния, что обычно является гораздо более быстрым алгоритмом при реализации на функциональных языках (не говоря уже о более чистом).

Ответ 2

Я думаю, это зависит от того, что вы подразумеваете под "идиоматическим". Основным преимуществом быстрой сортировки является очень быстрый алгоритм сортировки на месте. Таким образом, если вы не можете сортировать на месте, вы потеряете все свои преимущества, но вы все еще придерживаетесь этих преимуществ.

Итак, вот какой код я написал для Rosetta Code по этому самому вопросу. Он по-прежнему не сортируется на месте, но, с другой стороны, он сортирует любые новые коллекции:

import scala.collection.TraversableLike
import scala.collection.generic.CanBuildFrom
def quicksort
  [T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]]      // My type parameters -- which are expected to be inferred
  (coll: CC[T])                                                    // My explicit parameter -- the one users will actually see
  (implicit ord: Ordering[T], cbf: CanBuildFrom[CC[T], T, CC[T]])  // My implicit parameters -- which will hopefully be implicitly available
  : CC[T] =                                                        // My return type -- which is the very same type of the collection received
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll.tail partition (ord.lt(_, coll.head))
    quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)
  }

Ответ 3

Как бы то ни было, я попытался решить эту ту же проблему в последнее время. Я хотел иметь классический алгоритм (т.е. Тот, который выполняет сортировку на месте), преобразованный в хвостовую рекурсивную форму.

Если вы все еще заинтересованы, вы можете увидеть мое рекомендуемое решение здесь:

Quicksort переписан в хвостовой рекурсивной форме - пример в Scala

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

Ответ 4

Я сделал несколько экспериментов, пытаясь написать Quicksort в чисто функциональном стиле. Вот что я получил (Quicksort.scala):

def quicksort[A <% Ordered[A]](list: List[A]): List[A] = {
  def sort(t: (List[A], A, List[A])): List[A] = t match {
    case (Nil, p, Nil) => List(p)
    case (l, p, g) =>  partitionAndSort(l) ::: (p :: partitionAndSort(g))
  }

  def partition(as: List[A]): (List[A], A, List[A]) = {
    def loop(p: A, as: List[A], l: List[A], g: List[A]): (List[A], A, List[A]) = 
      as match {
        case h :: t => if (h < p) loop(p, t, h :: l, g) else loop(p, t, l, h :: g)
        case Nil => (l, p, g)
      }

    loop(as.head, as.tail, Nil, Nil)
  }

  def partitionAndSort(as: List[A]): List[A] = 
    if (as.isEmpty) Nil
    else sort(partition(as))

  partitionAndSort(list)
}