19

Haskell は初めてで、いくつかの既知のアルゴリズムを実装しようとしています。

文字列にマージソートを実装しました。C および Java の実装と比較して、私の Haskell 実装のパフォーマンスには少しがっかりしています。私のマシン (Ubuntu Linux、1.8 GHz) では、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 を初めて使用するので、実装をより時間/スペース効率的にできるかどうか知りたいです。

ヒントを事前にありがとうジョルジオ

私の実装:

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. 悪い考えは、最初にリストを分割することです。その代わりに、1つのメンバーリストのリストを作成するだけです。Haskellは怠惰です、それは適切なタイミングで行われます。
  2. 次に、リストが1つになるまで、リストのペアをマージします。

編集：この回答に反対票を投じた人：上記のマージソートの実装は、cmp関数が削除されていることを除いて、ghcData.List.sortで使用されているものと同じアルゴリズムです。ghcの作者は間違っているかもしれません：-/

于 2009-08-01T19:55:15.767 に答える
14

Haskell では、文字列は文字の遅延リストであり、他のリストと同じオーバーヘッドがあります。サイモン・ペイトン・ジョーンズが 2004 年に行った話を聞いたときのことを思い出すと、GHC のスペース・コストは 1 文字あたり 40 バイトです。同じもの同士を比較するには、おそらく sortingData.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 に答える