performance - rápido - ¿Por qué Haskell usa mergesort en lugar de quicksort?

quicksort raptor

Question

En el Haskell de Wikilibros , existe la siguiente afirmación :

Data.List ofrece una función de clasificación para ordenar listas. No utiliza quicksort; más bien, utiliza una implementación eficiente de un algoritmo llamado mergesort.

¿Cuál es la razón subyacente en Haskell para usar mergesort sobre quicksort? Quicksort por lo general tiene un mejor rendimiento práctico, pero tal vez no en este caso. Supongo que los beneficios in situ de quicksort son difíciles (¿imposibles?) De hacer con las listas de Haskell.

Hubo una pregunta relacionada con la ingeniería de software.SE , pero en realidad no se trataba de por qué se utiliza mergesort.

Yo mismo implementé los dos géneros para perfilar. Mergesort fue superior (aproximadamente el doble de rápido para una lista de 2 ^ 20 elementos), pero no estoy seguro de que mi implementación de quicksort fuera óptima.

Edición: Aquí están mis implementaciones de mergesort y quicksort:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) second@(v:vs)
    | l < v = l : merge ls second
    | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
    where pivotIndex = div (length l) 2
          pivot = l !! pivotIndex
          [less, greater] = foldl addElem [[], []] $ enumerate l
          addElem [less, greater] (index, elem)
            | index == pivotIndex = [less, greater]
            | elem < pivot = [elem:less, greater]
            | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

Edit 2 3: Me pidieron que proporcionara tiempos para mis implementaciones en comparación con la clasificación en Data.List . Siguiendo las sugerencias de @Will Ness, compilé esta -O2 con el indicador -O2 , cambiando la clasificación suministrada en main cada vez, y lo -O2 con +RTS -s . La lista ordenada era una lista [Int] pseudoaleatoria de creación barata con 2 ^ 20 elementos. Los resultados fueron los siguientes:

• Data.List.sort : 0.171s
• mergesort : 1.092s (~ 6x más lento que Data.List.sort )
• quicksort : 1.152s (~ 7x más lento que Data.List.sort )

Answer 1

Creo que la respuesta de @ comingstorm está prácticamente en la nariz, pero aquí hay más información sobre la historia de la función de clasificación de GHC.

En el código fuente de Data.OldList , puede encontrar la implementation de sort y verificar por sí mismo que es una ordenación de combinación. Justo debajo de la definición en ese archivo está el siguiente comentario:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <[email protected]>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it''s performance...

Por lo tanto, originalmente se usó un quicksort funcional (y la función qsort todavía está allí, pero comentó). Los puntos de referencia de Ian mostraron que su combinación era competitiva con la ordenación rápida en el caso de la "lista aleatoria" y superó de forma masiva en el caso de los datos ya clasificados. Más tarde, la versión de Ian fue reemplazada por otra implementación que fue aproximadamente dos veces más rápida, de acuerdo con los comentarios adicionales en ese archivo.

El principal problema con el qsort original era que no usaba un pivote aleatorio. En su lugar, se basó en el primer valor de la lista. Obviamente, esto es bastante malo porque implica que el rendimiento será el peor de los casos (o cierre) para la entrada ordenada (o casi ordenada). Desafortunadamente, hay un par de desafíos para cambiar de "pivote en primer lugar" a una alternativa (ya sea al azar o, como en su implementación, en algún lugar en el "medio"). En un lenguaje funcional sin efectos secundarios, administrar una entrada pseudoaleatoria es un poco un problema, pero digamos que lo resuelve (tal vez construyendo un generador de números aleatorios en su función de clasificación). Aún tiene el problema de que, al ordenar una lista enlazada inmutable, la ubicación de un pivote arbitrario y la partición basada en ella implicarán múltiples recorridos de listas y copias de listas secundarias.

Creo que la única forma de darse cuenta de los supuestos beneficios de quicksort sería escribir la lista en un vector, clasificarla en su lugar (y sacrificar la estabilidad de clasificación) y escribirla de nuevo en una lista. No veo que eso pueda ser una victoria general. Por otro lado, si ya tiene datos en un vector, entonces una orden rápida en el lugar definitivamente sería una opción razonable.

Answer 2

En lenguajes imperativos, Quicksort se realiza en el lugar mediante la mutación de una matriz. Como lo demuestra en el ejemplo de código, puede adaptar Quicksort a un lenguaje funcional puro como Haskell al crear listas enlazadas individualmente, pero esto no es tan rápido.

Por otro lado, Mergesort no es un algoritmo in situ: una implementación imperativa directa copia los datos combinados en una asignación diferente. Esto es mejor para Haskell, que por su naturaleza debe copiar los datos de todos modos.

