今回は Scheme プログラミング中級編にもどって、「ベクタ (vector) 」というデータ構造について説明します。ベクタは 1 次元配列のことで、手続き型言語ではおなじみのデータ構造です。Common Lisp は多次元配列を扱うことができますが、Scheme の仕様書 R5RS にはベクタしか規定されていません。もっとも、ベクタがあれば多次元配列を実装するのは難しいことではありません。実際、Gauche には多次元配列を操作するライブラリ (gauche.array) が用意されています。
まず最初に「配列 (array) 」について簡単に説明します。
配列はリストと同様に複数個のデータを格納することができます。配列に格納されたデータを「要素」と呼びます。リストは複数のコンスセルを接続して構成しますが、配列はデータを格納する変数を連続したメモリ領域に用意します。配列はホテルやマンションの部屋にたとえるとわかりやすいと思います。
ホテル全体を配列とすると、各部屋がデータを格納する変数と考えることができます。ホテルでは、ルームナンバーによって部屋を指定しますね。配列の場合も、整数値によってデータを格納する変数を指定することができます。この整数値を「添字 (subscripts) 」といいます。
添字 ０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
配列 │ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
図 : 配列の構造（その１）
たとえば、10 個のデータを格納する配列を考えてみます。これは、平屋建てのマンションで、部屋が 10 室あると考えてください。この場合は上図に示すように、データを格納する変数が並んでいて、それぞれ 0 から 9 までの添字で指定することができます。
Scheme (Lisp) の場合、添字は 0 から順番に数えます。ホテルのルームナンバーのように、4 や 9 は縁起が悪いから使わない、ということはありません。ほかのプログラミング言語、たとえばＣ言語は 0 から数えますが、PASCAL では 1 から数えます。
ところで、このマンションはたいへん好評で、隣の空き地に同じ建物を 2 つ新築しました。
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
Ａ棟(０)│ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
Ｂ棟(１)│ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
Ｃ棟(２)│ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
図 : 配列の構造（その２）
ルームナンバーは 0 から 29 というように、通しで番号をつけてもいいのですが、A 棟 0 号室とか C 棟 9 号室のようにつけると、各部屋を区別することができます。この A 棟、B 棟、C 棟を 0, 1, 2 の整数値 (添字) に対応させると、各部屋は 2 つの添字で区別することができます。添字の個数を「次元」といいます。
添字の数がひとつの配列を「1 次元配列」といい、特別に「ベクタ (vector) 」と呼びます。添字の数が 2 つの配列は「2 次元配列」といいます。これは、数学で習った「行列 (matrix) 」を思い出してもらえばいいでしょう。一般に、添字の個数が n 個であれば「n 次元配列」といいます。
たとえば、このマンションは平屋建てでしたが、これを 10 階建てに改築したとしましょう。すると、各部屋は 0 棟 1 階 2 号室というように、3 つの数値で区別することができますね。つまり、3 次元配列と考えることができます。
さて、話ばかりでは退屈なので、具体的にベクタの使い方を説明しましょう。まずは R5RS に規定されているベクタの操作関数から説明します。
ベクタは次の関数で作成します。
引数 k は要素の個数を表します。make-vector は k 個の要素を格納するベクタを作成して返します。引数 fill を指定すると、その値でベクタの各要素を初期化します。fill を省略した場合、各要素の値は未定義です。vector は引数 obj1, obj2, ... を要素とするベクタを作成して返します。関数 list のベクタ版です。
簡単な例を示しましょう。
gosh> (make-vector 5) #(#<undef> #<undef> #<undef> #<undef> #<undef>) gosh> (make-vector 5 0) #(0 0 0 0 0) gosh> (vector 1 2 3 4 5) #(1 2 3 4 5)
make-vector で初期値が指定されていない場合、Gauche は各要素を #<undef> で初期化します。ベクタは数や文字列と同じく自己評価フォームです。Scheme の場合、ベクタは #( ... ) で表記します。これは read で読み込むことがでる形式で、プログラムの中で指定することもできます。
データ型のチェックは型述語 vector? を使います。ベクタの大きさは関数 vector-length で求めることができます。簡単な例を示しましょう。
gosh> (define a (vector 1 2 3)) a gosh> a #(1 2 3) gosh> (vector? a) #t gosh> (vector? 1) #f gosh> (vector-length a) 3
ベクタの要素にアクセスするには vector-ref と vector-set! を使います。
vector-ref はベクタ vector の k 番目の要素を返します。vector-set! は vector の k 番目の要素の値を obj に書き換えます。vector-set! の返り値は未定義で、Gauche では #<undef> を返します。なお、添字がベクタの範囲を超えるとエラーになります。
簡単な使用例を示しましょう。
gosh> (define a1 (vector 10 20 30)) a1 gosh> (vector-ref a1 0) 10 gosh> (vector-ref a1 2) 30 gosh> (define a2 (make-vector 3 0)) a2 gosh> a2 #(0 0 0) gosh> (vector-set! a2 0 10) #<undef> gosh> a2 #(10 0 0) gosh> (vector-set! a2 2 100) #<undef> gosh> a2 #(10 0 100)
vector-set! は破壊的な操作であることに注意してください。もうひとつ、破壊的な操作関数を紹介しましょう。
vector-fill! はベクタ vector のすべての要素を引数 obj に書き換えます。vector-fill! の返り値は未定義です。簡単な例を示しましょう。
gosh> (define a (vector 1 2 3 4 5)) a gosh> a #(1 2 3 4 5) gosh> (vector-fill! a 0) #<undef> gosh> a #(0 0 0 0 0)
R5RS には、リストとベクタの相互変換を行う関数も用意されています。
vector->list は引数のベクタの要素を新しいリストに格納して返します。逆に、list->vector は引数のリストの要素を新しいベクタに格納して返します。簡単な例を示します。
gosh> (define a (vector 1 2 3 4 5)) a gosh> (vector->list a) (1 2 3 4 5) gosh> (define b (list 1 2 3 4 5)) b gosh> (list->vector b) #(1 2 3 4 5)
ところで、今までの例では整数値をベクタに格納しましたが、Scheme (Lisp) のベクタは S 式であればどんなデータでも格納することができます。簡単な例を示しましょう。
gosh> (vector 1 'a "abc" '(1 2 3)) #(1 a "abc" (1 2 3))
それでは簡単な例題として、ベクタ用の高階関数を作ってみましょう。なお、これから作成する関数のほとんどはライブラリ srfi-43 に用意されています。今回は Scheme のお勉強ということで、実際にプログラムを作ってみましょう。
最初にベクタの中からデータを探索する関数を作ります。いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching) 」といます。次のリストを見てください。
リスト : データの探索
; 見つけたデータを返す
(define (vector-find p v)
(let loop ((n 0))
(cond ((= (vector-length v) n) #f)
((p (vector-ref v n)) (vector-ref v n))
(else
(loop (+ n 1))))))
; 見つけたデータの位置を返す
(define (vector-position p v)
(let loop ((n 0))
(cond ((= (vector-length v) n) #f)
((p (vector-ref v n)) n)
(else
(loop (+ n 1))))))
; 述語 p が真となる要素の個数を返す
(define (vector-count p v)
(let loop ((n 0) (a 0))
(cond ((= (vector-length v) n) a)
((p (vector-ref v n))
(loop (+ n 1) (+ a 1)))
(else
(loop (+ n 1) a)))))
関数 vector-find はベクタ v の中から述語 p が真を返す要素を探します。名前付き let でベクタの要素を先頭から順番に調べていきます。局所変数 n が添字を表します。n がベクタの大きさと等しくなったならば、要素をすべて調べたので探索は失敗です。#f を返します。述語 p が真を返したならば、その要素を返します。そうでなければ loop を再帰呼び出しします。
関数 vector-position は見つけた要素の位置を返します。これは述語 p の返り値が真の場合、添字 n の値をそのまま返すだけです。関数 vector-count は述語 p が真となる回数を求めます。回数は局所変数 a でカウントします。a は 0 に初期化し、述語 p が真を返す場合は a を +1 し、そうでなければ a はそのままで loop を再帰呼び出しします。
簡単な実行例を示しましょう。
gosh> (define a (vector 1 2 3 4 5 6 7)) a gosh> (vector-find odd? a) 1 gosh> (vector-find even? a) 2 gosh> (vector-position odd? a) 0 gosh> (vector-position even? a) 1 gosh> (vector-count odd? a) 4 gosh> (vector-count even? a) 3
このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、例題で取り上げる「二分探索」や他の高速な探索アルゴリズム [*1] を使ってみてください。
次はマップ関数を作りましょう。
リスト : ベクタ用マップ関数
(define (vector-map f v)
(let ((new-vec (make-vector (vector-length v))))
(let loop ((n 0))
(cond ((= n (vector-length v)) new-vec)
(else
(vector-set! new-vec n (f (vector-ref v n)))
(loop (+ n 1)))))))
; 破壊的操作
(define (vector-map! f v)
(let loop ((n 0))
(cond ((= (vector-length v) n) v)
(else
(vector-set! v n (f (vector-ref v n)))
(loop (+ n 1))))))
マップ関数も簡単です。最初に新しいベクタを make-vector で作成して局所変数 new-vec にセットします。あとは、ベクタ v の要素に関数 f を適用して、その返り値をベクタ new-vec にセットするだけです。また、vector-map! のように、引数のベクタ v を直接書き換えることも簡単にできます。この場合、引数のベクタは破壊されることに注意してください。
簡単な実行例を示しましょう。
gosh> (define a (vector 1 2 3 4 5)) a gosh> a #(1 2 3 4 5) gosh> (vector-map (lambda (x) (* x x)) a) #(1 4 9 16 25) gosh> a #(1 2 3 4 5) gosh> (vector-map! (lambda (x) (* x x)) a) #(1 4 9 16 25) gosh> a #(1 4 9 16 25)
次は畳み込みを行う関数を作ります。
リスト : 畳み込み
(define (vector-reduce f g v)
(let loop ((n 0) (g g))
(if (= n (vector-length v))
g
(loop (+ n 1) (f g (vector-ref v n))))))
(define (vector-reduce-right f g v)
(let loop ((n (- (vector-length v) 1)) (g g))
(if (< n 0)
g
(loop (- n 1) (f (vector-ref v n) g)))))
関数 vector-reduce はベクタの先頭から、関数 vector-reduce-right はベクタの最後尾から順番に要素を取り出して畳み込み処理を行います。ベクタは最後尾の要素にも簡単にアクセスできるので、vector-reduce-right も繰り返しで処理することができます。
それでは簡単な例を示しましょう。
gosh> (define a (vector 1 2 3 4 5)) a gosh> (vector-reduce + 0 a) 15 gosh> (vector-reduce-right + 0 a) 15 gosh> (vector-reduce list 0 a) (((((0 1) 2) 3) 4) 5) gosh> (vector-reduce-right list 6 a) (1 (2 (3 (4 (5 6)))))
ところで、Scheme (Lisp) の世界ではリストが主役なので、データをリストに格納しておく方が便利な場合があります。したがって、Scheme (Lisp) では配列を使う機会はあまり多くないのですが、だからといって、配列が役に立たないわけではありません。配列を上手に使いこなすためには、リストと配列の違い、とくにベクタとの違いをよく理解しておくことが重要です。ここで、 2 つのデータ型の長所と短所を比較してみましょう。
まず、リストの構造を思い出してください。
CAR CDR CAR CDR CAR CDR CAR CDR
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
10 20 30 40
図 : リスト (10 20 30 40) の構造
リストは複数のコンスセルを接続して構成されています。コンスセルはデータを格納する CAR と、次のコンスセルを示す CDR (クダー) からなっていましたね。このリストの先頭に、新しいデータを追加してみましょう。これは、cons を使うと簡単にできます。
gosh> (define a '(10 20 30 40)) a gosh> a (10 20 30 40) gosh> (set! a (cons 50 a)) (50 10 20 30 40)
逆に、先頭のデータを取り外すには cdr を使えばいいですね。
gosh> (set! a (cdr a)) (10 20 30 40) gosh> (set! a (cdr a)) (20 30 40)
このように、リストはコンスセルをつないでデータを追加したり、コンスセルを外すことでデータを削除することができます。つまり、コンスセルを操作することで、その長さを自由に変更することができるのです。
今度は、ベクタ #(10 20 30 40) の先頭に新しいデータを追加することを考えてみましょう。ところで、ベクタの大きさは make-vector で作成したときに指定しましたね。ベクタは一度大きさを決めると、それ以上大きさを増やすことはできません。これはＣ言語でも同じです。したがって、ベクタの大きさを増やすには、必要な大きさのベクタを新しく確保して、元のベクタからデータをコピーするしかありません。
添字 ０ １ ２ ３
┌─┬─┬─┬─┐
ベクタ│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-ref を使うと簡単です。
gosh> (define a '(60 50 40 30 20 10)) (60 50 40 30 20 10) gosh> (list-ref a 4) 20
ここで、list-ref の処理を考えてみます。リストは、コンスセルをつなげて構成されています。リストの先頭の要素はすぐに求めることができますが、4 番目の要素を求めるには、先頭から順番に CDR 部をたどっていき、目的のコンスセルに到達したところで、ようやく要素を求めることができるのです。プログラム上では、list-ref を使って簡単に処理できるように見えますが、Scheme 内部では懸命にコンスセルをたどる処理を行っているのです。
これに対して、ベクタは連続したメモリ領域に用意されたデータ構造です。データは、この領域に順番に並べられます。Scheme (Lisp) の場合、データを格納する領域の大きさは、データ型の種類にかかわらず一定です。したがって、4 番目のデータを格納している領域は、単純な計算で求めることができるのです。リストのように、先頭から順番にデータをたどる必要はありません。Ｃ言語の場合も、配列に同じデータ型が格納されるので、単純な計算で指定した要素にアクセスすることができます。
このように、リストではコンスセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかりますが、ベクタはどの要素でも一定の時間でアクセスすることができます。つまり、配列はランダムアクセスが得意なデータ構造なのです。これが配列の長所です。
次は、ベクタの応用例として「二分探索（バイナリサーチ：binary searching）」を例題として取り上げます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。これに対し二分探索は log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめ昇順に並べておく必要があります。この操作を「ソート (sort) 」といいます。二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
[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 回程度の比較で探索を完了することができます。
二分探索は要素をランダムアクセスすることになるので、リストには不向きのアルゴリズムです。そこで、ベクタからデータを二分探索するプログラムを作ってみましょう。二分探索は簡単にプログラムできます。次のリストを見てください。
リスト : 二分探索
; 比較関数
(define (num-cmp x y) (- x y))
; ベクタの二分探索
(define (vector-binary-search item vec cmp)
(let loop ((low 0)
(high (- (vector-length vec) 1)))
(if (> low high)
#f
(let* ((mid (quotient (+ low high) 2))
(r (cmp item (vector-ref vec mid))))
(cond ((zero? r) mid)
((> r 0)
(loop (+ mid 1) high))
(else
(loop low (- mid 1))))))))
関数 vector-binary-search はベクタ vec の中から item と等しい要素を二分探索し、見つけた場合はその位置を返します。見つからない場合は #f を返します。item と要素の比較は引数 cmp に渡された比較関数で行います。(cmp x y) は x < y ならば負の値を、x = y ならば 0 を、x > y ならば正の値を返すこととします。数値の場合は関数 num-cmp のように定義すると簡単です。
最初に、探索する区間を示す変数 low と high を初期化します。ベクタの大きさは関数 vector-length で取得し、最後の要素の位置を high にセットします。次に名前付き let の繰り返しで探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 mid にセットします。そして、関数 cmp で item と mid の位置の要素を比較して、その結果を変数 r にセットします。r が 0 の場合は探索成功です。見つけた位置 mid を返します。
r が 0 よりも大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、r が 0 よりも小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し #f を返します。
これでプログラムは完成です。簡単な実行例を示しましょう。
gosh> (define a (vector 11 22 33 44 55 66 77 88 99)) a gosh> (vector-binary-search 44 a num-cmp) 3 gosh> (vector-binary-search 40 a num-cmp) #f
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作のことです。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。たいていの Scheme 処理系にはリストやベクタをソートする関数が用意されています。もちろん Gauche にも関数 sort がありますが、私達でもプログラムすることができます。
今回は簡単な例題ということで、挿入ソート (insert sort) を取り上げます。挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。下図を見てください。
[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 を挿入
残りの要素も同様に行う
図 : 挿入ソート
最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
プログラムは次のようになります。
リスト : 挿入ソート
(define (insert-sort vec cmp)
(let ((i 1)
(size (vector-length vec)))
(while (< i size)
(let ((tmp (vector-ref vec i))
(j (- i 1)))
(while (and (>= j 0)
(< (cmp tmp (vector-ref vec j)) 0))
(vector-set! vec (+ j 1) (vector-ref vec j))
(set! j (- j 1)))
(vector-set! vec (+ j 1) tmp)
(set! i (+ i 1))))))
引数 vec はソートするベクタ、cmp は要素の比較関数で、二分探索と同じ仕様です。vector-length でベクタ vec の長さを求めて変数 size にセットします。このプログラムでは、繰り返しに名前付き let ではなく while を使っています。
最初の while ループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行っていて、このときデータの移動も同時に行っています。
それでは実行してみましょう。
gosh> (define a (vector 5 6 4 7 3 8 2 9 1)) a gosh> (insert-sort a num-cmp) #<undef> gosh> a #(1 2 3 4 5 6 7 8 9)
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。ソートアルゴリズムに興味のある方は拙作のページ Python with Algorithms ソート [1] [2] [3] をお読みください。
今回はここまでです。簡単に復習しておきましょう。
次回はリストの破壊的な操作を説明します。