Combinar la clasificación en Haskell

performance mergesort

Question

Soy nuevo en Haskell y estoy tratando de implementar algunos algoritmos conocidos en él.

He implementado la clasificación de fusión en cadenas. Estoy un poco decepcionado con el rendimiento de mi implementación de Haskell en comparación con las implementaciones de C y Java. En mi máquina (Ubuntu Linux, 1.8 GHz), C (gcc 4.3.3) ordena 1 000 000 cadenas en 1.85 s, Java (Java SE 1.6.0_14) en 3.68 s, Haskell (GHC 6.8.2) en 25.89 s. Con una entrada mayor (10 000 000 cadenas), C toma 21,81 s, Java toma 59,68 s, Haskell comienza a intercambiar y prefiero detener el programa después de varios minutos.

Como soy nuevo en Haskell, me interesaría saber si mi implementación puede ser más eficiente en tiempo y espacio.

Gracias de antemano por cualquier pista Giorgio

Mi implementación:

merge :: [String] -> [String] -> [String]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x < y
                        then x : (merge xs (y:ys))
                        else y : (merge (x:xs) ys)

mergeSort :: [String] -> [String]
mergeSort xs = if (l < 2)
                 then xs
                 else merge h t
               where l = length xs
                     n = l `div` 2
                     s = splitAt n xs
                     h = mergeSort (fst s)
                     t = mergeSort (snd s)

Answer 1

En Haskell, una cadena es una lista perezosa de caracteres y tiene la misma sobrecarga que cualquier otra lista. Si recuerdo de una charla que escuché a Simon Peyton Jones dar en 2004, el costo de espacio en GHC es de 40 bytes por carácter. Para una comparación de manzanas con manzanas, probablemente debería clasificar Data.ByteString , que está diseñado para ofrecer un rendimiento comparable al de otros idiomas.

Answer 2

Mejor manera de dividir la lista para evitar el problema que señala CesarB:

split []             = ([], [])
split [x]            = ([x], [])
split (x : y : rest) = (x : xs, y : ys)
                       where (xs, ys) = split rest

mergeSort []  = []
mergeSort [x] = [x]
mergeSort xs  = merge (mergesort ys) (mergesort zs)
                where (ys, zs) = split xs

EDITAR: Fijo.

Answer 3

No estoy seguro de si esta es la causa de su problema, pero recuerde que las listas son una estructura de datos secuencial. En particular, tanto la length xs como splitAt n xs tomarán una cantidad de tiempo proporcional a la longitud de la lista ( O(n) ).

En C y Java, lo más probable es que esté utilizando arreglos, que toman tiempo constante para ambas operaciones ( O(1) ).

Edición: respondiendo a su pregunta sobre cómo hacerlo más eficiente, también puede usar arreglos en Haskell.

Answer 4

Prueba esta versión:

mergesort :: [String] -> [String]
mergesort = mergesort'' . map wrap

mergesort'' :: [[String]] -> [String]
mergesort'' [] = []
mergesort'' [xs] = xs
mergesort'' xss = mergesort'' (merge_pairs xss)

merge_pairs :: [[String]] -> [[String]]
merge_pairs [] = []
merge_pairs [xs] = [xs]
merge_pairs (xs:ys:xss) = merge xs ys : merge_pairs xss

merge :: [String] -> [String] -> [String]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
 = if x > y
        then y : merge (x:xs)  ys
        else x : merge  xs    (y:ys)

wrap :: String -> [String]
wrap x = [x]

1. La mala idea es dividir la lista primero. En lugar de eso, simplemente haga una lista de las listas de un miembro. Haskell es perezoso, se hará en el momento adecuado.
2. Luego fusiona pares de listas hasta que tengas solo una lista.

Edición : alguien que vota a favor esta respuesta: la implementación anterior de la combinación de combinaciones es el mismo algoritmo que se usa en ghc Data.List.sort, excepto que se ha eliminado la función cmp. Bueno, los autores de ghc pueden estar equivocados: - /