la forma merge-sort más rápido que la inserción-tipo me desconcierta

Question

Acabo de mojar mis pies en el algoritmo de clasificación con Haskell. He implementado inserción especie y combinar-tipo

insert_sort :: (Ord a, Show a) => [a] -> [a] 
insert_sort keys = foldr f [] keys 
      where f key []  = [key] 
       f key acc  = insert key acc 
       insert y []  = [y] 
       insert y (x:xs) 
        | x < y  = x : insert y xs 
        | otherwise = y : x : xs 

merge_sort :: (Ord a, Show a) => [a] -> [a] 
merge_sort (x:[]) = [x] 
merge_sort keys = merge (merge_sort (take len keys)) (merge_sort (drop len keys)) 
     where len   = length keys `div` 2 
      merge :: [a] -> [a] -> [a] 
      merge (x:xs) []  = (x:xs) 
      merge []  (y:ys) = (y:ys) 
      merge (x:xs) (y:ys) = if x <= y 
            then x : merge (xs) (y:ys) 
            else y : merge (x:xs) ys 

Así es como he comparado su eficiencia:

insert_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 
merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

Ambos de ellos comienza a imprimir los resultados después de un breve retraso, pero fusionar-ordenar impresiones de gran Más rápido. Como sabemos, merge-sort es mucho más rápido que insertion-sort para grandes conjuntos de datos. Pensé que eso se demostraría por la forma en que dan resultados (como un largo retraso versus uno corto) y no cómo imprimen los resultados. ¿Es porque utilizo foldr en inserción-sort? ¿Qué hay detrás de la escena?

EDIT: Thx guys. He oído hablar de la evaluación perezosa desde que comencé a aprender Haskell, pero aún así le di con el truco. ¿Alguien podría ilustrar un poco más con un pequeño conjunto de datos, digamos [5,2,6,3,1,4]? ¿Cómo es posible generar resultados antes de finalizar la clasificación con foldr ya que los primeros elementos llegan finalmente?

Answer 1

Detrás del escenario está la evaluación perezosa. El inicio de las listas ordenadas se determina antes de que se complete la clasificación, por lo que se puede generar antes de que el trabajo finalice. Como un mergesort es más rápido, la lista ordenada por fusión se imprime más rápido.

Según lo solicitado: cómo procede la clasificación [5,2,6,3,1,4]. Yo uso insert_sort = foldr ins [] para abreviar.

