7

昨夜、Haskell の学習を始めたばかりで、関数型プログラミング言語を使用したことがありません。マージソートの実装が良いか悪いか、正確には何が良いか悪いかを知りたいだけです。多分それは間違っているかもしれません-ソートはしますが、アルゴリズムはマージソートとは何かと私が思うものではないかもしれません。

ここで改善できることをすべて教えてください。私自身、かなり明確でシンプルな実装だと思います。あなたのアドバイスをありがとう、ここにコードがあります:)

merge [] ys = ys
merge xs [] = xs
merge xs ys =  sorted : merge left right
                where 
                    sorted = if head(xs) < head(ys) then head(xs) else head(ys)
                    left = if head(xs) <= head(ys) then tail(xs) else xs
                    right = if head(xs) > head(ys) then tail(ys) else ys

msort [] = []
msort [x] = [x]
msort xs = merge (msort left) (msort right)
            where 
                left = take (div (length xs) 2) xs
                right = drop (div (length xs) 2) xs
4

1 に答える 1

14

まず第一に、パターン マッチングを使用してマージをもう少しエレガントに書き直すことができます。

merge [] ys = ys
merge xs [] = xs
merge xs@(x:xs1) ys@(y:ys1)
    | x <= y = x : merge xs1 ys
    | otherwise = y : merge xs ys1

head一般に、andは少し安全ではない (空のリストに対してエラーが発生する) ため、使用を避けtail、可能な限りパターン マッチングを使用する必要があります。

の実装はmsort、より効率的な方法でリストを分割できることを除いて、かなり適切です。それlength xsは - 完了するのに O(N) かかるからです。コンパイラはユーザーを保存し、呼び出しの結果をキャッシュしlengthて、2 番目の呼び出しがlengthリストを再度トラバースしないようにする場合があります。しかし、takeanddropはさらに 2 つのトラバーサルを発生させるため、3 つのトラバーサルを使用してリストを分割すると、コストが高くなる可能性があります。次のように、リストを 2 つのリストに分割することで、より良い結果を得ることができます。

msort [] = []
msort [x] = [x]
msort xs = merge (msort first) (msort second)
    where
        (first, second) = splitInHalves xs
        splitInHalves [] = ([], [])
        splitInHalves [x] = ([x], [])
        splitInHalves (x:y:xs) =
            let (xs1, ys1) = splitInHalves xs
            in  (x:xs1, y:ys1)

これにより、O（NlogN）時間で同じマージソートが得られます。おそらく、C などの命令型言語で (元のリストを変更することによって) その場で実装するため、異なる感じがします。このバージョンは、メモリのコストがわずかに高くなりますが、利点があります。であるため、より保守しやすく、アルゴリズム自体以外は何も気にせずに並列化するのが非常に簡単です。これは、優れたプログラミング言語がそれを使用する開発者に提供する必要があるものです。

編集1：

構文が少し多い場合は、次のリソースを参照してください。

  • パターン マッチング@-シンボルを含むビットはas-patternと呼ばれます。あなたはそこにそれを見つけるでしょう
  • letは、それに続く式で使用される変数を宣言するために使用されるキーワードです (一方where、前の式で変数をバインドします)。ガード ( が付いているもの) を含む Haskell 構文の詳細については、 Learn You a Haskell| condition = valueのこの章を参照してください。

編集2：

@is7s は、 functionsplitInHalvesを使用するはるかに簡潔なバージョンを提案しました:foldr 

splitInHalves = foldr (\x (l,r) -> (x:r,l)) ([],[])

編集3：

マージソートの代替実装を提供する別の回答を次に示します。これには、安定しているというプロパティもあります。

遅延評価と時間の複雑さ

これがお役に立てば幸いです。関数型プログラミングの素晴らしい世界へようこそ!

于 2012-11-19T14:46:50.173 に答える