Почему минималистский пример быстрой сортировки Haskell не является «настоящей» быстрой сортировкой?

Question

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

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

Они также включают "Истинная быстрая сортировка в C" ,

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    a[hi] = a[l];
    a[l] = p;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

Ссылка под версией C направляет на страницу со статусом 'Быстрая сортировка, приведенная во введении, не является "реальной" быстрой сортировкой и не масштабируется для более длинных списков, таких как код cделает. '

Почему вышеприведенная функция Haskell не является настоящей быстрой сортировкой?Как не масштабируется для длинных списков?

Answer 1

У настоящей быстрой сортировки есть два прекрасных аспекта:

1. Разделяй и властвуй: разбей проблему на две меньшие проблемы.
2. Разделить элементы на месте.

Короткий пример на Haskell демонстрирует (1), но не (2). Как это делается (2), может быть неочевидно, если вы еще не знаете технику!

Answer 2

Реальная быстрая сортировка на месте в Haskell:

import qualified Data.Vector.Generic as V 
import qualified Data.Vector.Generic.Mutable as M 

qsort :: (V.Vector v a, Ord a) => v a -> v a
qsort = V.modify go where
    go xs | M.length xs < 2 = return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

Answer 3

Вот транслитерация «истинного» кода быстрой сортировки C на Haskell. Готовьтесь.

import Control.Monad
import Data.Array.IO
import Data.IORef

qsort :: IOUArray Int Int -> Int -> Int -> IO ()
qsort a lo hi = do
  (h,l,p,t) <- liftM4 (,,,) z z z z

  when (lo < hi) $ do
    l .= lo
    h .= hi
    p .=. (a!hi)

    doWhile (get l .< get h) $ do
      while ((get l .< get h) .&& ((a.!l) .<= get p)) $ do
        modifyIORef l succ
      while ((get h .> get l) .&& ((a.!h) .>= get p)) $ do
        modifyIORef h pred
      b <- get l .< get h
      when b $ do
        t .=. (a.!l)
        lVal <- get l
        hVal <- get h
        writeArray a lVal =<< a!hVal
        writeArray a hVal =<< get t

    lVal <- get l
    writeArray a hi =<< a!lVal
    writeArray a lVal =<< get p

    hi' <- fmap pred (get l)
    qsort a lo hi'
    lo' <- fmap succ (get l)
    qsort a lo' hi

Это было весело, не так ли? На самом деле я вырезал этот большой let в начале, а также where в конце функции, определяя всех помощников, чтобы сделать предыдущий код несколько симпатичным.

  let z :: IO (IORef Int)
      z = newIORef 0
      (.=) = writeIORef
      ref .=. action = do v <- action; ref .= v
      (!) = readArray
      (.!) a ref = readArray a =<< get ref
      get = readIORef
      (.<) = liftM2 (<)
      (.>) = liftM2 (>)
      (.<=) = liftM2 (<=)
      (.>=) = liftM2 (>=)
      (.&&) = liftM2 (&&)
  -- ...
  where doWhile cond foo = do
          foo
          b <- cond
          when b $ doWhile cond foo
        while cond foo = do
          b <- cond
          when b $ foo >> while cond foo

И вот, тупой тест, чтобы увидеть, работает ли он.

main = do
    a <- (newListArray (0,9) [10,9..1]) :: IO (IOUArray Int Int)
    printArr a
    putStrLn "Sorting..."
    qsort a 0 9
    putStrLn "Sorted."
    printArr a
  where printArr a = mapM_ (\x -> print =<< readArray a x) [0..9]

Я не часто пишу императивный код в Haskell, поэтому я уверен, что есть много способов очистить этот код.

И что?

Вы заметите, что приведенный выше код очень и очень длинный. Суть его примерно такая же, как и в коде на C, хотя каждая строка часто более многословна. Это потому, что C тайно делает много неприятных вещей, которые вы можете принять как должное. Например, a[l] = a[h];. Это обращается к изменяемым переменным l и h, а затем обращается к изменяемому массиву a, а затем изменяет изменяемый массив a. Святая мутация, бэтмен! В Haskell мутация и доступ к изменяемым переменным является явным. «Поддельный» ксорт привлекателен по разным причинам, но главная из них - не использовать мутации; это добровольное ограничение значительно упрощает понимание.

