Unisci ordina in Haskell

Question

Sono nuovo di Haskell e sto cercando di implementare alcuni algoritmi noti al suo interno.

Ho implementato il merge sort su stringhe. Sono un po 'deluso dalle prestazioni della mia implementazione Haskell rispetto alle implementazioni C e Java. Sulla mia macchina (Ubuntu Linux, 1,8 GHz), C (gcc 4.3.3) ordina 1 000 000 stringhe in 1,85 s, Java (Java SE 1.6.0_14) in 3.68 s, Haskell (GHC 6.8.2) in 25.89 S. Con un input più grande (10.000.000 di stringhe), C ha 21.81 s, Java richiede 59.68 s, Haskell inizia lo scambio e ho preferito interrompere il programma dopo alcuni minuti.

Poiché sono nuovo di Haskell, sarei interessato a sapere se la mia implementazione può rendere più efficiente in termini di tempo/spazio.

Grazie in anticipo per qualsiasi suggerimento Giorgio

mia realizzazione:

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

Non sono sicuro se questa è la causa del problema, ma ricordo che le liste sono una struttura di dati sequenziali. In particolare, sia length xs sia splitAt n xs impiegheranno una quantità di tempo proporzionale alla lunghezza dell'elenco (O(n)).

In C e Java, si sta probabilmente utilizzando matrici, che richiedono tempo costante per entrambe le operazioni (O(1)).

Modifica: rispondendo alla domanda su come renderlo più efficiente, è possibile utilizzare anche gli array in Haskell.

Answer 2

In Haskell, una stringa è un elenco pigro di caratteri e ha lo stesso sovraccarico di qualsiasi altro elenco. Se ricordo proprio da un discorso che ho ascoltato Simon Peyton Jones nel 2004, il costo dello spazio in GHC è di 40 byte per personaggio. Per un confronto tra mele e mele probabilmente dovresti scegliere lo Data.ByteString, progettato per offrire prestazioni paragonabili ad altre lingue.

Answer 3

modo migliore per dividere l'elenco per evitare il problema CesarB sottolinea:

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 

EDIT: Fisso.

Answer 4

Prova questa versione:

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. Bad idea è la lista splitting prima. Invece di fare solo lista di un elenco di membri. Haskell è pigro, sarà fatto nel momento giusto.
2. Quindi unire coppie di elenchi finché non si dispone di una sola lista.

Edit: Qualcuno che down-voto questa risposta: sopra merge sort implementazione è stesso algoritmo utilizzato in ghc Data.List.sort se non con la funzione cmp rimosso. Gli autori di well ghc potrebbero essere errati: -/