ソートのお話です。今まで例題としてクイックソートと挿入ソートを取り上げました。データ数を N とすると、挿入ソートの実行時間は N2 に比例します。挿入ソートは遅いソートですが、クイックソートは高速なソートで、実行時間は N * log2 N に比例します。
ところがクイックソートにも弱点があり、枢軸の選び方によっては実行時間が N2 に比例する遅いソートになってしまいます。リストの場合、枢軸を自由に選ぶことが難しいので、クイックソートはリスト向きのアルゴリズムとはいえません。
そこで、今回はリストに適したソートアルゴリズムである「マージソート (merge sort)」を取り上げます。データ数を N とすると、マージソートの実行時間は N * log2 N に比例します。
マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速になります。ただし、クイックソートとは違って、データによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれます。
まず最初にマージから説明します。「マージ (併合)」とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。
┌─ [1; 3; 5] : リスト a
[] ←┤
└─ [2; 4; 6] : リスト b
小さい方をセットする
┌─ [3; 5] : リスト a
[1] ←┘
[2; 4; 6] : リスト b
1 をセットする
[3; 5] : リスト a
[1; 2] ←┐
└─ [4; 6] : リスト b
2 をセットする
データがなくなるまで繰り返す
図 1 : リストのマージ
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
それでは、実際にプログラムを作ってみましょう。次のリストを見てください。
リスト 9 : リストのマージ
let rec merge xs ys =
match (xs, ys) with
([], _) -> ys
| (_, []) -> xs
| (x1:: xs1, y1::ys1) ->
if x1 < y1 then x1::merge xs1 ys else y1::merge xs ys1
関数 merge の引数 xs と ys がマージするリストです。最初の節はリスト xs が空リストになった場合で、リスト ys をそのまま返します。2 番目の節はリスト ys が空リストになった場合で、リスト xs をそのまま返します。この 2 つの節が再帰呼び出しの停止条件になります。
リスト xs と ys にデータがあれば、先頭要素 x1 と y1 を比較します。x1 が小さい場合は x1 を、そうでなければ y1 を merge が返すリストに追加します。merge を再帰呼び出しするときは、追加する先頭要素をリストから取り除くことに注意してください。これでリストをマージすることができます。
簡単な実行例を示しましょう。
val merge: xs: 'a list -> ys: 'a list -> 'a list when 'a: comparison
> merge [1; 3; 5; 7] [2; 4; 6; 8];; val it: int list = [1; 2; 3; 4; 5; 6; 7; 8] > merge [10; 20; 30] [1; 2; 3; 4];; val it: int list = [1; 2; 3; 4; 10; 20; 30]
マージソートは、このマージを使ってデータをソートします。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 2 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。
実際にプログラムを作る場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。
リスト 10 : マージソート
// 先頭から n 個の要素を削除する
let rec drop xs n =
match (xs, n) with
((_, 0) | ([], _)) -> xs
| (_ :: ys, _) -> drop ys (n - 1)
// マージソート
let rec merge_sort n xs =
match (n, xs) with
(_, []) -> []
| (1, x::xs) -> [x]
| (2, x1::x2::xs) ->
if x1 < x2 then [x1; x2] else [x2; x1]
| (_, _) ->
let m = n / 2 in
merge (merge_sort m xs) (merge_sort (n - m) (drop xs m))
関数 merge_sort の引数 xs がソートするリスト、引数 n がリストの長さを表します。merge_sort はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。
引数 x
｜
｜←── 長さn ──→｜
（１ ２ ３ ４ ５ ６ ７ ８）
｜←n/2→｜ ｜←n/2→｜
｜ ｜
引数 x 引数 y 再帰呼び出し
図 3 : リストの分割
merge_sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と n / 2 で表します。y はリスト x の先頭から n / 2 個の要素を取り除けば求めることができます。
この処理を関数 drop で行います。drop は list の先頭から n 個の要素を取り除きます。リストに対して n 回だけ tail を適用すると考えてもかまいません。簡単な例を示しましょう。
val drop: xs: 'a list -> n: int -> 'a list
> drop [1; 2; 3; 4] 0;; val it: int list = [1; 2; 3; 4] > drop [1; 2; 3; 4] 2;; val it: int list = [3; 4] > drop [1; 2; 3; 4] 4;; val it: int list = []
あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。リストの長さが 2 の場合は簡単なので、2 つの要素を比較してソート済みのリストを作成して返します。そして、merge_sort の返り値を merge でマージすればいいわけです。
それでは実行してみましょう。
val merge_sort: n: int -> xs: 'a list -> 'a list when 'a: comparison
> merge_sort 9 [5; 9; 1; 8; 2; 7; 3; 6; 4];; val it: int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
正常に動作していますね。
次の関数を定義してください。
val position_if: pred: ('a -> bool) -> _arg1: 'a list -> 'a option
val count_if: pred: ('a -> bool) -> xs: 'a list -> int
val product_set: xs: 'a list -> ys: 'b list -> ('a * 'b) list
val power_set: _arg1: 'a list -> 'a list list
val sieve: n: int -> int list
リスト : 解答例
let rec position_if pred = function
[] -> None
| x::xs -> if pred x then Some x else position_if pred xs
let count_if pred xs =
let rec count xs a =
match xs with
[] -> a
| y::ys -> count ys (if pred y then a + 1 else a)
count xs 0
(* 別解 *)
let count_if1 pred xs =
List.fold (fun a x -> if pred x then a + 1 else a) 0 xs
let rec flatten = function
[] -> []
| x::xs -> x @ flatten xs
let flatmap f xs = flatten (List.map f xs)
let product_set xs ys =
flatmap (fun x -> List.map (fun y -> (x, y)) ys) xs
let rec power_set = function
[] -> [[]]
| x::xs -> (power_set xs) @ (List.map (fun ys -> x::ys) (power_set xs))
let rec iota n m =
if n > m then []
else n :: iota (n + 1) m
let rec rev_append xs ys =
match xs with
[] -> ys
| x::xs1 -> rev_append xs1 (x::ys)
let sieve n =
let rec sieve_sub xs a =
match xs with
[] -> a
| x::xs as ys ->
if x * x > n then rev_append a ys
else sieve_sub (List.filter (fun y -> y % x <> 0) xs) (x::a)
sieve_sub (iota 2 n) []
> position_if (fun x -> x % 2 = 0) [1;2;3;4;5;6;7;8];; val it: int option = Some 2 > position_if (fun x -> x % 7 = 0) [1;2;3;4;5;6;7;8];; val it: int option = Some 7 > position_if (fun x -> x % 9 = 0) [1;2;3;4;5;6;7;8];; val it: int option = None > count_if (fun x -> x % 2 = 0) [1;2;3;4;5;6;7;8];; val it: int = 4 > count_if (fun x -> x % 4 = 0) [1;2;3;4;5;6;7;8];; val it: int = 2 > count_if (fun x -> x % 9 = 0) [1;2;3;4;5;6;7;8];; val it: int = 0 > product_set [1;2;3] [4;5];; val it: (int * int) list = [(1, 4); (1, 5); (2, 4); (2, 5); (3, 4); (3, 5)] > product_set [1;2;3] [4;5;6];; val it: (int * int) list = [(1, 4); (1, 5); (1, 6); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6)] > power_set [1;2;3;4];; val it: int list list = [[]; [4]; [3]; [3; 4]; [2]; [2; 4]; [2; 3]; [2; 3; 4]; [1]; [1; 4]; [1; 3]; [1; 3; 4]; [1; 2]; [1; 2; 4]; [1; 2; 3]; [1; 2; 3; 4]] > sieve 100;; val it: int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97] > sieve 500;; val it: int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499]