Answer 4

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

Answer 5

Благодаря ленивой оценке программа на Haskell не (почти не может ) делать то, что выглядит так.

Рассмотрим эту программу:

main = putStrLn (show (quicksort [8, 6, 7, 5, 3, 0, 9]))

На нетерпеливом языке сначала запускается quicksort, затем show, затем putStrLn. Аргументы функции вычисляются до ее запуска.

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

Итак, первая вещь, которая происходит в этой программе, заключается в том, что putStrLn начинает работать.

Реализация GHC putStrLn работает путем копирования символов аргумента String в выходной буфер. Но когда он входит в этот цикл, show еще не запущен. Следовательно, когда он копирует первый символ из строки, Haskell вычисляет долю вызовов show и quicksort, необходимых для вычисления этого символа . Затем putStrLn переходит к следующему персонажу. Таким образом, выполнение всех трех функций & mdash; putStrLn, show и quicksort & mdash; чередуется quicksort выполняется постепенно, оставляя график неоцененных thunks , чтобы запомнить, где он остановился.

Теперь это сильно отличается от того, что вы можете ожидать, если вы знакомы с любым другим языком программирования. Нелегко представить, как на самом деле quicksort ведет себя в Haskell с точки зрения доступа к памяти или даже порядка сравнений. Если бы вы могли наблюдать только поведение, а не исходный код, , вы бы не узнали, что он делает, как быструю сортировку .

Например, версия C быстрой сортировки разделяет все данные перед первым рекурсивным вызовом. В версии на Haskell первый элемент результата будет вычислен (и даже может появиться на вашем экране) до того, как будет завершен запуск первого раздела & mdash; действительно, прежде чем вообще будет выполнена какая-либо работа на greater.

P.S. Код на Haskell был бы более похож на quicksort, если бы он выполнял то же число сравнений, что и quicksort; написанный код выполняет в два раза больше сравнений, потому что lesser и greater определены для вычисления независимо, выполняя два линейных сканирования по списку. Конечно, в принципе возможно, чтобы компилятор был достаточно умен, чтобы исключить дополнительные сравнения; или код может быть изменен для использования Data.List.partition.

P.P.S. Классическим примером алгоритмов Хаскелла, который не работает так, как вы ожидали, является сито Эратосфена для вычисления простых чисел.

Answer 6

Я думаю, что аргумент, который пытается использовать этот аргумент, заключается в том, что причина, по которой обычно используется быстрая сортировка, заключается в том, что она на месте и, как следствие, довольно кеширует. Поскольку у вас нет этих преимуществ в списках Haskell, его основной смысл исчез, и вы также можете использовать сортировку слиянием, которая гарантирует O (n log n) , тогда как с быстрой сортировкой вы либо необходимо использовать рандомизацию или сложные схемы разбиения, чтобы избежать O (n ² ) времени выполнения в худшем случае.

Answer 7

Я полагаю, что причина, по которой большинство людей говорят, что симпатичная сортировка Haskell не является «настоящей» быстрой сортировкой, заключается в том, что она не на месте - ясно, что этого не может быть при использовании неизменяемых типов данных. Но есть также возражение, что это не «быстро»: отчасти из-за дорогого ++, а также из-за утечки пространства - вы цепляетесь за список ввода, делая рекурсивный вызов для меньших элементов, и в некоторых случаях - например, когда список уменьшается - это приводит к использованию квадратичного пространства. (Вы можете сказать, что запускать его в линейном пространстве - это самое близкое к «на месте» использование неизменяемых данных.) Существуют аккуратные решения обеих проблем, используя накопление параметров, кортеж и слияние; см. S7.6.1 Ричарда Берда Введение в функциональное программирование с использованием Haskell .

Answer 8

Это не идея мутировать элементы на месте в чисто функциональных настройках.Альтернативные методы в этой теме с изменяемыми массивами утратили дух чистоты.

