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

Question

Я недавно ответил на вопрос , пытаясь написать функцию быстрой сортировки в 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 был плохим выбором для быстрой сортировки и, во-вторых, вышеописанное не было хвостовой рекурсивностью.

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

Answer 1

Несколько лет назад я потратил некоторое время, пытаясь максимально оптимизировать функциональную быструю сортировку. Вот что я придумал для ванили 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. Эта пользовательская структура в основном отслеживала идеальную (или почти идеальная) опорную точку для списка. Таким образом, я мог бы получить гораздо лучшую точку поворота в постоянное время, просто используя этот специальный список свойств. На практике это немного лучше, чем стандартный функциональный подход к выбору головы.

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

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

Answer 2

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

Итак, вот код, который я написал для 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)
  }

Answer 3

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

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

Быстрая сортировка, переписанная в хвостовой рекурсивной форме - пример в Scala

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

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