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

правда на месте быстрой сортировки на 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

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

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

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

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

считайте эту программу:

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

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

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

так первый то, что происходит в этой программе, это putStrLn начинает работать.

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

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

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

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

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

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

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

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

True quicksort в C сортирует на месте

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

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

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-полосная перегородка, упомянутая 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]
   

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

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

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

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

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

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

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

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