sorting - ¿Por qué el ejemplo minimalista Haskell quicksort no es una solución "verdadera"?

Question

El sitio web de Haskell presenta una función de orden rápido de 5 líneas muy atractiva, como se ve a continuación.

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

También incluyen un "Quicksort verdadero 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 enlace debajo de la versión C dirige a una página que dice ''La oferta rápida citada en Introducción no es la'' rápida ''y no escala para listas más largas como hace el código c''.

¿Por qué la función Haskell anterior no es una verdadera oferta rápida? ¿Cómo no puede escalar para listas más largas?

Answer 1

Aquí hay una transcripción del código "verdadero" de quicksort C en Haskell. Prepárate.

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

Eso fue divertido, ¿no? De hecho, recorté esta gran let al principio, así como el punto al final de la función, definiendo todos los ayudantes para que el código anterior sea bastante bonito.

  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

Y aquí, una prueba tonta para ver si funciona.

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]

No escribo código imperativo con mucha frecuencia en Haskell, así que estoy seguro de que hay muchas formas de limpiar este código.

¿Y qué?

Notarás que el código anterior es muy, muy largo. El núcleo de esto es tan largo como el código C, aunque cada línea es a menudo un poco más detallada. Esto es porque C secretamente hace muchas cosas desagradables que podrías dar por sentado. Por ejemplo, a[l] = a[h]; . Esto accede a las variables mutables l , y luego accede a la matriz mutable a , y luego muta la matriz mutable a . ¡Santa mutación, Batman! En Haskell, la mutación y el acceso a las variables mutables es explícito. El qsort "falso" es atractivo por varias razones, pero el principal es que no usa mutación; esta restricción autoimpuesta lo hace mucho más fácil de entender de un vistazo.

Answer 2

Creo que el argumento que este argumento intenta hacer es que la razón por la cual el Quicksort se usa comúnmente es que está en el lugar y es bastante amigable con el caché como resultado. Ya que no tiene esos beneficios con las listas de Haskell, su principal razón de ser se ha ido, y también podría usar el tipo de fusión, lo que garantiza O (n log n) , mientras que con quicksort tiene que usar la aleatorización o complicada esquemas de partición para evitar el tiempo de ejecución O (n ² ) en el peor de los casos.

Answer 3

Creo que la razón por la que la mayoría de las personas dice que la bonita Haskell Quicksort no es una "verdadera" Quicksort es el hecho de que no está en su lugar, claramente, no puede ser cuando se usan tipos de datos inmutables. Pero también existe la objeción de que no es "rápido": en parte debido a los costosos ++, y también porque hay una fuga de espacio: usted se aferra a la lista de entrada mientras hace la llamada recursiva en los elementos menores, y en algunos casos, por ejemplo, cuando la lista está disminuyendo, esto da como resultado un uso de espacio cuadrático. (Podría decir que hacer que se ejecute en el espacio lineal es lo más cercano que puede llegar a "in situ" utilizando datos inmutables). Hay soluciones claras para ambos problemas, usando parámetros de acumulación, tupling y fusión; ver S7.6.1 de la Introducción de Richard Bird a la Programación Funcional Usando Haskell .

Answer 4

El verdadero quicksort tiene 2 hermosos aspectos:

1. Divide y conquistaras; divide el problema en dos problemas más pequeños.
2. Partición de los elementos en el lugar.

El ejemplo corto de Haskell demuestra (1), pero no (2). ¡Cómo se hace (2) puede no ser obvio si aún no conoce la técnica!

Answer 5

En mi opinión, decir que "no es una verdadera oferta rápida" exagera el caso. Creo que es una implementación válida del algoritmo Quicksort , pero no particularmente eficiente.

Answer 6

Gracias a la evaluación perezosa, un programa Haskell no hace (casi no puede ) hacer lo que parece que hace.

Considera este programa:

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

En un lenguaje entusiasta, se ejecutaría el primer quicksort , luego se show y luego se putStrLn . Los argumentos de una función se computan antes de que esa función comience a ejecutarse.

En Haskell, es todo lo contrario. La función comienza a ejecutarse primero. Los argumentos solo se computan cuando la función realmente los usa. Y un argumento compuesto, como una lista, se calcula de a una por vez, a medida que se usa cada parte.

Entonces, lo primero que sucede en este programa es que putStrLn comience a ejecutarse.

