Pourquoi le tri rapide minimaliste, par exemple Haskell, n'est-il pas un «vrai» tri rapide?

Le site Web de Haskell présente une fonction de tri rapide en 5 lignes très attrayante , comme illustré ci-dessous.

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

Ils incluent également un "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] <= 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 sous la version C dirige vers une page qui indique "Le tri rapide cité dans l'introduction n'est pas le" vrai "tri rapide et ne s'adapte pas aux listes plus longues comme le fait le code c."

Pourquoi la fonction Haskell ci-dessus n'est-elle pas un véritable tri rapide? Comment échoue-t-il à évoluer pour des listes plus longues?

Le vrai tri rapide a deux beaux aspects:

1. Divisez pour vaincre: divisez le problème en deux problèmes plus petits.
2. Partitionnez les éléments sur place.

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

Véritable tri rapide sur place dans 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

Voici une translittération du "vrai" code C de tri rapide en Haskell. Préparez 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, non? En fait, j'ai coupé ce gros letau début, ainsi qu'à la wherefin de la fonction, définissant tous les helpers pour rendre le code précédent assez joli.

  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 test stupide pour voir si ça marche.

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 existe de nombreuses façons de nettoyer ce code.

Et alors?

Vous remarquerez que le code ci-dessus est très, très long. Le cœur de celui-ci est à peu près aussi long que le code C, bien que chaque ligne soit souvent un peu plus verbeuse. C'est parce que C fait secrètement beaucoup de choses désagréables que vous pourriez prendre pour acquises. Par exemple a[l] = a[h];,. Cela accède aux variables mutables let h, puis accède au tableau mutable a, puis mute le tableau mutable a. Sainte mutation, batman! Dans Haskell, la mutation et l'accès aux variables mutables sont explicites. Le "faux" qsort est attrayant pour diverses raisons, mais la principale d'entre elles est qu'il n'utilise pas de mutation; cette restriction auto-imposée le rend beaucoup plus facile à comprendre en un coup d'œil.

À mon avis, dire que ce n'est "pas un vrai tri rapide" exagère le cas. Je pense que c'est une implémentation valide de l' algorithme Quicksort , mais pas particulièrement efficace.

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

Grâce à l'évaluation paresseuse, un programme Haskell ne le fait pas (presque pas ) ce qu'il semble faire.

Considérez ce programme:

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

Dans une langue enthousiaste, d'abord quicksort courrait, puis show, puis putStrLn. Les arguments d'une fonction sont calculés avant que cette fonction ne commence à s'exécuter.

Dans Haskell, c'est le contraire. La fonction démarre en premier. Les arguments ne sont calculés que lorsque la fonction les utilise réellement. Et un argument composé, comme une liste, est calculé un morceau à la fois, car chaque morceau est utilisé.

Donc, la première chose qui se passe dans ce programme est queputStrLn démarre.

L'implémentation de GHCputStrLn fonctionne en copiant les caractères de l'argument String dans un tampon de sortie. Mais quand il entre dans cette boucle, shown'a pas encore exécuté. Par conséquent, lorsqu'il va copier le premier caractère de la chaîne, Haskell évalue la fraction des appels showet quicksortnécessaires pour calculer ce caractère . Puis putStrLnpasse au personnage suivant. Ainsi , l'exécution des trois fonctions- putStrLn, showet quicksort- est entrelacée. quicksorts'exécute de manière incrémentielle, laissant un graphique de thunks non évalués pendant qu'il se souvient où il s'est arrêté.

Maintenant, c'est très différent de ce à quoi vous pourriez vous attendre si vous connaissez, vous savez, n'importe quel autre langage de programmation. Il n'est pas facile de visualiser comment quicksortse comporte réellement dans Haskell en termes d'accès à la mémoire ou même l'ordre des comparaisons. Si vous pouviez seulement observer le comportement, et non le code source, vous ne reconnaîtrez pas ce qu'il fait comme un tri rapide .

Par exemple, la version C de quicksort partitionne toutes les données avant le premier appel récursif. Dans la version Haskell, le premier élément du résultat sera calculé (et pourrait même apparaître sur votre écran) avant la fin de l'exécution de la première partition - en fait avant que tout travail ne soit effectué greater.

