Я новичок в Haskell, и я пытаюсь реализовать в нем несколько известных алгоритмов.
Я реализовал сортировку слияния по строкам. Я немного разочарован тем, что производительность моей реализации Haskell по сравнению с реализациями C и Java. На моей машине (Ubuntu Linux, 1,8 ГГц) C (gcc 4.3.3) сортирует 1 000 000 строк за 1,85 с, Java (Java SE 1.6.0_14) в 3.68 с, Haskell (GHC 6.8.2) в 25.89 с. С более крупным вводом (10 000 000 строк) C занимает 21,81 с, Java занимает 59,68 с, Haskell начинает меняться, и я предпочел остановить программу через несколько минут.
Поскольку я новичок в Haskell, мне было бы интересно узнать, может ли моя реализация сделать больше времени/пространства эффективным.
Заранее благодарю за любой намек Giorgio
Моя реализация:
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)