一般に関数型言語の場合、関数の引数や let で定義した局所変数の値を書き換えることはできません。ところが、ML 系の言語 (SML/NJ, OCaml) の場合、「配列 (array)」と「参照 (reference)」というデータ型を使うと、その値を書き換えることができます。OCaml のモジュール Array には配列を操作する便利な関数が用意されていますが、今回は OCaml の勉強ということで、「ベクタ (1 次元配列)」を操作する便利な関数や高階関数を実際に作ってみましょう。
最初にベクタの中からデータを探索する関数を作ります。いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching)」といます。次のリストを見てください。
リスト : データの探索
(* x と等しい要素があるか *)
let member x vec =
let rec iter n m =
if n >= m then false
else if x = vec.(n) then true
else iter (n + 1) m
in
iter 0 (Array.length vec)
(* 述語 pred が真となる要素があるか *)
let member_if pred vec =
let rec iter n m =
if n >= m then false
else if pred vec.(n) then true
else iter (n + 1) m
in
iter 0 (Array.length vec)
(* x と等しい要素の位置を返す *)
let position x vec =
let rec iter n m =
if n >= m then None
else if vec.(n) = x then Some n
else iter (n + 1) m
in
iter 0 (Array.length vec)
(* 述語 pred が真となる要素の位置を返す *)
let position_if pred vec =
let rec iter n m =
if n >= m then None
else if pred vec.(n) then Some n
else iter (n + 1) m
in
iter 0 (Array.length vec)
(* 述語 pred が真となる要素を返す *)
let find_if pred vec =
let rec iter n m =
if n >= m then None
else if pred vec.(n) then Some vec.(n)
else iter (n + 1) m
in
iter 0 (Array.length vec)
(* 述語 pred が真となる要素の個数を返す *)
let count_if pred vec =
let rec iter n m a =
if n >= m then a
else if pred vec.(n) then iter (n + 1) m (a + 1)
else iter (n + 1) m a
in
iter 0 (Array.length vec) 0
val member : 'a -> 'a array -> bool = <fun>
val member_if : ('a -> bool) -> 'a array -> bool = <fun>
val position : 'a -> 'a array -> int option = <fun>
val position_if : ('a -> bool) -> 'a array -> int option = <fun>
val find_if : ('a -> bool) -> 'a array -> 'a option = <fun>
val count_if : ('a -> bool) -> 'a array -> int = <fun>
どの関数も局所関数 iter で探索処理を行います。n がベクタの添字を、m がベクタの大きさを表します。ベクタの要素を先頭から順番に調べていき、n が m 以上になったならば、すべての要素を調べたので探索は失敗となります。
関数 member はベクタ vec から引数 x と等しい要素を探します。member_if は述語 pred が真を返す要素を探します。見つけた場合は true を返し、見つからない場合は false を返します。関数 postion と position_if は見つけた要素の位置 (添字) を返します。関数 find_if は見つけた要素を返します。関数 count_if は述語 pred が真を返す要素の個数を求めます。
簡単な実行例を示しましょう。
# member 3 [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : bool = true # member 10 [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : bool = false # member_if (fun x -> x mod 2 = 0) [|1;2;3;4;5;6;7;8;9|];; - : bool = true # member_if (fun x -> x mod 10 = 0) [|1;2;3;4;5;6;7;8;9|];; - : bool = false # position 3 [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int option = Some 2 # position 10 [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int option = None # position_if (fun x -> x mod 5 = 0) [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int option = Some 4 # position_if (fun x -> x mod 10 = 0) [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int option = None # find_if (fun x -> x mod 3 = 0) [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int option = Some 3 # find_if (fun x -> x mod 10 = 0) [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int option = None # count_if (fun x -> x mod 3 = 0) [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int = 3 # count_if (fun x -> x mod 10 = 0) [|1; 2; 3; 4; 5; 6; 7; 8; 9|];; - : int = 0
このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、例題で取り上げる「二分探索」や他の高速な探索アルゴリズム [*1] を使ってみてください。
次はベクタ用の高階関数を作ってみましょう。なお、これから作成する関数のほとんどは標準モジュール Array に用意されています。最初はマップ関数からです。
リスト : ベクタ用マップ関数
let map fn vec =
let k = Array.length vec in
let a = Array.make k (fn vec.(0)) in
for i = 1 to k - 1 do
a.(i) <- fn vec.(i)
done;
a
(* 破壊的操作 *)
let map_into fn vec =
let k = Array.length vec in
for i = 0 to k - 1 do
vec.(i) <- fn vec.(i)
done;
vec
(* インデックス (添字) も関数 fn に渡す *)
let map_index fn vec =
let k = Array.length vec in
let a = Array.make k (fn 0 vec.(0)) in
for i = 1 to k - 1 do
a.(i) <- fn i vec.(i)
done;
a
val map : ('a -> 'b) -> 'a array -> 'b array = <fun>
val map_into : ('a -> 'a) -> 'a array -> 'a array = <fun>
val map_index : (int -> 'a -> 'b) -> 'a array -> 'b array = <fun>
マップ関数も簡単です。最初に新しいベクタを Array.make で作成して局所変数 a にセットします。Array.make は初期値が必要になるので、fn vec.(0) で初期値を求めています。あとは、ベクタ vec の要素に関数 fn を適用して、その返り値をベクタ a にセットするだけです。この処理を for 文でプログラムしています。
また、関数 map_into のように、引数のベクタ vec を直接書き換えることも簡単にできます。この場合、関数 fn の返り値は vec の要素と同じデータ型であることと、引数の vec は破壊されることに注意してください。map_index は要素だけではなく添字も関数 fn に渡します。
簡単な実行例を示しましょう。
# let a = [|1; 2; 3; 4; 5|];; val a : int array = [|1; 2; 3; 4; 5|] # map (fun x -> (x, x)) a;; - : (int * int) array = [|(1, 1); (2, 2); (3, 3); (4, 4); (5, 5)|] # map (fun x -> x * x) a;; - : int array = [|1; 4; 9; 16; 25|] # map_into (fun x -> x * x) a;; - : int array = [|1; 4; 9; 16; 25|] # a;; - : int array = [|1; 4; 9; 16; 25|] # map_index (fun x y -> (x, y)) a;; - : (int * int) array = [|(0, 1); (1, 4); (2, 9); (3, 16); (4, 25)|]
次は畳み込みを行う関数を作ります。
リスト : 畳み込み
let fold_left fn a vec =
let acc = ref a in
for i = 0 to (Array.length vec) - 1 do
acc := fn !acc vec.(i)
done;
!acc
let fold_right fn a vec =
let acc = ref a in
for i = (Array.length vec) - 1 downto 0 do
acc := fn vec.(i) !acc
done;
!acc
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a = <fun>
val fold_right : ('a -> 'b -> 'b) -> 'b -> 'a array -> 'b = <fun>
関数 fold_left はベクタの先頭から、関数 fold_right はベクタの最後尾から順番に要素を取り出して畳み込み処理を行います。ベクタは最後尾の要素にも簡単にアクセスできるので、fold_right も繰り返しで処理することができます。
それでは簡単な例を示しましょう。
# fold_left (+) 0 [|1; 2; 3; 4; 5|];; - : int = 15 # fold_right (+) 0 [|1; 2; 3; 4; 5|];; - : int = 15 # let cons a b = a::b;; val cons : 'a -> 'a list -> 'a list = <fun> # fold_right cons [] [|1; 2; 3; 4; 5|];; - : int list = [1; 2; 3; 4; 5]
イテレータも簡単に作ることができます。次のリストを見てください。
リスト : ベクタのイテレータ
let iter fn vec =
for i = 0 to (Array.length vec) - 1 do
fn vec.(i)
done
let iter_index fn vec =
for i = 0 to (Array.length vec) - 1 do
fn i vec.(i)
done
val iter : ('a -> 'b) -> 'a array -> unit = <fun>
val iter_index : (int -> 'a -> 'b) -> 'a array -> unit = <fun>
関数 iter はベクタの要素に関数 fn を適用します。関数 iter_index はベクタの要素と添字を関数 fn に渡します。どちらの関数も返り値は unit です。簡単な実行例を示します。
- : unit = () # iter (fun x -> print_int x; print_newline ()) [|1; 2; 3; 4; 5|];; 1 2 3 4 5 - : unit = () # iter_index (fun x y -> print_int (x * y); print_newline ()) [|1; 2; 3; 4; 5|];; 0 2 6 12 20 - : unit = ()
一般に、関数型言語の世界ではリストが主役なので、データをリストに格納しておく方が便利な場合があります。したがって、OCaml では配列を使う機会はあまり多くないと思いますが、だからといって、配列が役に立たないわけではありません。配列を上手に使いこなすためには、リストと配列の違い、とくにベクタとの違いをよく理解しておくことが重要です。ここで、 2 つのデータ型の長所と短所を比較してみましょう。
まず、リストの構造を思い出してください。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
10 20 30 40
図 : リスト (10 20 30 40) の構造
リストは複数のコンスセルを接続して構成されています。コンスセルはデータを格納する場所と、次のコンスセルを示す場所からなっていましたね。このリストの先頭に、新しいデータを追加してみましょう。これは、演算子 :: を使うと簡単にできます。
# let a = [10;20;30;40];; val a : int list = [10; 20; 30; 40] # let b = 50 :: a;; val b : int list = [50; 10; 20; 30; 40]
逆に、先頭のデータを取り外すには List.tl を使えばいいですね。
# let c = List.tl b;; val c : int list = [10; 20; 30; 40]
このように、リストはコンスセルをつないでデータを追加したり、コンスセルを外すことでデータを削除することができます。つまり、コンスセルを操作することで、その長さを自由に変更することができるのです。
今度は、ベクタ [|10; 20; 30; 40|] の先頭に新しいデータを追加することを考えてみましょう。ところで、ベクタの大きさは Array.make で作成したときに指定しましたね。ベクタは一度大きさを決めると、それ以上大きさを増やすことはできません。これはＣ言語でも同じです。したがって、ベクタの大きさを増やすには、必要な大きさのベクタを新しく確保して、元のベクタからデータをコピーするしかありません。
添字 ０ １ ２ ３
┌─┬─┬─┬─┐
ベクタ│10│20│30│40│
└─┴─┴─┴─┘
50 を追加───┐ │ │ │ │ コピーする
↓ ↓ ↓ ↓ ↓
┌─┬─┬─┬─┬─┐
ベクタ│50│10│20│30│40│ 新しいベクタ
└─┴─┴─┴─┴─┘
添字 ０ １ ２ ３ ４
図 : ベクタの先頭にデータを追加する場合
これは、ベクタが連続したメモリ領域に割り当てられているためで、リストのようにコンスセルをつないでデータを増やす、というわけにはいかないのです。
データを削除する場合も同様です。この場合、新しいベクタを用意するのが面倒であれば、データの移動で済ますことができます。
添字 ０ １ ２ ３ ４
┌─┬─┬─┬─┬─┐
ベクタ│50│10│20│30│40│
└─┴─┴─┴─┴─┘
↑ 有効なデータの範囲
添字 ０ １ ２ ３ ４
┌─┬─┬─┬─┬─┐
ベクタ│10│20│30│40│40│ データを前へ移動
└─┴─┴─┴─┴─┘
↑
有効なデータの範囲
図 : ベクタの先頭からデータを削除
この方法では、データの移動のほかにも、ベクタの有効範囲を管理しなくてはならないので、その分だけ処理が複雑になってしまいます。
ここまでの説明で、リストの長所とベクタの短所は、おわかりいただけたかと思います。リストはデータの追加や削除が簡単で、リストの大きさも自由に変更できます。ベクタは一度決めた大きさを変更することはできないので、データの追加や削除は簡単に行うことができません。
今度は逆に、リストの短所とベクタの長所について説明しましょう。たとえば、[60; 50; 40; 30; 20; 10] というリストで、4 番目のデータを求めることを考えてみます。これは List.nth を使うと簡単です。
# List.nth [60; 50; 40; 30; 20; 10] 4;; - : int = 20
ここで、List.nth の処理を考えてみます。リストは、コンスセルをつなげて構成されています。リストの先頭の要素はすぐに求めることができますが、4 番目の要素を求めるには、先頭から順番にコンスセルをたどっていき、目的のコンスセルに到達したところで、ようやく要素を求めることができるのです。プログラム上では、List.nth を使って簡単に処理できるように見えますが、OCaml 内部では懸命にコンスセルをたどる処理を行っているのです。
これに対して、ベクタは連続したメモリ領域に用意されたデータ構造です。データは、この領域に順番に並べられます。OCaml の場合、データを格納する領域の大きさは、データ型の種類にかかわらず一定です。したがって、4 番目のデータを格納している領域は、単純な計算で求めることができるのです。リストのように、先頭から順番にデータをたどる必要はありません。Ｃ言語の場合も、配列に同じデータ型が格納されるので、単純な計算で指定した要素にアクセスすることができます。
このように、リストではコンスセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかりますが、ベクタはどの要素でも一定の時間でアクセスすることができます。つまり、配列はランダムアクセスが得意なデータ構造なのです。これが配列の長所です。
次は、ベクタの応用例として「二分探索 (バイナリサーチ：binary searching)」を例題として取り上げます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。これに対し二分探索は log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめ昇順に並べておく (ソートしておく) 必要があります。このため、二分探索は線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
[11 22 33 44 55 66 77 88 99] key は 66
↑ 66 > 55 後半を探す
11 22 33 44 55 [66 77 88 99] 88 > 66 前半を探す
↑
11 22 33 44 55 [66 77] 88 99 77 > 66 前半を探す
↑
11 22 33 44 55 [66] 77 88 99 66 = 66 発見
↑
図 : 二分探索
二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。
あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。
上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。
二分探索は要素をランダムアクセスすることになるので、リストには不向きのアルゴリズムです。そこで、ベクタからデータを二分探索するプログラムを作ってみましょう。二分探索は簡単にプログラムできます。次のリストを見てください。
リスト : 二分探索
let intcmp x y = x - y
let binary_search x vec cmp =
let rec iter low high =
if low > high then false
else
let mid = (low + high) / 2 in
let result = cmp x vec.(mid) in
if result = 0 then true
else if result < 0 then iter low (mid - 1)
else iter (mid + 1) high
in
iter 0 ((Array.length vec) - 1)
val binary_search : 'a -> 'b array -> ('a -> 'b -> int) -> bool = <fun>
関数 binary_search はベクタ vec の中から x と等しい要素を二分探索し、見つけた場合は true を返します。見つからない場合は false を返します。x と要素の比較は引数 cmp に渡された比較関数で行います。cmp x y は x < y ならば負の値を、x = y ならば 0 を、x > y ならば正の値を返すこととします。整数値の場合は関数 intcmp のように定義すると簡単です。
実際の処理は局所関数 iter で行います。引数 low と high で探索する区間を表します。最初に iter を呼び出すとき、low は 0 で high は (Array.length vec) - 1 になります。iter は区間の中央値を求めて変数 mid にセットします。そして、関数 cmp で x と mid の位置の要素を比較して、その結果を変数 result にセットします。result が 0 の場合は探索成功なので true を返します。
r が 0 よりも小さい場合は区間の前半を調べるため、iter を再帰呼び出しするときの区間は low (mid - 1) となります。逆に、r が 0 よりも大きい場合は区間の後半を調べます。iter を再帰呼び出しするときの区間は (mid + 1) high となります。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので false を返します。
これでプログラムは完成です。簡単な実行例を示しましょう。
# binary_search 50 [|10; 20; 30; 40; 50; 60; 70; 80; 90|] intcmp;; - : bool = true # binary_search 55 [|10; 20; 30; 40; 50; 60; 70; 80; 90|] intcmp;; - : bool = false # binary_search 0 [|10; 20; 30; 40; 50; 60; 70; 80; 90|] intcmp;; - : bool = false # binary_search 100 [|10; 20; 30; 40; 50; 60; 70; 80; 90|] intcmp;; - : bool = false
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
次は「挿入ソート (insert sort)」を取り上げます。挿入ソートの考え方はとても簡単です。ソート済みのベクタに新しいデータを挿入していくことでソートを行います。下図を見てください。
最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから要素を順番に比較するとき、いっしょにデータの移動も行うことにします。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 挿入ソート
プログラムは次のようになります。
リスト : 挿入ソート
let insert_sort vec =
let rec insert_element x n =
if n >= 0 && x < vec.(n) then (
vec.(n + 1) <- vec.(n);
insert_element x (n - 1)
) else
vec.(n + 1) <- x
in
for i = 1 to (Array.length vec) - 1 do
insert_element vec.(i) (i - 1)
done;
vec
引数 vec はソートするベクタです。局所関数 insert_element はデータ x を 0 から n 番目のデータの中に挿入します。具体的には x 以下となる n 番目の要素を求めます。n 番目の要素が x よりも大きい場合は、その要素を n + 1 番目に移動して n - 1 番目の要素を調べます。x 以下の要素が見つかった場合、または n が 0 よりも小さくなった場合、n + 1 番目に x を挿入します。あとは、1 番目の要素から順番に insert_element で挿入していくだけです。
それでは実行してみましょう。
# let a = [|5; 6; 7; 4; 3; 2; 8; 9; 1|];; val a : int array = [|5; 6; 7; 4; 3; 2; 8; 9; 1|] # insert_sort a;; - : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9|] # a;; - : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9|]
ところで挿入ソートの場合、データの挿入位置を決めるときに二分探索を使うことができます。次のリストを見てください。
リスト : 挿入ソート (二分探索バージョン)
let insert_sort1 vec =
let rec binary_search x low high =
if low >= high then low
else
let mid = (low + high) / 2 in
if vec.(mid) <= x then binary_search x (mid + 1) high
else binary_search x low mid
in
for i = 1 to (Array.length vec - 1) do
if vec.(i - 1) > vec.(i) then
let j = binary_search vec.(i) 0 (i - 1) in
let tmp = vec.(i) in
for k = i downto j + 1 do
vec.(k) <- vec.(k - 1)
done;
vec.(j) <- tmp
done;
vec
局所関数 binary_search はデータ x の挿入位置を求めます。x と等しいデータが複数ある場合、その最後尾に x を追加するため、x 以上の要素がある間は二分探索を続けます。low が high 以上になったら探索を終了します。low が挿入位置になります。あとは、1 番目の要素から順番に binary_search で挿入位置を求めて、データを一つずつ後ろに動かしてから、その位置にデータを挿入します。
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
最後に「クイックソート (quick sort)」を作りましょう。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々のグループを同様に分割して 2 つのグループに分けます。最後はグループの要素がひとつになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つのグループについて再び
同様な分割を行う
図 : クイックソート
今回は中央にある要素を枢軸に選ぶことにしましょう。図 4 を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つのグループに適用します。これは再帰定義を使えば簡単に実現できます。分割したグループの要素数が 1 以下になったときが再帰の停止条件になります。プログラムは次のようになります。
リスト : クイックソート
let rec quick_sort vec =
let rec partition pivot low high =
let swap n m =
let tmp = vec.(n) in vec.(n) <- vec.(m); vec.(m) <- tmp
in let rec search_fore n =
if pivot <= vec.(n) then n else search_fore (n + 1)
in let rec search_back n =
if pivot >= vec.(n) then n else search_back (n - 1)
in
let i = search_fore low and
j = search_back high
in
if i < j then (
swap i j;
partition pivot (i + 1) (j - 1)
) else (i, j)
in let rec sort low high =
let (i, j) = partition vec.((low + high) / 2) low high in
if low < i - 1 then sort low (i - 1) else ();
if high > j + 1 then sort (j + 1) high else ()
in
sort 0 ((Array.length vec) - 1);
vec
実際の処理は局所関数 sort で行います。引数 low が区間の下限値、high が区間の上限値です。区間の分割は局所関数 partition で行います。最初の引数 pivot が枢軸です。今回は区間の中央にあるデータを枢軸として選びます。
そして、局所関数 search_fore で区間の前から枢軸以上のデータを探して、その位置を変数 i にセットします。次に、局所関数 search_back で区間の後ろから枢軸以下のデータを探して、その位置を変数 j にセットます。枢軸が番兵になるので、区間をオーバーすることはありません。
i < j であれば、i 番目と j 番目の要素を局所関数 swap で交換します。i >= j の場合、区間の分割は終了しました。i と j をタプルにまとめて返します。そして、区間 (low, i - 1) にデータが 2 つ以上ある場合、sort を再帰呼び出しして区間をソートします。同様に、区間 (j + 1, high) にデータが 2 つ以上ある場合、その区間を sort でソートします。
それでは実際に実行してみましょう。
# let a = [|5; 6; 4; 7; 3; 8; 2; 9; 1|];; val a : int array = [|5; 6; 4; 7; 3; 8; 2; 9; 1|] # quick_sort a;; - : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9|] # a;; - : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9|]
クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中間値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数を N とすると N * log2 N に比例する時間でソートすることができます。
逆に、区間での最大値または最小値を枢軸に選ぶと、その要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。つまり、挿入ソートと同じくらい遅いソートになるのです。
この問題は枢軸の選び方を工夫することで、完全ではありませんが回避することができます。区間の中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は少なくなりますが、値を選ぶのに時間がかかってしまいます。実際には 3 つから 5 つの要素を選んで、その中で中央の値を持つ要素を枢軸とする場合が多いようです。
次の関数を定義してください。
リスト : 身長のデータ
let height =
[|148.7; 149.5; 133.7; 157.9; 154.2; 147.8; 154.6; 159.1; 148.2; 153.1;
138.2; 138.7; 143.5; 153.2; 150.2; 157.3; 145.1; 157.2; 152.3; 148.3;
152.0; 146.0; 151.5; 139.4; 158.8; 147.6; 144.0; 145.8; 155.4; 155.5;
153.6; 138.5; 147.1; 149.6; 160.9; 148.9; 157.5; 155.1; 138.9; 153.0;
153.9; 150.9; 144.4; 160.3; 153.4; 163.0; 150.9; 153.3; 146.6; 153.3;
152.3; 153.3; 142.8; 149.0; 149.4; 156.5; 141.7; 146.2; 151.0; 156.5;
150.8; 141.0; 149.0; 163.2; 144.1; 147.1; 167.9; 155.3; 142.9; 148.7;
164.8; 154.1; 150.4; 154.2; 161.4; 155.0; 146.8; 154.2; 152.7; 149.7;
151.5; 154.5; 156.8; 150.3; 143.2; 149.5; 145.6; 140.4; 136.5; 146.9;
158.9; 144.4; 148.1; 155.5; 152.4; 153.3; 142.3; 155.3; 153.1; 152.3|]
階級 度数 累積度数 ------------------------ 130 - 135 1 1 135 - 140 6 7 140 - 145 12 19 145 - 150 25 44 150 - 155 32 76 155 - 160 17 93 160 - 165 6 99 165 - 170 1 100
階級はデータの範囲を表します。この表では x cm 以上 y cm 未満を x - y で表しています。度数はその階級に出現したデータの個数です。度数を示してある表のことを「度数分布表」といいます。累積度数はその階級までの度数を全部加えたものです。累積度数を示してある表を「累積度数分布表」といいます。
リスト : 解答例
(* 最大値を求める *)
let maximum xs =
let x = ref xs.(0) in
for i = 1 to Array.length xs - 1 do
if !x < xs.(i) then x := xs.(i) else ()
done;
!x
(* 別解 *)
let maximum1 xs =
Array.fold_left (fun a x -> if x > a then x else a) xs.(0) xs
(* 最小値を求める *)
let minimum xs =
let x = ref xs.(0) in
for i = 1 to Array.length xs - 1 do
if !x > xs.(i) then x := xs.(i) else ()
done;
!x
(* 別解 *)
let minimum1 xs =
Array.fold_left (fun a x -> if x < a then x else a) xs.(0) xs
(* 平均値を求める *)
let average xs =
(Array.fold_left (+.) 0.0 xs) /. (float_of_int (Array.length xs))
(* 述語 pred が真となる要素の位置を返す *)
let position_if pred vec =
let rec iter n m =
if n >= m then None
else if pred vec.(n) then Some n
else iter (n + 1) m
in
iter 0 (Array.length vec)
let get_class x limit =
match position_if (fun (low, high) -> low <= x && x < high) limit with
None -> -1
| Some n -> n
(* 出現頻度表と累積度数表を求める *)
let frequency xs =
let limit = [|(130., 135.); (135., 140.); (140., 145.); (145., 150.);
(150., 155.); (155., 160.); (160., 165.); (165., 170.)|] in
let freq = Array.make 8 0 in
let cum = Array.make 8 0 in
Array.iter
(fun x -> let n = get_class x limit in freq.(n) <- freq.(n) + 1)
height;
cum.(0) <- freq.(0);
for i = 1 to 7 do
cum.(i) <- cum.(i - 1) + freq.(i)
done;
for i = 0 to 7 do
let (low, high) = limit.(i) in
Printf.printf "%.0f - %.0f | %3d %3d\n" low high freq.(i) cum.(i)
done
# maximum [|5; 6; 4; 7; 3; 8; 2; 9; 1; 0|];; - : int = 9 # maximum1 [|5; 6; 4; 7; 3; 8; 2; 9; 1; 0|];; - : int = 9 # minimum [|5; 6; 4; 7; 3; 8; 2; 9; 1; 0|];; - : int = 0 # minimum1 [|5; 6; 4; 7; 3; 8; 2; 9; 1; 0|];; - : int = 0 # average [|5.; 6.; 4.; 7.; 3.; 8.; 2.; 9.; 1.; 0.|];; - : float = 4.5 # frequency ();; 130 - 135 | 1 1 135 - 140 | 6 7 140 - 145 | 12 19 145 - 150 | 25 44 150 - 155 | 32 76 155 - 160 | 17 93 160 - 165 | 6 99 165 - 170 | 1 100 - : unit = ()