在Haskell中合并排序

Question

我是Haskell的新手,我正在尝试在其中实现一些已知的算法.

我已经对字符串实现了合并排序.与C和Java实现相比,我对Haskell实现的性能有点失望.在我的机器上(Ubuntu Linux,1.8 GHz),C(gcc 4.3.3)在1.85秒内对1 000 000个字符串进行排序,在3.68秒内对Java(Java SE 1.6.0_14),在2.89秒内对Haskell(GHC 6.8.2)进行排序.使用更大的输入(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. 不好的想法是先拆分清单.而不是只列出一个成员列表.Haskell很懒,它会在合适的时间完成.
2. 然后合并列表对,直到您只有一个列表.

编辑:向下投票给出这个答案的人:上面的合并排序实现与ghc Data.List.sort中使用的算法相同,只是删除了cmp函数.那么ghc的作者可能是错的: - /

Answer 2

在Haskell中,字符串是一个惰性字符列表,并且具有与任何其他列表相同的开销.如果我记得2004年Simon Peyton Jones给出的演讲,那么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中使用数组.