Pourquoi est minimaliste, exemple Haskell quicksort pas un "vrai" quicksort?

Question

Haskell site présente un très beau 5 ligne quicksort fonction, comme on le voit ci-dessous.

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

Ils comprennent également un "Vrai quicksort en 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 );
  }
}

Un lien ci-dessous, la version C dirige vers une page que les états "Le quicksort cité en Introduction n'est pas le "vrai" quicksort et n'a pas d'échelle pour les longues listes telles que le code c n'.'

Pourquoi est-le au-dessus de Haskell fonction pas un vrai quicksort? Comment est-il échouer à l'échelle pour plus de listes?

EDIT: Voici le lien où ce quicksort définition peut être trouvé. http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell

Answer 1

Le vrai quicksort a 2 beaux aspects:

1. Diviser pour régner; diviser le problème en deux petits problèmes.
2. Partition les éléments en place.

Le court Haskell montre l'exemple (1), mais pas (2). Comment (2) est fait ne peut pas être évident si vous ne la connaissez pas la technique!

Answer 2

Véritable place de quicksort en 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

Première (mauvaise) version:

import Data.Vector.Generic
import qualified Data.Vector.Generic.Mutable as M 

iqsort :: (Vector v a, Ord a) => v a -> v a
iqsort = modify go where
         go xs  | len < 2   = return ()
                | otherwise = do
                    p <- xs `M.read` (len `div` 2)
                    m <- M.unstablePartition (< p) xs
                    go $ M.slice 0     m         xs
                    go $ M.slice (m+1) (len-m-1) xs
                where len = M.length xs

Answer 3

Voici une translittération de la "vraie" quicksort code C en Haskell. Accrochez-vous.

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

C'était amusant, n'est-ce pas? J'ai fait découper ce grand let au début, ainsi que l' where à la fin de la fonction, la définition de l'ensemble des aides pour rendre le code précédent un peu assez.

  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

Et ici, un muet test pour voir si elle fonctionne.

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]

Je n'écris pas de code impératif très souvent en Haskell, donc je suis sûr qu'il ya beaucoup de façons de nettoyer le présent code.

Et alors?

Vous remarquerez que le code ci-dessus est très, très longtemps. Le cœur est à peu près aussi longtemps que le code C, bien que chaque ligne est souvent un peu plus verbeux. C'est parce que C secrètement fait beaucoup de choses désagréables que vous pourriez prendre pour acquis. Par exemple, a[l] = a[h];. Cette accède à la mutable variables l et h, puis accède à la mutable tableau a, puis se transforme le mutable tableau a. Saint mutation, batman! En Haskell, la mutation et l'accès mutable variables est explicite. Le "faux" qsort est attrayant pour diverses raisons, mais la principale d'entre elles est qu'il n'utilise pas de mutation; cette auto-restriction imposée rend beaucoup plus facile à comprendre en un clin d'œil.

Answer 4

À mon avis, en disant que ce n'est "pas un vrai quicksort" est exagéré. Je pense que c'est une bonne mise en œuvre de l' algorithme Quicksort, juste pas particulièrement efficace.

Answer 5

Je pense que le cas de cet argument essaie de faire, c'est que la raison pour laquelle quicksort est couramment utilisé est qu'il est en place et assez de cache-friendly. Puisque vous n'avez pas ces avantages avec Haskell listes, sa principale raison d'être a disparu, et vous pourriez aussi bien utiliser de fusion, ce qui garantit O(n log n), alors qu'avec quicksort soit vous devez utiliser la randomisation ou compliqué schémas de partitionnement pour éviter de O(n²) temps d'exécution dans le pire des cas.