Dlaczego minimalistyczny, na przykład Haskell quicksort, nie jest „prawdziwym” quicksort?

118

Witryna Haskell wprowadza bardzo atrakcyjną 5-wierszową funkcję szybkiego sortowania , jak widać poniżej.

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

Obejmują również „Prawdziwe szybkie sortowanie w 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 );
  }
}

Odnośnik pod wersją C kieruje do strony, na której stwierdza się: „Quicksort cytowany we wstępie nie jest„ prawdziwym ”quicksort i nie skaluje się dla dłuższych list, jak robi to kod c.

Dlaczego powyższa funkcja Haskell nie jest prawdziwym szybkim sortowaniem? Jak to się nie udaje przy dłuższych listach?

rybosome
źródło
Powinieneś dodać link do dokładnej strony, o której mówisz.
Staven
14
Nie jest na miejscu, więc jest dość powolny? Właściwie dobre pytanie!
fuz
4
@FUZxxl: Listy Haskell są niezmienne, więc żadna operacja nie będzie wykonywana podczas korzystania z domyślnych typów danych. Co do szybkości - niekoniecznie będzie wolniejsza; GHC to imponujący element technologii kompilatora i bardzo często rozwiązania haskell wykorzystujące niezmienne struktury danych są tak szybkie, jak inne, zmienne w innych językach.
Callum Rogers
1
Czy to właściwie nie jest qsort? Pamiętaj, że qsort ma O(N^2)środowisko uruchomieniowe .
Thomas Eding
2
Należy zauważyć, że powyższy przykład jest wprowadzającym przykładem Haskella i że quicksort jest bardzo złym wyborem do sortowania list. Sortowanie w Data.List zostało zmienione na scalanie w 2002 roku: hackage.haskell.org/packages/archive/base/3.0.3.1/doc/html/src/… , można tam również zobaczyć poprzednią implementację szybkiego sortowania. Obecna implementacja jest połączeniem wykonanym w 2009 roku: hackage.haskell.org/packages/archive/base/4.4.0.0/doc/html/src/… .
HaskellElephant

Odpowiedzi:

75

Prawdziwy quicksort ma dwa piękne aspekty:

  1. Dziel i rządź: podziel problem na dwa mniejsze problemy.
  2. Podziel elementy w miejscu.

Krótki przykład Haskella pokazuje (1), ale nie (2). Sposób wykonania (2) może nie być oczywisty, jeśli nie znasz jeszcze techniki!

poklepać
źródło
17
informit.com/articles/article.aspx?p=1407357&seqNum=3 - Andrey Alexandrescu
The_Ghost
Aby uzyskać jasny opis procesu partycjonowania w miejscu, zobacz Interactivepython.org/courselib/static/pythonds/SortSearch/… .
pvillela
57

Prawdziwe szybkie sortowanie w miejscu w 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
klapaucius
źródło
Źródło dla unstablePartition ujawnia, że ​​jest to rzeczywiście ta sama technika zamiany w miejscu (o ile wiem).
Dan Burton,
3
To rozwiązanie jest nieprawidłowe. unstablePartitionjest bardzo podobny do partitionfor quicksort, ale nie gwarantuje, że element na mtej pozycji jest sprawiedliwy p.
nymk
29

Oto transliteracja „prawdziwego” kodu szybkiego sortowania C na Haskell. Przygotuj się.

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

To było zabawne, prawda? Właściwie wyciąłem ten duży letna początku, a także plikwhere na końcu funkcji, definiując wszystkich pomocników, aby poprzedni kod był nieco ładny.

  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

A tutaj głupi test, aby sprawdzić, czy to działa.

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]

Nie piszę zbyt często kodu imperatywnego w Haskell, więc jestem pewien, że jest wiele sposobów na wyczyszczenie tego kodu.

Więc co?

Zauważysz, że powyższy kod jest bardzo, bardzo długi. Jej sercem jest prawie tak długi, jak kod C, chociaż każda linia jest często nieco bardziej szczegółowa. Dzieje się tak, ponieważ C potajemnie robi wiele paskudnych rzeczy, które możesz wziąć za pewnik. Na przykład a[l] = a[h];. Ten dostęp zmienne zmienny li h, a następnie uzyskuje dostęp do tablicy zmienny a, a następnie mutuje się zmienny układ a. Święta mutacja, batmanie! W Haskell mutacja i dostęp do zmiennych zmiennych są jawne. „Fałszywy” qsort jest atrakcyjny z różnych powodów, ale głównym z nich jest to, że nie wykorzystuje mutacji; to samo narzucone ograniczenie znacznie ułatwia zrozumienie na pierwszy rzut oka.

