Сортировка слиянием в Haskell

Question

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

Answer 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]

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

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

Answer 2

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

Answer 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

РЕДАКТИРОВАТЬ: Исправлено.

Answer 4

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

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

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