Объединить сортировку в Haskell

Я новичок в 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)

Ответы

Ответ 1

Попробуйте эту версию:

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]

Плохая идея - это раскалывание списка. Вместо этого просто создайте список из одного списка участников. Haskell ленив, это будет сделано в нужное время.
Затем объедините пары списков, пока не появится только один список.

Изменить. Кто-то, кто проголосовал за этот ответ: выше реализация сортировки слияния - это тот же алгоритм, что и в ghc Data.List.sort, за исключением функции cmp. Возможно, авторы ghc могут ошибаться: -/

Ответ 2

В Haskell строка представляет собой ленивый список символов и имеет те же накладные расходы, что и любой другой список. Если я помню прямо из разговора, я слышал, как Саймон Пейтон Джонс дал в 2004 году, стоимость пространства в GHC составляет 40 байт на символ. Для сравнения яблок с яблоками вы, вероятно, должны сортировать Data.ByteString, который предназначен для обеспечения производительности, сравнимой с другими языками.

Ответ 3

Лучший способ разбить список, чтобы избежать проблемы. 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

EDIT: исправлено.

Ответ 4

Я не уверен, что это причина вашей проблемы, но помните, что списки - это последовательная структура данных. В частности, как length xs, так и splitAt n xs будет занимать промежуток времени, пропорциональный длине списка (O(n)).

В C и Java вы, скорее всего, используете массивы, которые занимают постоянное время для обеих операций (O(1)).

Изменить: отвечая на вопрос о том, как сделать его более эффективным, вы также можете использовать массивы в Haskell.