Dan Burton
źródło
3
To niesamowite, w pewien sposób powodujący mdłości. Zastanawiam się, jaki rodzaj kodu tworzy GHC z czegoś takiego?
Ian Ross
@IanRoss: Od nieczystego szybkiego sortowania? GHC faktycznie tworzy całkiem przyzwoity kod.
JD
„Fałszywy” qsort jest atrakcyjny z różnych powodów… „Obawiam się, że jego działanie bez manipulacji w miejscu (jak już wspomniano) byłoby okropne. I zawsze przyjmowanie pierwszego elementu jako obrotu również nie pomaga.
dbaltor
25

Moim zdaniem stwierdzenie, że to „nie jest prawdziwy szybki przegląd”, przesadza. Myślę, że jest to poprawna implementacja algorytmu Quicksort , ale nie jest to szczególnie wydajna.

Keith Thompson
źródło
9
Kiedyś pokłóciłem się z kimś: wyszukałem rzeczywisty dokument, który określał QuickSort i rzeczywiście jest na miejscu.
ivanm
2
Hiperłącza @ivanm albo to się nie stało :)
Dan Burton,
1
Uwielbiam to, że ten artykuł jest niezbędny, a nawet zawiera sztuczkę gwarantującą użycie przestrzeni logarytmicznej (o której wiele osób nie wie), podczas gdy (teraz popularna) rekurencyjna wersja w ALGOL to tylko przypis. Chyba będę musiał teraz poszukać innego papieru ... :)
hugomg
6
„Prawidłowa” implementacja dowolnego algorytmu powinna mieć takie same asymptotyczne granice, nie sądzisz? Bastardized Haskell quicksort nie zachowuje żadnej złożoności pamięci pierwotnego algorytmu. Nawet nie blisko. Dlatego jest ponad 1000 razy wolniejszy niż prawdziwy Quicksort Sedgewicka w C.
JD
16

Myślę, że argument, który próbuje przedstawić ten argument, polega na tym, że powodem, dla którego często używa się quicksort, jest to, że jest on na miejscu i w rezultacie dość przyjazny dla pamięci podręcznej. Ponieważ nie masz tych korzyści z listami Haskella, jego główna racja bytu zniknęła i równie dobrze możesz użyć sortowania przez scalanie, które gwarantuje O (n log n) , podczas gdy w przypadku szybkiego sortowania musisz użyć randomizacji lub skomplikowanego schematy partycjonowania w celu uniknięcia czasu wykonywania O (n 2 ) w najgorszym przypadku.

hammar
źródło
5
A Mergesort jest znacznie bardziej naturalnym algorytmem sortowania (niezmiennych) list polubionych, w którym jest wolny od konieczności pracy z tablicami pomocniczymi.
hugomg
16

Dzięki leniwej ocenie program Haskell nie (prawie nie może ) robić tego, na co wygląda.

Rozważ ten program:

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

W gorliwym języku najpierw quicksortbiegał show, potemputStrLn . Argumenty funkcji są obliczane przed uruchomieniem tej funkcji.

W Haskell jest odwrotnie. Funkcja jest uruchamiana jako pierwsza. Argumenty są obliczane tylko wtedy, gdy funkcja faktycznie ich używa. Argument złożony, taki jak lista, jest obliczany po jednym fragmencie, gdy jest używany.

Więc pierwszą rzeczą, która dzieje się w tym programie, jest to, że putStrLnzaczyna działać.

Implementacja GHCputStrLn działa poprzez kopiowanie znaków argumentu String do bufora wyjściowego. Ale kiedy wchodzi w tę pętlę, showjeszcze nie działa. Dlatego też, kiedy zamierza skopiować pierwszy znak z ciągu, Haskell ocenia ułamek wywołań showi quicksortpotrzebnych do obliczenia tego znaku . Następnie putStrLnprzechodzi do następnego znaku. Zatem wykonanie wszystkich trzech funkcji putStrLn- show, i quicksort- jest przeplatane. quicksortwykonuje się przyrostowo, pozostawiając wykres nieocenionych fragmentów w miarę zapamiętywania miejsca, w którym zostało przerwane.

