3

これは、命令型スタイルを使用してF＃でマージソートを実装した方法です。

let merge (l1: List<string>,  l2: List<string>) = 
 let r: List<string> = new List<string>()
 let mutable (i,j, cnt1, cnt2) =  (0,0, l1.Count, l2.Count)
 while i < cnt1 && j < cnt2 do
    if l1.[i] <= l2.[j] then
        r.Add (l1.[i])
        i <- i + 1
    else
        r.Add (l2.[j])
        j <- j + 1

 if i = cnt1 then
    while j < cnt2 do
        r.Add (l2.[j])
        j <- j + 1
 else    
    while i < cnt1 do
        r.Add (l1.[i])
        i <- i + 1
 r

これを代替の「機能的な」スタイルの実装に変換し、可能であればどのように機能するかを説明できますか？現在、リスト内包表記などを勉強していますが、ここで使用するというアイデアは思いつきません。

4

2 に答える 2

4

混乱を避けるために、F＃でResizeArray<'T>List<'T>に名前が変更された.NETを使用しています。関数リストを使用する場合、関数は次のようになります。merge

let merge(xs, ys) =
    let rec loop xs ys acc =
        match xs, ys with
        | [], [] -> List.rev acc (* 1 *)
        | [], y::ys' -> loop xs ys' (y::acc) (* 2 *)
        | x::xs', [] -> loop xs' ys (x::acc) (* 3 *)
        | x::xs', y::_ when x <= y -> loop xs' ys (x::acc) (* 4 *)
        | _::_, y::ys' -> loop xs ys' (y::acc) (* 5 *)
    loop xs ys []

命令型の観点からこの機能を説明するには：

  • 4番目と5番目のパターンは、while2つの現在の要素を比較し、小さい方の要素を結果のリストに追加する最初のループに対応しています。
  • while2番目と3番目のパターンは、2番目と3番目のループに似ています。
  • i = cnt1最初のパターンは、とj = cnt2が結果を返す必要がある場合です。新しい要素は常にアキュムレータの前に付加されるため、昇順でリストを取得するには、それを逆にする必要があります。

正確には、merge関数はマージソートアルゴリズムの一部にすぎません。リストを2つに分割し、2つの半分でmerge-sortを呼び出し、2つのソートされた半分を1つにマージする関数が必要です。以下のsplit機能は演習として残されています。

let rec mergeSort ls =
    match ls with
    | [] | [_] -> ls
    | _  -> let xs, ys = split ls
            let xs', ys' = mergeSort xs, mergeSort ys
            merge(xs', ys')
于 2012-09-09T15:28:46.730 に答える
1

パッドのよりシンプルだが素朴な代替手段を追加するには：

let rec merge x y = 
    match (x, y) with
    | ([], []) -> []
    | ([], rest) -> rest
    | (rest, []) -> rest
    | (fx :: xs, fy :: _) when fx <= fy -> fx :: merge xs y
    | (fx :: _, fy :: ys) -> fy :: merge x ys

パッドと同様に、関数パラメーターのパターンマッチングを行っています。

  • 最初にそれらをタプルに入れて、両方を同時にパターンマッチングできるようにします。
  • 次に、両方またはいずれかのパラメーターが空の基本ケースを処理します。
  • 次に、whenガードを使用して、最初のどのアイテムが小さいかを確認します
  • merge私は最終的に最初のアイテムを取得し、それを、小さいアイテムが取得された残りのアイテムと他のリスト全体を使用した別の呼び出しの結果に変換します。したがって、の最初の項目xが小さい場合は、（の最初の項目が大きかったため）の残りの部分と全体（の最初の項目が大きかったため）を渡す呼び出しの結果にx（この場合）の最初の項目を追加します。fxmergexxsyy
于 2012-09-11T19:07:21.680 に答える