La implementación de putStrLn de GHC funciona copiando los caracteres del argumento String en un búfer de salida. Pero cuando ingresa en este ciclo, el show aún no se ha ejecutado. Por lo tanto, cuando va a copiar el primer carácter de la cadena, Haskell evalúa la fracción del show y las llamadas al sistema quicksort necesarias para calcular ese carácter . Luego putStrLn pasa al siguiente personaje. Entonces, la ejecución de las tres funciones, putStrLn , show y quicksort , está entrelazada. quicksort ejecuta incrementalmente, dejando un gráfico de los subprocesos no evaluados a medida que avanza para recordar dónde se quedó.

Ahora esto es muy diferente de lo que cabría esperar si está familiarizado con cualquier otro lenguaje de programación. No es fácil visualizar cómo se comporta quicksort en Haskell en términos de acceso a la memoria o incluso el orden de las comparaciones. Si solo pudieras observar el comportamiento, y no el código fuente, no reconocerías lo que está haciendo como un servicio rápido .

Por ejemplo, la versión C de quicksort divide todos los datos antes de la primera llamada recursiva. En la versión de Haskell, el primer elemento del resultado se computará (e incluso podría aparecer en su pantalla) antes de que la primera partición se termine de ejecutarse, de hecho antes de que cualquier trabajo se realice en greater .

PD: el código de Haskell sería más parecido a una lista rápida si hiciera el mismo número de comparaciones que la ruta rápida; el código tal como está escrito hace el doble de comparaciones porque se especifican lesser y greater para ser computados independientemente, haciendo dos escaneos lineales a través de la lista. Por supuesto, es posible, en principio, que el compilador sea lo suficientemente inteligente como para eliminar las comparaciones adicionales; o el código podría cambiarse para usar Data.List.partition .

PPS El ejemplo clásico de algoritmos Haskell que parecen no comportarse como esperabas es el tamiz de Eratóstenes para primos informáticos.

Answer 7

No es la idea de mutar elementos in situ en entornos puramente funcionales. Los métodos alternativos en este hilo con matrices mutables perdieron el espíritu de pureza.

Hay al menos dos pasos para optimizar la versión básica (que es la versión más expresiva) de quick-sort.

1. Optimizar la concatenación (++), que es una operación lineal, por acumuladores:

   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. Optimice para la clasificación rápida ternaria (partición de 3 vías, mencionada por Bentley y Sedgewick), para manejar elementos duplicados:

   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. Combine 2 y 3, consulte el libro 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

O, como alternativa, si los elementos duplicados no son la mayoría:

    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

Desafortunadamente, la mediana de tres no se puede implementar con el mismo efecto, por ejemplo:

    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] 

porque todavía tiene un bajo rendimiento en los siguientes 4 casos:

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

Todos estos 4 casos están bien manejados por el enfoque imperativo de la mediana de tres.

En realidad, el algoritmo de ordenamiento más adecuado para una configuración puramente funcional sigue siendo merge-sort, pero no quick-sort.

Para más detalles, visite mi escrito en curso en: https://sites.google.com/site/algoxy/dcsort

Answer 8

No hay una definición clara de lo que es y lo que no es una verdadera solución rápida.

Lo están llamando no una verdadera solución rápida, porque no ordena en el lugar:

True quicksort en C ordena en el lugar

Answer 9

Pídale a cualquiera que escriba quicksort en Haskell, y obtendrá esencialmente el mismo programa; obviamente, se trata de un servicio rápido. Aquí hay algunas ventajas y desventajas:

Pro: Mejora en la conexión rápida "verdadera" al ser estable, es decir, conserva el orden de secuencia entre elementos iguales.

Pro: es trivial generalizar a una división tridireccional (<=>), lo que evita el comportamiento cuadrático debido a que algún valor ocurre O (n) veces.

Pro: es más fácil de leer, incluso si se debe incluir la definición de filtro.

Con: Usa más memoria.

Con: Es costoso generalizar la elección del pivote mediante un muestreo adicional, lo que podría evitar el comportamiento cuadrático en ciertos ordenamientos de baja entropía.

Answer 10

Porque tomar el primer elemento de la lista da como resultado un tiempo de ejecución muy malo. Usa la mediana de 3: primero, medio, último.

Answer 11

True in situ 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