PS Le code Haskell serait plus rapide s'il effectuait le même nombre de comparaisons que quicksort; le code tel qu'il est écrit fait deux fois plus de comparaisons car lesseril greaterest spécifié pour être calculé indépendamment, en effectuant deux balayages linéaires dans la liste. Bien sûr, il est possible en principe que le compilateur soit suffisamment intelligent pour éliminer les comparaisons supplémentaires; ou le code pourrait être changé pour utiliser Data.List.partition.

PPS L'exemple classique des algorithmes de Haskell se révélant ne pas se comporter comme prévu est le tamis d'Eratosthène pour le calcul des nombres premiers.

Je crois que la raison pour laquelle la plupart des gens disent que le joli Haskell Quicksort n'est pas un "vrai" Quicksort est le fait qu'il n'est pas en place - clairement, cela ne peut pas être lors de l'utilisation de types de données immuables. Mais il y a aussi l'objection que ce n'est pas «rapide»: en partie à cause du cher ++, et aussi parce qu'il y a une fuite d'espace - vous vous accrochez à la liste d'entrée tout en faisant l'appel récursif sur les éléments inférieurs, et dans certains cas - par exemple lorsque la liste diminue - cela se traduit par une utilisation de l'espace quadratique. (Vous pourriez dire que le faire fonctionner dans un espace linéaire est le plus proche que vous puissiez obtenir "sur place" en utilisant des données immuables.) Il existe des solutions intéressantes à ces deux problèmes, en utilisant des paramètres d'accumulation, du tupling et de la fusion; voir S7.6.1 de Richard Bird

Ce n'est pas l'idée de faire muter des éléments en place dans des contextes purement fonctionnels. Les méthodes alternatives de ce fil avec des tableaux mutables ont perdu l'esprit de pureté.

Il y a au moins deux étapes pour optimiser la version de base (qui est la version la plus expressive) du tri rapide.

1. Optimiser la concaténation (++), qui est une opération linéaire, par accumulateurs:

   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. Optimisez le tri rapide ternaire (partition à 3 voies, mentionnée par Bentley et Sedgewick), pour gérer les éléments dupliqués:

   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. Combinez 2 et 3, reportez-vous au livre de 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

Ou bien si les éléments dupliqués ne sont pas majoritaires:

    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

Malheureusement, la médiane de trois ne peut pas être implémentée avec le même effet, par exemple:

    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] 

car il fonctionne toujours mal dans les 4 cas suivants:

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

Tous ces 4 cas sont bien traités par une approche impérative de la médiane de trois.

En fait, l'algorithme de tri le plus approprié pour un paramètre purement fonctionnel est toujours le tri par fusion, mais pas le tri rapide.

Pour plus de détails, veuillez consulter ma rédaction en cours sur: https://sites.google.com/site/algoxy/dcsort

Il n'y a pas de définition claire de ce qui est et de ce qui n'est pas un véritable tri rapide.

Ils l'appellent pas un vrai tri rapide, car il ne trie pas sur place:

Véritable tri rapide en C trie sur place

Parce que prendre le premier élément de la liste entraîne une très mauvaise exécution. Utilisez la médiane de 3: premier, milieu, dernier.

Demandez à n'importe qui d'écrire Quicksort dans Haskell, et vous obtiendrez essentiellement le même programme - c'est évidemment quicksort. Voici quelques avantages et inconvénients:

Pro: Il améliore le "vrai" tri rapide en étant stable, c'est-à-dire qu'il préserve l'ordre des séquences entre des éléments égaux.

Pro: Il est trivial de généraliser à une division à trois (<=>), ce qui évite un comportement quadratique dû à une certaine valeur se produisant O (n) fois.

Pro: C'est plus facile à lire - même s'il fallait inclure la définition du filtre.

Con: Il utilise plus de mémoire.

Inconvénient: il est coûteux de généraliser le choix du pivot par un échantillonnage supplémentaire, ce qui pourrait éviter un comportement quadratique sur certains ordres de faible entropie.