To bardzo różni się od tego, czego można by się spodziewać, jeśli znasz, wiesz, jakikolwiek inny język programowania. Nie jest łatwo wyobrazić sobie, jak quicksortfaktycznie zachowuje się Haskell pod względem dostępu do pamięci, a nawet kolejności porównań. Gdybyś mógł tylko obserwować zachowanie, a nie kod źródłowy, nie rozpoznałbyś tego, co robi jako szybki sort .

Na przykład wersja C quicksort dzieli na partycje wszystkie dane przed pierwszym wywołaniem rekurencyjnym. W wersji Haskell, pierwszy element wyniku zostanie obliczony (i może nawet pojawić się na ekranie) przed zakończeniem działania pierwszej partycji - a właściwie przed wykonaniem jakiejkolwiek pracy greater.

PS Kod Haskell byłby bardziej podobny do szybkiego sortowania, gdyby wykonywał taką samą liczbę porównań jak w przypadku szybkiego sortowania; napisany kod wykonuje dwa razy więcej porównań, ponieważ lesseri greatersą określone do obliczania niezależnie, wykonując dwa liniowe skanowanie listy. Oczywiście w zasadzie kompilator może być wystarczająco inteligentny, aby wyeliminować dodatkowe porównania; lub kod można zmienić do użycia Data.List.partition.

PPS Klasycznym przykładem algorytmów Haskella, które okazały się nie zachowywać się zgodnie z oczekiwaniami, jest sito Eratostenesa do obliczania liczb pierwszych.

Jason Orendorff
źródło
2
lpaste.net/108190 . - zajmuje się „sortowaniem wylesionych drzew”, jest na ten temat stary wątek redditowy . por. stackoverflow.com/questions/14786904/ ... i powiązane.
Will Ness
1
wygląda Tak, to całkiem dobra charakterystyka tego, co program faktycznie robi.
Jason Orendorff
Jeśli chodzi o uwagę na sicie, gdyby była napisana jako ekwiwalent primes = unfoldr (\(p:xs)-> Just (p, filter ((> 0).(`rem` p)) xs)) [2..], jej najpilniejszy problem byłby być może jaśniejszy. I to zanim rozważymy przejście na algorytm prawdziwego sita.
Will Ness
Jestem zdezorientowany twoją definicją tego, jaki kod „wygląda jak działa”. Twój kod „wygląda” dla mnie tak, jakby wywoływał, z putStrLnktórej aplikacji showzmyślonej, lub z aplikacji, quicksortdo listy - i to jest dokładnie to, co robi! (przed optymalizacją --- ale czasami porównaj kod C ze zoptymalizowanym asemblerem!). Może masz na myśli „dzięki leniwej ocenie, program Haskell nie robi tego, co podobnie wyglądający kod robi w innych językach”?
Jonathan Cast
4
@jcast Myślę, że pod tym względem istnieje praktyczna różnica między C i Haskellem. Naprawdę ciężko jest prowadzić przyjemną debatę na ten temat w komentarzu, tak bardzo, jak bardzo chciałbym wypowiedzieć ją przy kawie w prawdziwym życiu. Daj mi znać, jeśli kiedykolwiek będziesz w Nashville z godziną do stracenia!
Jason Orendorff,
12

Uważam, że powodem, dla którego większość ludzi twierdzi, że ładny Haskell Quicksort nie jest „prawdziwym” Quicksort, jest fakt, że nie jest on na miejscu - oczywiście nie może tak być, gdy używa się niezmiennych typów danych. Ale jest też zastrzeżenie, że nie jest to „szybkie”: częściowo z powodu drogiego ++, a także z powodu wycieku spacji - trzymasz się listy wejściowej podczas wykonywania rekurencyjnego wywołania mniejszych elementów i w niektórych przypadkach - np. gdy lista jest malejąca - powoduje to kwadratowe wykorzystanie przestrzeni. (Można powiedzieć, że sprawienie, by działał w przestrzeni liniowej, jest najbliższym osiągnięciem „w miejscu” przy użyciu niezmiennych danych.) Istnieją zgrabne rozwiązania obu problemów, wykorzystując akumulację parametrów, kręcenie i fuzję; patrz S7.6.1 książki Richard Bird '