Существует как минимум два шага для оптимизации базовой версии (которая является наиболее выразительной версией) быстрой сортировки.

1. Оптимизация конкатенации (++), которая является линейной операцией, с помощью аккумуляторов:

   qsort xs = qsort' xs []
   
   qsort' [] r = r
   qsort' [x] r = x:r
   qsort' (x:xs) r = qpart xs [] [] r where
       qpart [] as bs r = qsort' as (x:qsort' bs r)
       qpart (x':xs') as bs r | x' <= x = qpart xs' (x':as) bs r
                              | x' >  x = qpart xs' as (x':bs) r
   

2. Оптимизация для тройной быстрой сортировки (3-стороннее разбиение,упомянутые Бентли и Седжвиком), для обработки дублированных элементов:

   tsort :: (Ord a) => [a] -> [a]
   tsort [] = []
   tsort (x:xs) = tsort [a | a<-xs, a<x] ++ x:[b | b<-xs, b==x] ++ tsort [c | c<-xs, c>x]
   

3. Объедините 2 и 3, обратитесь к книге Ричарда Берда:

   psort xs = concat $ pass xs []
   
   pass [] xss = xss
   pass (x:xs) xss = step xs [] [x] [] xss where
       step [] as bs cs xss = pass as (bs:pass cs xss)
       step (x':xs') as bs cs xss | x' <  x = step xs' (x':as) bs cs xss
                                  | x' == x = step xs' as (x':bs) cs xss
                                  | x' >  x = step xs' as bs (x':cs) xss
   

Или альтернативно, если дублированные элементы не являются большинством:

    tqsort xs = tqsort' xs []

    tqsort' []     r = r
    tqsort' (x:xs) r = qpart xs [] [x] [] r where
        qpart [] as bs cs r = tqsort' as (bs ++ tqsort' cs r)
        qpart (x':xs') as bs cs r | x' <  x = qpart xs' (x':as) bs cs r
                                  | x' == x = qpart xs' as (x':bs) cs r
                                  | x' >  x = qpart xs' as bs (x':cs) r

К сожалению, медиана-тройка не может быть реализована с таким же эффектом, например:

    qsort [] = []
    qsort [x] = [x]
    qsort [x, y] = [min x y, max x y]
    qsort (x:y:z:rest) = qsort (filter (< m) (s:rest)) ++ [m] ++ qsort (filter (>= m) (l:rest)) where
        xs = [x, y, z]
        [s, m, l] = [minimum xs, median xs, maximum xs] 

, поскольку он все еще работает плохо в следующих 4 случаях:

1. [1, 2, 3, 4, ...., n]

2. [n, n-1, n-2, ..., 1]

3. [m-1, m-2, ... 3, 2, 1,m + 1, m + 2, ..., n]

4. [n, 1, n-1, 2, ...]

Все эти 4 случая хорошо обрабатываются с помощью подхода «Медиана-три».

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

Для получения подробной информации, пожалуйста, посетите мою текущую работу по адресу: https://sites.google.com/site/algoxy/dcsort

Answer 9

Нет четкого определения того, что является истинной быстрой сортировкой, а что нет.

Они называют ее не настоящей быстрой сортировкой, поскольку она не сортируется на месте:

Истинная быстрая сортировка в C сортирует на месте

Answer 10

Попросите кого-нибудь написать быструю сортировку на Haskell, и вы получите по сути ту же самую программу - это, очевидно, быстрая сортировка. Вот некоторые преимущества и недостатки:

Pro: улучшена «истинная» быстрая сортировка благодаря стабильности, т. Е. Она сохраняет порядок последовательностей среди равных элементов.

Pro: Обобщение до трехстороннего разбиения (<=>) тривиально, что позволяет избежать квадратичного поведения из-за некоторого значения, встречающегося O (n) раз.

Pro: его легче читать, даже если нужно было включить определение фильтра.

Con: он использует больше памяти.

Con:. Это дорого обобщать выбор поворота путем дальнейшего отбора проб, которые могли бы избежать квадратичного поведения на некоторых низкоэнтропийных порядками