Haskell中的合并排序
我是Haskell的新手，我正在尝试在其中实现一些已知的算法。
我已经在字符串上实现了合并排序。与C和Java实现相比，我对我的Haskell实现的性能有点失望。在我的机器上(Ubuntu Linux，1.8 GHz)，C (gcc 4.3.3)在1.85秒内排序1000000个字符串，Java (Java 1.6.0_14)在3.68s内排序，Haskell (GHC6.8.2)在25.89s内排序。在较大的输入(10000000个字符串)下，C花费21.81s，Java花费59.68s，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)回答 3
Stack Overflow用户
发布于 2009-08-01 01:45:26
在Haskell中，字符串是一个懒惰的字符列表，与任何其他列表具有相同的开销。如果我记得我在2004年听过Simon Peyton Jones的演讲，GHC中的空间成本是每个字符40个字节。为了进行比较，您可能应该对Data.ByteString进行排序，它旨在提供可与其他语言相媲美的性能。
Stack Overflow用户
发布于 2009-08-01 06:16:50
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编辑:已修复。
Stack Overflow用户
发布于 2009-08-01 00:22:35
我不确定这是否是您的问题的原因，但请记住，列表是一种顺序数据结构。特别是，length xs和splitAt n xs都将花费与列表长度(O(n))成正比的时间量。
在C和Java中，您最有可能使用的是数组，这两个操作都需要恒定的时间(O(1))。
编辑:关于如何使其更高效的问题，您也可以在Haskell中使用数组。
https://stackoverflow.com/questions/1215432
复制相似问题