Jeremy Gibbons
źródło
4

To nie jest idea mutowania elementów na miejscu w czysto funkcjonalnych warunkach. Alternatywne metody w tym wątku z zmiennymi tablicami straciły ducha czystości.

Istnieją co najmniej dwa kroki, aby zoptymalizować podstawową wersję (która jest najbardziej wyrazistą wersją) szybkiego sortowania.

  1. Zoptymalizuj konkatenację (++), która jest operacją liniową, przez akumulatory:

    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. Zoptymalizuj do trójskładnikowego szybkiego sortowania (trójdrożna partycja, o której wspominają Bentley i Sedgewick), aby obsługiwać zduplikowane elementy:

    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. Połącz 2 i 3, patrz książka Richarda Birda:

    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

Lub alternatywnie, jeśli zduplikowane elementy nie stanowią większości:

    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

Niestety, mediana-trzech nie może zostać zaimplementowana z takim samym skutkiem, na przykład:

    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] 

ponieważ nadal działa słabo w następujących 4 przypadkach:

  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, ...]

Wszystkie te 4 przypadki są dobrze obsługiwane przez imperatywną metodę mediany z trzech.

W rzeczywistości najbardziej odpowiednim algorytmem sortowania dla czysto funkcjonalnego ustawienia jest nadal sortowanie przez scalanie, ale nie sortowanie szybkie.

Aby uzyskać szczegółowe informacje, zapoznaj się z moim ciągłym pisaniem pod adresem : https://sites.google.com/site/algoxy/dcsort

Larry LIU Xinyu
źródło
Jest jeszcze jedna optymalizacja, którą przegapiłeś: użyj partycji zamiast 2 filtrów, aby utworzyć podlistę (lub foldr na podobnej funkcji wewnętrznej, aby utworzyć 3 listy podrzędne).
Jeremy Lista
3

Nie ma jasnej definicji tego, co jest, a co nie jest prawdziwym szybkim sortowaniem.

Nazywają to nie prawdziwym szybkim sortowaniem, ponieważ nie sortuje na miejscu:

Prawdziwe szybkie sortowanie w C. na miejscu

Piotr Praszmo
źródło
-1

Ponieważ pobranie pierwszego elementu z listy skutkuje bardzo złym działaniem. Użyj mediany 3: pierwsza, środkowa, ostatnia.

Joshua
źródło
2
Wzięcie pierwszego elementu jest w porządku, jeśli lista jest losowa.
Keith Thompson
2
Ale sortowanie posortowanej lub prawie posortowanej listy jest powszechne.
Joshua
7
Ale qsort IS O(n^2)
Thomas Eding
8
qsort to średnia n log n, najgorsza n ^ 2.
Joshua
3
Z technicznego punktu widzenia nie jest to gorsze niż wybranie losowej wartości, chyba że dane wejściowe są już posortowane lub prawie posortowane. Złe pivoty to osie, które są oddalone od mediany; pierwszy element jest tylko złym obrotem, jeśli jest bliski minimum lub maksimum.
Platinum Azure
-1

Poproś kogokolwiek o napisanie quicksort w Haskell, a otrzymasz zasadniczo ten sam program - jest to oczywiście quicksort. Oto kilka zalet i wad:

Pro: Poprawia "prawdziwego" szybkiego sortowania poprzez bycie stabilnym, tj. Zachowuje kolejność między równymi elementami.

Zaleta: Uogólnienie do podziału na trzy części (<=>), który pozwala uniknąć zachowania kwadratowego z powodu pewnej wartości występującej O (n) razy, jest trywialne.

Pro: Jest łatwiejszy do odczytania - nawet gdyby trzeba było uwzględnić definicję filtra.

Wada: zużywa więcej pamięci.

Wada: Kosztowne jest uogólnianie wyboru obrotu przez dalsze próbkowanie, co mogłoby uniknąć zachowania kwadratowego na niektórych uporządkowaniach o niskiej entropii.

mercator
źródło