在Haskell中合并排序 [英] Merge sort in Haskell

问题描述

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

我已经在字符串上实现了合并排序。与C和Java实现相比，我对Haskell实现的
性能有点失望。
在我的机器上（Ubuntu Linux，1.8 GHz），C（gcc 4.3.3）在1.85 s中排序1 000 000个字符串，3.68 s中排列
Java（Java SE 1.6.0_14），Haskell（GHC 6.8.2）在25.89秒。
更大的输入（10 000 000个字符串），C需要21.81 s，Java需要59.68 s，Haskell
开始交换，我更愿意在几分钟后停止程序。

由于我是Haskell的新手，我很想知道我的实现是否可以使
更加节省时间/空间。

提前感谢您提供任何提示
Giorgio

我的实施：

  merge :: [String]  - > [字符串]  - > [String] 
 merge [] ys = ys 
 merge xs [] = xs 
 merge（x：xs）（y：ys）= if x< y 
然后x：（merge xs（y：ys））
 else y：（merge（x：xs）ys）
 
 mergeSort :: [String]  - > [String] 
 mergeSort xs = if（l <2）
 then xs 
 else merge ht 
 where l = length xs 
n = l`div` 2 
s = splitAt n xs 
h = mergeSort（fst s）
t = mergeSort（snd s）
  

<试试这个版本：

  mergesort :: [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）=合并xs ys：merge_pairs xss

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

I am new to Haskell and I am trying to implement a few known algorithms in it.

I have implemented merge sort on strings. I am a bit disappointed with the performance of my Haskell implementation compared to C and Java implementations. On my machine (Ubuntu Linux, 1.8 GHz), C (gcc 4.3.3) sorts 1 000 000 strings in 1.85 s, Java (Java SE 1.6.0_14) in 3.68 s, Haskell (GHC 6.8.2) in 25.89 s. With larger input (10 000 000 strings), C takes 21.81 s, Java takes 59.68 s, Haskell starts swapping and I preferred to stop the program after several minutes.

Since I am new to Haskell, I would be interested to know if my implementation can be made more time / space efficient.

Thank you in advance for any hint Giorgio

My implementation:

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)

解决方案

Try this version:

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. Bad idea is splitting list first. Instead of it just make list of one member lists. Haskell is lazy, it will be done in right time.
2. Then merge pairs of lists until you have only one list.

Edit: Someone who down-vote this answer: above merge sort implementation is same algorithm as used in ghc Data.List.sort except with cmp function removed. Well ghc authors are may be wrong :-/

这篇关于在Haskell中合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！