Retrocedamos un poco: la ventaja del rendimiento de Quicksort es la "tradición", una reputación creada hace décadas en máquinas muy diferentes a las que utilizamos hoy. Incluso si utiliza el mismo idioma, es necesario volver a verificar este tipo de conocimientos de vez en cuando, ya que los hechos en el terreno pueden cambiar. El último documento de evaluación comparativa que leí sobre este tema tenía a Quicksort aún en la parte superior, pero su ventaja sobre Mergesort era escasa, incluso en C / C ++.

Mergesort tiene otras ventajas: no es necesario modificarlo para evitar el peor de los casos de O (n ^ 2) de Quicksort, y es naturalmente estable. Por lo tanto, si pierde la estrecha diferencia de rendimiento debido a otros factores, Mergesort es una opción obvia.

Answer 3

En una lista de enlaces individuales, mergesort se puede hacer en su lugar. Además, las implementaciones ingenuas escanean más de la mitad de la lista para obtener el inicio de la segunda sublista, pero el inicio de la segunda sublista es un efecto secundario de la clasificación de la primera sublista y no necesita un escaneo adicional. La única cosa que quicksort ha revisado es la coherencia de caché. Quicksort trabaja con elementos cercanos entre sí en la memoria. Tan pronto como un elemento de indirección ingresa en él, como cuando se ordenan matrices de punteros en lugar de los datos en sí, la ventaja se reduce.

Mergesort tiene duras garantías para el peor comportamiento, y es fácil hacer una clasificación estable con él.

Answer 4

Muchos argumentos sobre por qué Quicksort no se usa en Haskell parecen verosímiles. Sin embargo, al menos Quicksort no es más lento que Mergesort para el caso aleatorio. Basándome en la implementación dada en el libro de Richard Bird, Pensando funcionalmente en Haskell , hice una ordenación rápida de 3 vías:

tqsort [] = []
tqsort (x:xs) = sortp xs [] [x] [] 
  where
    sortp [] us ws vs     = tqsort us ++ ws ++ tqsort vs
    sortp (y:ys) us ws vs =
      case compare y x of 
        LT -> sortp ys (y:us) ws vs 
        GT -> sortp ys us ws (y:vs)
        _  -> sortp ys us (y:ws) vs

Comparé algunos casos, por ejemplo, listas de tamaño 10 ^ 4 que contienen Int entre 0 y 10 ^ 3 o 10 ^ 4, y así sucesivamente. El resultado es que el Quicksort de 3 vías o incluso la versión de Bird son mejores que el Mergesort de GHC, algo así como 1.x ~ 3.x más rápido que el Mergesort de ghc, dependiendo del tipo de datos (¿muchas repeticiones? ¿Muy escasas?). Las siguientes estadísticas son generadas por criterion :

benchmarking Data.List.sort/Diverse/10^5
time                 223.0 ms   (217.0 ms .. 228.8 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 226.4 ms   (224.5 ms .. 228.3 ms)
std dev              2.591 ms   (1.824 ms .. 3.354 ms)
variance introduced by outliers: 14% (moderately inflated)

benchmarking 3-way Quicksort/Diverse/10^5
time                 91.45 ms   (86.13 ms .. 98.14 ms)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 96.65 ms   (94.48 ms .. 98.91 ms)
std dev              3.665 ms   (2.775 ms .. 4.554 ms)

Sin embargo, hay otro requisito de sort establecido en Haskell 98 : debe ser estable . La implementación típica de Quicksort que usa Data.List.partition es estable , pero la anterior no lo es.

tqsort posterior : un Quicksort de 3 vías estable mencionado en el comentario parece tan rápido como tqsort aquí.

Answer 5

No estoy seguro, pero mirando el código no creo que Data.List.sort sea ​​Mergesort como lo conocemos. Simplemente hace que una sola pasada comience con la función de sequences en una forma recursiva mutua triangular hermosa con funciones ascending y descending para obtener una lista de fragmentos ordenados ya ascendentes o descendentes en el orden requerido. Sólo entonces comienza a fusionarse.

Es una manifestación de la poesía en la codificación. A diferencia de Quicksort, su caso más desfavorable (entrada aleatoria total) tiene una complejidad de tiempo O (nlogn), y el mejor de los casos (ya ordenado ascendente o descendente) es O (n).

No creo que ningún otro algoritmo de clasificación pueda vencerlo.

Answer 6

Respuesta corta:

Quicksort es ventajoso para arreglos (en el lugar, rápido, pero no en el peor de los casos óptimo). Mergesort para listas enlazadas (rápido, en el peor de los casos óptimo, estable, simple).

Quicksort es lento para las listas, Mergesort no está en el lugar para los arreglos.