Perché il quicksort Haskell minimalista, ad esempio, non è un quicksort “vero”?

Il sito Web di Haskell introduce una funzione quicksort a 5 linee molto attraente, come mostrato di seguito.

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

= p) xs

Includono anche “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]  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 ); } } 

Un link sotto la versione C indirizza a una pagina che dice ‘Il quicksort citato in Introduzione non è il quicksort “reale” e non scala per elenchi più lunghi come fa il codice C. “

Perché la funzione Haskell di cui sopra non è un vero quicksort? Come non riesce a scalare per liste più lunghe?

Il vero quicksort ha 2 bellissimi aspetti:

  1. Dividere e conquistare; rompere il problema in due problemi minori.
  2. Partizione degli elementi sul posto.

L’esempio breve di Haskell dimostra (1), ma non (2). Come (2) è fatto potrebbe non essere ovvio se non conosci già la tecnica!

Vero quicksort in haskell in Haskell:

 import qualified Data.Vector.Generic as V import qualified Data.Vector.Generic.Mutable as M qsort :: (V.Vector va, Ord a) => va -> va 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 

Ecco una traslitterazione del codice C “quicksort” vero in Haskell. Preparati.

 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 (,,,) zzzz 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 

E 'stato divertente, non è vero? In realtà ho ritagliato questo let grande all'inizio, così come il where alla fine della funzione, definendo tutti gli helper per rendere abbastanza carino il codice precedente.

  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 

E qui, un test stupido per vedere se funziona.

 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 ax) [0..9] 

Non scrivo codice imperativo molto spesso in Haskell, quindi sono sicuro che ci sono molti modi per pulire questo codice.

E allora?

Noterai che il codice sopra è molto, molto lungo. Il cuore di esso è lungo quanto il codice C, anche se ogni riga è spesso un po 'più prolissa. Questo perché C segretamente fa un sacco di cose brutte che potresti dare per scontate. Ad esempio, a[l] = a[h]; . Questo accede alle variabili mutabili l e h , quindi accede alla matrice mutabile a e quindi muta l'array mutabile a . Santa mutazione, batman! In Haskell, la mutazione e l'accesso a variabili mutabili sono esplicite. Il qsort "falso" è attraente per vari motivi, ma il principale tra questi è che non usa la mutazione; questa restrizione autoimposta rende molto più facile capire a colpo d'occhio.

Secondo me, affermare che “non è un vero quicksort” esagera il caso. Penso che sia un’implementazione valida dell’algoritmo Quicksort , solo non particolarmente efficiente.

Penso che il caso che questa argomentazione cerca di fare sia che il motivo per cui quicksort è comunemente usato è che è un posto sul posto e abbastanza cache-friendly come risultato. Dato che non hai questi benefici con gli elenchi di Haskell, la sua principale ragione d’essere è sparita, e potresti anche usare l’ordinamento di fusione, che garantisce O (n log n) , mentre con quicksort devi usare randomizzazione o complicazioni schemi di partizionamento per evitare O (n 2 ) tempo di esecuzione nel peggiore dei casi.

Grazie alla valutazione lazy, un programma Haskell non fa (quasi non può ) fare quello che sembra.

Considera questo programma:

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

In un linguaggio appassionato, il primo quicksort verrebbe eseguito, quindi show , quindi putStrLn . Gli argomenti di una funzione vengono calcolati prima che la funzione inizi a essere eseguita.

In Haskell, è il contrario. La funzione inizia per prima. Gli argomenti vengono calcolati solo quando la funzione li utilizza effettivamente. E un argomento composto, come una lista, è calcolato un pezzo alla volta, dato che ogni parte di esso viene usata.

Quindi la prima cosa che succede in questo programma è che putStrLn inizia a girare.

L’implementazione di putStrLn da parte di putStrLn funziona copiando i caratteri dell’argomento String in un buffer di output. Ma quando entra in questo ciclo, lo show non è ancora stato eseguito. Pertanto, quando va a copiare il primo carattere dalla stringa, Haskell valuta la frazione dello show e le chiamate quicksort necessarie per calcolare quel personaggio . Quindi putStrLn passa al carattere successivo. Quindi l’esecuzione di tutte e tre le funzioni – putStrLn , show e quicksort – è interlacciata. quicksort esegue in modo incrementale, lasciando un grafico di thunks non valutati mentre va a ricordare da dove era stato interrotto.

Ora questo è molto diverso da quello che ci si potrebbe aspettare se si ha familiarità con qualsiasi altro linguaggio di programmazione. Non è facile visualizzare come si comporta effettivamente quicksort in Haskell in termini di accessi alla memoria o persino dell’ordine di confronti. Se si potesse solo osservare il comportamento, e non il codice sorgente, non si riconoscerebbe ciò che sta facendo come quicksort .

