19

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

我已经对字符串实现了合并排序。与 C 和 Java 实现相比，我对 Haskell 实现的性能有点失望。在我的机器（Ubuntu Linux，1.8 GHz）上，C（gcc 4.3.3）在 1.85 秒内对 1 000 000 个字符串进行排序，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 的新手，我很想知道我的实现是否可以提高时间/空间效率。

提前感谢您的任何提示乔治

我的实现：

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)
4

4 回答 4

18

试试这个版本：

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作者可能是错的：-/

于 2009-08-01T19:55:15.767 回答
14

在 Haskell 中，字符串是一个惰性字符列表，与任何其他列表具有相同的开销。如果我记得我在 2004 年听 Simon Peyton Jones 的一次演讲，GHC 中的空间成本是每个字符 40 字节。对于苹果对苹果的比较，您可能应该排序Data.ByteString，它旨在提供与其他语言相当的性能。

于 2009-08-01T01:45:25.570 回答
9

拆分列表以避免 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

编辑：固定。

于 2009-08-01T06:16:49.533 回答
5

我不确定这是否是您的问题的原因，但请记住列表是一种顺序数据结构。特别是，两者都length xs将splitAt n xs花费与列表长度成正比的时间量 ( O(n))。

在 C 和 Java 中，您很可能使用数组，这两种操作都需要固定的时间 ( O(1))。

编辑：回答您关于如何提高效率的问题，您也可以在 Haskell 中使用数组。

于 2009-08-01T00:22:35.197 回答