Почему минималистский, например, Haskell quicksort не "истинный" quicksort?

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

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

Они также включают "True quicksort in 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 не является истинным quicksort? Как он не масштабируется для более длинных списков?

Ответы

Ответ 1

Истинная quicksort имеет 2 красивых аспекта:

Разделите и победите; разбить проблему на две более мелкие проблемы.
Разделите элементы на месте.

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

Ответ 2

True inplace quicksort в 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

Ответ 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 мутация и доступ к изменяемым переменным являются явными. "Поддельный" qsort привлекателен по разным причинам, но главным среди них является то, что он не использует мутацию; это самоналоженное ограничение облегчает понимание с первого взгляда.

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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

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

Итак, первое, что происходит в этой программе, - это запуск putStrLn.

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

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

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

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

P.P.S. Классический пример алгоритмов Haskell, не приводящих к тому, как вы ожидали, - это сито

Ответ 7

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

Ответ 8

Нет четкого определения того, что есть и что не является истинным quicksort.

Они называют это не настоящим quicksort, потому что он не сортируется на месте:

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

Ответ 9

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

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

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

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

Оптимизируйте до тройной быстрой сортировки (3-полосный раздел, упомянутый Bentley и Sedgewick), для обработки дублированных элементов:
```
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]
```

Объедините 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, 2, 3, 4,...., n]
[n, n-1, n-2,..., 1]
[m-1, m-2,... 3, 2, 1, m + 1, m + 2,..., n]
[n, 1, n-1, 2,...]

Все эти 4 случая хорошо обрабатываются с помощью подхода, соответствующего медианному принципу.

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

Подробные сведения см. в моем текущем письме: https://sites.google.com/site/algoxy/dcsort

Ответ 10

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

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

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

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

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

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

Ответ 11

Поскольку первый элемент из списка приводит к очень плохому времени выполнения. Используйте медиану 3: первый, средний, последний.