insert_sort [5,2,6,3,1,4] 
    = foldr ins [] [5,2,6,3,1,4] 
    = 5 `ins` foldr ins [] [2,6,3,1,4] 
    = 5 `ins` 2 `ins` [6,3,1,4] ... 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` 4 `ins` [] 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` (4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` (1:4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` (1 : (3 `ins` (4:[]))) 
    = 5 `ins` 2 `ins` (1 : (6 `ins` (3 `ins` (4:[])))) 
    = 5 `ins` (1 : (2 `ins` (6 `ins` (3 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3 `ins` (4:[]))))) -- now 1 can be output 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3:4:[])))) 
    = 1 : (5 `ins` (2 `ins` (3 : (6 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 : (3 : (6 `ins` (4:[]))))) 
    = 1 : 2 : (5 `ins` (3 : (6 `ins` (4:[]))))   -- now 2 can be output 
    = 1 : 2 : 3 : (5 `ins` (6 `ins` (4:[])))    -- now 3 
    = 1 : 2 : 3 : (5 `ins` (4:6:[])) 
    = 1 : 2 : 3 : 4 : (5 `ins` (6:[]))     -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- done 

and Merge sort (abreviaturas: merge = mg, merge_sort = ms):

merge_sort [5,2,6,3,1,4] 
    = mg (ms [5,2,6]) (ms [3,1,4]) 
    = mg (mg (ms [5]) (ms [2,6])) (mg (ms [3]) (ms [1,4])) 
    = mg (mg [5] (mg [2] [6])) (mg [3] (mg [1] [4])) 
    = mg (mg [5] [2,6]) (mg [3] [1,4]) 
    = mg (2 : mg [5] [6]) (1 : mg [3] [4]) 
    = 1 : mg (2 : mg [5] [6]) (mg [3] [4])    -- now 1 can be output 
    = 1 : mg (2 : mg [5] [6]) [3,4] 
    = 1 : 2 : mg (mg [5] [6]) [3,4]      -- now 2 can be output 
    = 1 : 2 : mg [5,6] [3,4] 
    = 1 : 2 : 3 : mg [5,6] [4]       -- now 3 
    = 1 : 2 : 3 : 4 : mg [5,6] []       -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- now 5 and 6 

verdad es que me he tomado un par de atajos, pero Haskell no es el único perezoso.

Answer 2

OK aquí está el desglose. Quiere que imprima:

merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

Sé que esta es una lista. Así primer lugar voy a imprimir una llave abierta

[ 

A continuación, voy a buscar el primer elemento de la lista, la impresión de que fuera, y luego una coma. Eso significa que tengo que comenzar a evaluar esa expresión hasta que pueda descubrir cuál es el primer elemento de la lista.

merge_sort THUNK0 

Bueno, ahora tengo que coincidir con el patrón. O THUNK coincide con (x:[]) o no. Pero aún no lo sé Así que voy a evaluar ese truco un poco. Hago que el thunk produzca los dos primeros números aleatorios (de 100000). Ahora yo sé que no coincide con la primera definición, entonces tomo la segunda definición de merge_sort.

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0 

Bueno, eso es bastante fácil ... es sólo una llamada a fusionar. Expandiré esa definición. Oh mierda, hay tres patrones diferentes que pueden coincidir.Creo que debería evaluar THUNK1 un poco y ver si coincide con el patrón de la primera definición, (x:xs)

merge_sort (take THUNK3 THUNK0) 

Volver a merge_sort de nuevo, ¿verdad? Eso significa que necesito evaluar (take THUNK3 THUNK0) lo suficiente como para saber si coincide con (x:[]) o no. Oh mierda. take es estricto en su primer argumento ... eso significa que tengo que evaluar completamente THUNK3. Ok ... respiraciones profundas ...

len = length THUNK0 `div` 2 

Ahora, aquí está un caso irritante. Para calcular length en THUNK0 (que es una lista), tengo que expandir TODA LA COLUMNA VERTEBRAL. No tengo que calcular realmente los valores en el interior, pero sí necesito desarrollar la estructura de toda la lista. Esto, por supuesto, se realiza una coincidencia de patrón a la vez, determinando si es [] o (x:xs). Pero como un todo, length es "riguroso".

breve pausa mientras yo dar cuerpo a la columna vertebral de una lista de elementos 100000

Uf, tengo que hacer. Ahora sé la longitud, lo que significa que sé len = 500000. THUNK0 es finalmente totalmente evaluado! ¡Uf! ¿Donde estaba?

merge_sort (take 500000 THUNK3) 

---

Y así sucesivamente. merge_sort seguirá tratando de ser lo más vago posible. Las llamadas recursivas al merge_sort serán tan vagas como sea posible. Finalmente, para determinar el primer elemento del merge_sort más externo, necesitaremos conocer el primer elemento de ambas llamadas recursivas al merge_sort. Y para conocer el primer elemento de eso ... necesitaremos el primer elemento de las llamadas recursivas subsiguientes, etc. Así que habrá aproximadamente O (n) trabajo hecho, porque cada elemento necesita ser evaluado (realizando el azar generación de números para cada uno).

Entonces, piénsalo como un torneo. Cada elemento está emparejado contra otro elemento. Los elementos "ganadores" (los más bajos) avanzan a la siguiente ronda (convirtiéndose en el primer elemento de la llamada recursiva al merge_sort s más bajo). Hay otra competencia con 1/2 combatientes y 1/2 de (1/4 del total) pasan a la siguiente ronda, etc. Esto también resulta ser O (n) trabajo , ya que las comparaciones (n/2) se realizan durante la primera ronda, y las rondas siguientes se hacen más pequeñas demasiado rápido para ser significativas. (La suma media + 1/4 + 1/8 ... converge a 1, lo que significa se llevan a cabo un total de n comparaciones.)

Con todo, O (n) necesita trabajo a realizar para finalmente producir el primer elemento. Es necesario realizar trabajos adicionales para los elementos subsiguientes, pero la cantidad total de trabajo termina siendo O (n log (n)).

---

Ahora contraste esto con insert_sort. Solo piense en cómo funciona: atraviesa la lista e "inserta" cada elemento en una lista ordenada.Eso significa que no puede saber con seguridad cuál es el primer elemento de la ordenada hasta que haya realizado la última parte del trabajo, e insertó el elemento final (que podría haber sido el más bajo) en la lista ordenada.

espero que esto ilustra claramente cómo merge_sort no es necesario para llevar a cabo todas el trabajo con el fin de empezar a producir resultados, mientras que insert_sort hace.