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

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?

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!

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

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.

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.

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 ² ) w najgorszym przypadku.

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.

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 '

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

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

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

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.