Fusionner trier dans Haskell

Question

Je suis nouveau à Haskell et j'essaye d'implémenter quelques algorithmes connus dedans.

J'ai implémenté le tri par fusion sur les chaînes. Je suis un peu déçu des performances de mon implémentation Haskell par rapport aux implémentations C et Java. Sur ma machine (Ubuntu Linux, 1,8 GHz), C (gcc 4.3.3) trie 1 000 000 chaînes en 1,85 s, Java (Java SE 1.6.0_14) en 3,68 s, Haskell (GHC 6.8.2) en 25,89 s. Avec une plus grande entrée (10 000 000 chaînes), C prend 21,81 s, Java prend 59,68 s, Haskell commence à échanger et j'ai préféré arrêter le programme après plusieurs minutes.

Depuis que je suis nouveau à Haskell, je serais intéressé de savoir si ma mise en œuvre peut être rendue plus de temps/espace efficace.

Merci à l'avance pour tout soupçon Giorgio

Ma mise en œuvre:

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

Je ne sais pas si cela est la cause de votre problème, mais rappelez-vous que les listes sont une structure de données séquentielle. En particulier, length xs et splitAt n xs prendront une durée proportionnelle à la longueur de la liste (O(n)). En C et Java, vous utilisez probablement des tableaux, qui prennent un temps constant pour les deux opérations (O(1)). Edit: répondant à votre question sur la façon de le rendre plus efficace, vous pouvez également utiliser des tableaux dans Haskell.

Answer 2

Dans Haskell, une chaîne est une liste de caractères paresseux et a le même préfixe que toute autre liste. Si je me souviens bien d'une conversation que j'ai entendue en 2004 avec Simon Peyton Jones, le coût de l'espace dans GHC est de 40 octets par personnage. Pour une comparaison pommes-pommes, vous devriez probablement trier Data.ByteString, qui est conçu pour donner des performances comparables aux autres langues.

Answer 3

meilleure façon de diviser la liste pour éviter les CesarB d'émission souligne:

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: fixe.

Answer 4

Essayez cette version:

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. idée Bad est la liste fractionnement en premier. Au lieu de cela, il suffit de faire la liste des listes d'un membre. Haskell est paresseux, ça se fera au bon moment.
2. Fusionnez ensuite les paires de listes jusqu'à ce que vous ayez une seule liste.

Modifier: Quelqu'un qui down-vote cette réponse: ci-dessus tri par fusion est mise en œuvre même algorithme que celui utilisé dans GHC Data.List.sort sauf fonction cmp supprimée. Eh bien les auteurs de ghc peuvent se tromper: -/