Ad esempio, la versione C di quicksort suddivide tutti i dati prima della prima chiamata ricorsiva. Nella versione Haskell, il primo elemento del risultato verrà calcolato (e potrebbe persino apparire sul tuo schermo) prima che la prima partizione abbia finito di funzionare, anzi prima che tutto il lavoro venga eseguito su greater .

PS Il codice Haskell sarebbe più simile a Quicksort se avesse fatto lo stesso numero di confronti di Quicksort; il codice così come scritto fa il doppio dei confronti perché lesser e greater sono specificati per essere calcolati in modo indipendente, facendo due scansioni lineari attraverso l’elenco. Ovviamente è ansible in linea di principio che il compilatore sia abbastanza intelligente da eliminare i confronti extra; oppure il codice potrebbe essere modificato per utilizzare Data.List.partition .

PPS Il classico esempio di algoritmi di Haskell che si rivelano non comportarsi come ci si aspetta è il setaccio di Eratostene per il calcolo dei numeri primi.

Credo che la ragione per la maggior parte della gente sia che il bel Haskell Quicksort non è un “vero” Quicksort è il fatto che non è sul posto – chiaramente, non può essere quando si usano tipi di dati immutabili. Ma c’è anche l’obiezione che non è “veloce”: in parte a causa del costoso ++, e anche perché c’è una perdita di spazio – ci si aggrappa alla lista di input mentre si fa la chiamata ricorsiva sugli elementi minori, e in alcuni casi, ad esempio quando la lista si sta riducendo, questo si traduce in un utilizzo dello spazio quadratico. (Si potrebbe dire che renderlo eseguito in uno spazio lineare è il più vicino che si possa raggiungere “sul posto” utilizzando dati immutabili). Esistono soluzioni chiare a entrambi i problemi, utilizzando parametri di accumulo, tupling e fusione; vedi S7.6.1 di Richard Bird’s Introduzione alla programmazione funzionale usando Haskell .

Non esiste una definizione chiara di cosa sia e cosa non sia un vero quicksort.

Lo chiamano non un vero quicksort, perché non ordina in locale:

True quicksort in C ordina sul posto

Non è l’idea di mutare gli elementi sul posto in contesti puramente funzionali. I metodi alternativi in ​​questo thread con matrici mutevoli hanno perso lo spirito di purezza.

Ci sono almeno due passaggi per ottimizzare la versione base (che è la versione più espressiva) di quick-sort.

  1. Ottimizza la concatenazione (++), che è un’operazione lineare, da accumulatori:

     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. Ottimizza l’ordinamento rapido ternario (partizione a 3 vie, menzionata da Bentley e Sedgewick), per gestire gli elementi duplicati:

     tsort :: (Ord a) => [a] -> [a] tsort [] = [] tsort (x:xs) = tsort [a | a<-xs, ax] 
  3. Combina 2 e 3, fai riferimento al libro di Richard Bird:

     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 

O in alternativa se gli elementi duplicati non sono la maggioranza:

  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 

Sfortunatamente, la mediana di tre non può essere implementata con lo stesso effetto, ad esempio:

  qsort [] = [] qsort [x] = [x] qsort [x, y] = [min xy, max xy] 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] 

perché funziona ancora male per i seguenti 4 casi:

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

Tutti questi 4 casi sono ben gestiti dall’imperativo approccio mediano dei tre.

In realtà, l’algoritmo di ordinamento più adatto per un’impostazione puramente funzionale è ancora merge-sort, ma non quick-sort.

Per i dettagli, visita la mia scrittura in corso all’indirizzo: https://sites.google.com/site/algoxy/dcsort

Chiedete a chiunque di scrivere quicksort in Haskell e otterrete essenzialmente lo stesso programma – ovviamente è quicksort. Ecco alcuni vantaggi e svantaggi:

Pro: Migliora il quicksort “vero” essendo stabile, cioè conserva l’ordine delle sequenze tra gli elementi uguali.

Pro: È banale generalizzare a una suddivisione a tre vie (<=>), che evita il comportamento quadratico a causa di un certo numero di volte O (n).

Pro: È più facile da leggere, anche se è necessario includere la definizione di filtro.

Con: Usa più memoria.

Contro: È costoso generalizzare la scelta del pivot con un ulteriore campionamento, che potrebbe evitare il comportamento quadratico su alcuni ordini a bassa entropia.

Perché prendere il primo elemento dall’elenco comporta un runtime molto brutto. Usa la mediana di 3: primo, medio, ultimo.