今回は「ベクタ (vector)」というデータ構造について説明します。Clojure のベクタは 1 次元配列のことで、手続き型言語ではお馴染みのデータ構造です。Common Lisp は多次元配列を扱うことができますが、Clojure にはベクタしかありません。もっとも、ベクタがあれば多次元配列を実装するのは難しいことではありません。ただし、Clojure のベクタは immutable なデータ構造であることに注意してください。まず最初に、一般的な「配列 (array)」について簡単に説明します。
配列はリストと同様に複数個のデータを格納することができます。配列に格納されたデータを「要素」と呼びます。リストは複数のコンスセルを接続して構成しますが、配列はデータを格納する変数を連続したメモリ領域に用意します [*1]。配列はホテルやマンションの部屋にたとえるとわかりやすいと思います。
ホテル全体を配列とすると、各部屋がデータを格納する変数と考えることができます。ホテルでは、ルームナンバーによって部屋を指定しますね。配列の場合も、整数値によってデータを格納する変数を指定することができます。この整数値を「添字 (subscripts)」といいます。
添字 ０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
配列 │ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
図 : 配列の構造 (その１)
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
Ａ棟(０)│ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
Ｂ棟(１)│ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
Ｃ棟(２)│ │ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
図 : 配列の構造 (その２)
たとえば、10 個のデータを格納する配列を考えてみます。これは、平屋建てのマンションで、部屋が 10 室あると考えてください。この場合は上図に示すように、データを格納する変数が並んでいて、それぞれ 0 から 9 までの添字で指定することができます。
Lisp 言語の場合、添字は 0 から順番に数えるのが一般的です。ホテルのルームナンバーのように、4 や 9 は縁起が悪いから使わない、ということはありません。ほかのプログラミング言語、たとえばＣ言語は 0 から数えますが、PASCAL や Julia では 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 次元配列と考えることができます。
さて、話ばかりでは退屈なので、具体的にベクタの使い方を説明しましょう。ベクタは次の方法で作成します。
ベクタは角カッコ '[' と ']' で囲み、要素を空白で区切って表します。[ ] は要素が一つもない空ベクタになります。vector は引数 obj1, obj2, ... を要素とするベクタを作成して返します。関数 list のベクタ版です。関数 vec は引数のコレクションをベクタに変換して返します。なお、Lisp 言語のベクタは S 式であればどんなデータでも格納することができます。
簡単な例を示しましょう。
user=> (def a [1 2 3 4 5]) #'user/a user=> a [1 2 3 4 5] user=> (vector 'a 'b 'c 'd 'e) [a b c d e] user=> (vec '(a b c d e)) [a b c d e] user=> (vector? a) true user=> (vector? 1) false user=> (count a) 5
ベクタ [...] は read で読み込むことができる形式で、プログラムの中で指定することもできます。ベクタは数や文字列と同じく自己評価フォームです。データ型のチェックは型述語 vector? を使います。ベクタの大きさは関数 count で求めることができます。
ベクタの要素は関数 get で求めることができます。
get はベクタ vector の index 番目の要素を返します。Clojure のベクタは immutable なので、要素を破壊的に修正することはできません。ベクタはシーケンス (列) 型のデータなので、関数 first, second, nth などで要素を求めることもできます。index が範囲外の場合は nil を返します。
簡単な使用例を示しましょう。
user=> (def b [10 20 30 40 50]) #'user/b user=> b [10 20 30 40 50] user=> (get b 0) 10 user=> (get b 4) 50 user=> (get b 5) nil user=> (dotimes [n (count b)] (println (get b n))) 10 20 30 40 50 nil user=> (nth b 0) 10 user=> (first b) 10 user=> (second b) 20
関数 peek はベクタの末尾要素を求めます。引数がリストの場合は first と同じです。
user=> b [10 20 30 40 50] user=> (peek b) 50 user=> (peek '(a b c d e)) a
関数 conj はコレクションに新しい要素を追加します。
coll がベクタの場合、item はベクタの末尾に追加されます。coll がリストであれば、先頭に追加されます。
user=> b [10 20 30 40 50] user=> (def c (conj b 60)) #'user/c user=> c [10 20 30 40 50 60] user=> b [10 20 30 40 50] user=> (conj c 1 2 3 4 5) [10 20 30 40 50 60 1 2 3 4 5] user=> (def d '(a b c d e)) #'user/d user=> (conj d 1) (1 a b c d e) user=> (conj d 1 2 3 4 5) (5 4 3 2 1 a b c d e) user=> d (a b c d e)
元のベクタ b とリスト d はそのままです。conj は新しいコレクションを返すことに注意してください。
関数 pop はコレクションから要素を一つ削除します。
引数 coll がベクタの場合、末尾要素を削除した新しいベクタを返します。リストの場合は rest と同じ動作になります。
user=> b [10 20 30 40 50] user=> (pop b) [10 20 30 40] user=> b [10 20 30 40 50] user=> d (a b c d e) user=> (pop d) (b c d e) user=> d (a b c d e)
Clojure のベクタは immutable ですが、要素を更新した新しいベクタを生成することはできます。
関数 assoc は連想配列 (またはベクタ) の値を更新した新しい連想配列 (またはベクタ) を返します。連想配列はあとで説明します。ベクタの場合、key は更新する要素の添字で、val が新しい値になります。関数 update は key の値を val とすると、(func val args ...) の評価結果が新しい要素になります。
user=> (def a [1 2 3 4 5]) #'user/a user=> (assoc a 1 2.0) [1 2.0 3 4 5] user=> a [1 2 3 4 5] user=> (assoc a 1 2.0 4 5.0) [1 2.0 3 4 5.0] user=> a [1 2 3 4 5] user=> (update a 0 list 'a) [(1 a) 2 3 4 5] user=> (update a 0 list 'a 'b 'c) [(1 a b c) 2 3 4 5] user=> (update a 0 inc) [2 2 3 4 5] user=> (update a 0 + 10) [11 2 3 4 5]
関数 replace はベクタ keys の要素が連想配列のキー (またはベクタの添字) であれば、連想配列の値 (またはベクタの要素) に置き換えた新しいベクタを返します。
user=> a [1 2 3 4 5] user=> (replace a [0 2 4]) [1 3 5] user=> (replace a [0 'a 2 'b 4 'c]) [1 a 3 b 5 c]
連想配列のキー (またはベクタの添字) でなければ、値自身がベクタの要素になります。
ベクタの連結は関数 concat で、ベクタの反転は関数 rseq で、ベクタのコピーは関数 subvec で行うことができます。
subvec は start 番目の要素から end - 1 番目の要素をコピーします。end を省略すると最後までコピーします。
user=> (concat [1 2 3] [4 5 6]) (1 2 3 4 5 6) user=> (concat [1 2 3] [4 5 6] [7 8 9]) (1 2 3 4 5 6 7 8 9) user=> (rseq [1 2 3 4 5]) (5 4 3 2 1) user=> (subvec [1 2 3 4 5] 0) [1 2 3 4 5] user=> (subvec [1 2 3 4 5] 1 3) [2 3]
なお、今まで説明した高階関数 map, filter, remove, reduce などは、ベクタにも適用することができます。
user=> (map #(* % %) [1 2 3 4 5 6 7 8]) (1 4 9 16 25 36 49 64) user=> (filter even? [1 2 3 4 5 6 7 8]) (2 4 6 8) user=> (remove even? [1 2 3 4 5 6 7 8]) (1 3 5 7) user=> (reduce + 0 [1 2 3 4 5 6 7 8]) 36
map, filter, remove はシーケンス (列) を返しますが、ベクタを返す関数 mapv, filterv も用意されています。
user=> (mapv #(* % %) [1 2 3 4 5 6 7 8]) [1 4 9 16 25 36 49 64] user=> (mapv + [1 2 3 4] [5 6 7 8]) [6 8 10 12] user=> (filterv odd? [1 2 3 4 5 6 7 8]) [1 3 5 7] user=> (filterv even? [1 2 3 4 5 6 7 8]) [2 4 6 8]
それでは簡単な例題として、ベクタ用の高階関数を作ってみましょう。最初にベクタの中からデータを探索する関数を作ります。いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching)」といます。次のリストを見てください。
リスト : データの探索
;; 見つけたデータを返す
(defn vector-find [pred vs]
(loop [i 0]
(cond
(= (count vs) i) false
(pred (get vs i)) (get vs i)
:else (recur (inc i)))))
;; 見つけたデータの位置を返す
(defn vector-position [pred vs]
(loop [i 0]
(cond
(= (count vs) i) -1
(pred (get vs i)) i
:else (recur (inc i)))))
;; 述語 p が真となる要素の個数を返す
(defn vector-count [pred vs]
(loop [i 0 c 0]
(cond
(= (count vs) i) c
(pred (get vs i)) (recur (inc i) (inc c))
:else (recur (inc i) c))))
関数 vector-find はベクタ vs の中から述語 pred が真を返す要素を探します。loop / recur でベクタの要素を先頭から順番に調べていきます。局所変数 i が添字を表します。i がベクタの大きさになったならば false を返します。述語 pred が真を返したならば vs の要素を返します。そうでなければ、loop / recur で次の要素を調べます。
関数 vector-position は見つけた要素の位置 i を返すだけです。関数 vector-count は述語 pred が真となる回数を求めます。回数は局所変数 c でカウントします。c は 0 に初期化し、述語 pred が真を返す場合は c を +1 します。なお、Clojure には Java のメソッド indexOf, lastIndexOf を呼び出す関数 .indexOf, .lastIndexOf があります。
簡単な実行例を示しましょう。
user=> (def a [1 2 3 4 5 6 7]) #'user/a user=> (vector-find even? a) 2 user=> (vector-find odd? a) 1 user=> (vector-find neg? a) false user=> (vector-position even? a) 1 user=> (vector-position odd? a) 0 user=> (vector-position neg? a) -1 user=> (vector-count even? a) 3 user=> (vector-count odd? a) 4 user=> (vector-count neg? a) 0 user=> (.indexOf [1 2 3 4 1 2 3 4] 4) 3 user=> (.lastIndexOf [1 2 3 4 1 2 3 4] 4) 7 user=> (.indexOf [1 2 3 4 1 2 3 4] 5) -1 user=> (.lastIndexOf [1 2 3 4 1 2 3 4] 5) -1
このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、例題で取り上げる「二分探索」や他の高速な探索アルゴリズム [*2] を使ってみてください。
次は畳み込みを行う関数を作ります。
リスト : 畳み込み
(defn vector-foldl [f a vs]
(loop [i 0 a a]
(if (= (count vs) i)
a
(recur (inc i) (f a (get vs i))))))
(defn vector-foldr [f a vs]
(loop [i (dec (count vs)) a a]
(if (neg? i)
a
(recur (dec i) (f (get vs i) a)))))
関数 vector-foldl はベクタの先頭から、関数 vector-foldr はベクタの最後尾から順番に要素を取り出して畳み込み処理を行います。ベクタは最後尾の要素にも簡単にアクセスできるので、vector-foldr も繰り返しで処理することができます。
それでは簡単な例を示しましょう。
user=> a [1 2 3 4 5 6 7] user=> (vector-foldl + 0 a) 28 user=> (vector-foldr + 0 a) 28 user=> (vector-foldl list 0 a) (((((((0 1) 2) 3) 4) 5) 6) 7) user=> (vector-foldr list 8 a) (1 (2 (3 (4 (5 (6 (7 8)))))))
次は、ベクタの応用例として「二分探索 (バイナリサーチ：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 回程度の比較で探索を完了することができます。
二分探索は要素をランダムアクセスすることになるので、リストには不向きのアルゴリズムです。そこで、ベクタからデータを二分探索するプログラムを作ってみましょう。二分探索は簡単にプログラムできます。次のリストを見てください。
リスト : 二分探索
(defn binary-search [item vs]
(loop [low 0
high (dec (count vs))]
(if (> low high)
false
(let [mid (quot (+ low high) 2)
r (compare item (get vs mid))]
(cond
(zero? r) mid
(pos? r) (recur (inc mid) high)
:else (recur low (dec mid)))))))
関数 binary-search はベクタ vs の中から item と等しい要素を二分探索し、見つけた場合はその位置を返します。見つからない場合は false を返します。item と要素の比較はプリミティブな関数 compare で行います。(compare x y) は x < y ならば負の値を、x == y ならば 0 を、x > y ならば正の値を返します。
最初に、探索する区間を示す変数 low と high を初期化します。ベクタの大きさは関数 count で取得し、最後の要素の位置を high にセットします。次に loop / recur の繰り返しで探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 mid にセットします。そして、関数 compare で item と mid の位置の要素を比較して、その結果を変数 r にセットします。r が 0 の場合は探索成功です。見つけた位置 mid を返します。
r が正の場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、r が負の場合は前半を調べるため、変数 high に mid - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し false を返します。
これでプログラムは完成です。簡単な実行例を示しましょう。
user=> (def v (vector 11 22 33 44 55 66 77 88 99)) #'user/v user=> (binary-search 44 v) 3 user=> (binary-search 40 v) false
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作のことです。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。たいていの Lisp 処理系にはリストやベクタをソートする関数が用意されています。もちろん Clojure にも関数 sort があります。
sort は引数 coll をソートします。デフォルトの比較関数は compare です。sort-by は引数 coll の要素に keyfunc を適用し、その結果を使ってソートします。どちらの関数も比較関数 comp を渡すことができます。
簡単な実行例を示しましょう。
user=> (sort [5 6 4 7 3 8 2 9 1 0]) (0 1 2 3 4 5 6 7 8 9) user=> (sort '(9 8 7 6 5 4 3 2 1 0)) (0 1 2 3 4 5 6 7 8 9) user=> (sort > [5 6 4 7 3 8 2 9 1 0]) (9 8 7 6 5 4 3 2 1 0) user=> (sort > '(0 1 2 3 4 5 6 7 8 9)) (9 8 7 6 5 4 3 2 1 0) user=> (sort-by first [[5 6] [4 7] [3 8] [2 9] [1 0]]) ([1 0] [2 9] [3 8] [4 7] [5 6]) user=> (sort-by second [[5 6] [4 7] [3 8] [2 9] [1 0]]) ([1 0] [5 6] [4 7] [3 8] [2 9]) user=> (sort-by first > [[5 6] [4 7] [3 8] [2 9] [1 0]]) ([5 6] [4 7] [3 8] [2 9] [1 0]) user=> (sort-by second > [[5 6] [4 7] [3 8] [2 9] [1 0]]) ([2 9] [3 8] [4 7] [5 6] [1 0])
Clojure の「分配束縛 (Destructuring) は、シーケンス (リストやベクタなど) または連想配列 (Map) からデータを取り出して別々の変数に代入するための構文です。シーケンスの分配束縛は、変数を格納したベクタ (変数リスト) と値を格納したシーケンス (値リスト) を照合し、変数リストの変数と同じ位置にある値リストの値でその変数を初期化します。変数を定義するところ、たとえば defn の仮引数とか let で局所変数を定義するとき、分配束縛を使用することができます。
簡単な例を示しましょう。
user=> (let [[a b c] [1 2 3]] (list a b c)) (1 2 3) user=> (let [[a b c] '(1 2 3)] (list a b c)) (1 2 3) user=> (let [[a b c] [1 2]] (list a b c)) (1 2 nil) user=> (let [[a b c] [1 2 3 4]] (list a b c)) (1 2 3) user=> (let [[a b c] []] (list a b c)) (nil nil nil) user=> (let [[a b c] '()] (list a b c)) (nil nil nil)
変数が余る場合、その変数の値は nil に初期化されます。値が余る場合、余った値は無視されます。値リストが空の場合、全ての変数は nil になります。エラーにはならないので注意してください。
変数リストと値リストは入れ子であってもかまいません。簡単な例を示します。
user=> (let [[[a b] [c d]] [[1 2] [3 4]]] (list a b c d)) (1 2 3 4) user=> (let [[[a b] c] [[1 2] [3 4]]] (list a b c)) (1 2 [3 4]) user=> (let [[a [b c]] [[1 2] [3 4]]] (list a b c)) ([1 2] 3 4) user=> (let [[a b [c d]] [1 2 3 4]] (list a b c d)) エラー user=> (let [[a b [c d]] []] (list a b c d)) (nil nil nil nil) user=> (let [[a b [c d]] '()] (list a b c d)) (nil nil nil nil)
変数リストと値リストの構造が合わないとエラーになりますが、空リスト (空ベクタ) の場合はエラーにならず、全ての変数が nil になります。
分配束縛は可変個引数のように & を使うことができます。
user=> (let [[a b c & d] [1 2 3 4 5]] (list a b c d)) (1 2 3 (4 5)) user=> (let [[a b c & d] [1 2 3 4]] (list a b c d)) (1 2 3 (4)) user=> (let [[a b c & d] [1 2 3]] (list a b c d)) (1 2 3 nil)
:as を使うと、値リスト全体を取得することができます。
user=> (let [[a b c :as d] [1 2 3]] (list a b c d)) (1 2 3 [1 2 3]) user=> (let [[a b c :as d] '(1 2 3)] (list a b c d)) (1 2 3 (1 2 3))
分配束縛を使うと、簡単にリストを分解することができます。
user=> (defn foo [[x & xs]] (list x xs)) #'user/foo user=> (foo '(1 2 3)) (1 (2 3)) user=> (foo '(1 2)) (1 (2)) user=> (foo '(1)) (1 nil) user=> (foo '()) (nil nil) user=> (foo '(nil)) (nil nil)
[x & xs] は空リストにもマッチングします。最後の例のように、リストに nil が含まれていると、x が nil だからといって、引数が空リストと判定することはできません。ご注意くださいませ。
ご参考までに、リスト操作関数を分配束縛を使って書き直してみましょう。
リスト : リスト操作関数
;; リストの連結
(defn append [[x & xs :as ls] ys]
(if-not (seq ls)
ys
(cons x (append xs ys))))
;; リストの反転
;; loop は分配束縛を使えないようだ
(defn my-reverse
([xs] (my-reverse xs '()))
([[y & ys :as ls] a]
(if-not (seq ls)
a
(recur ys (cons y a)))))
;; マッピング
(defn mapcar [func [x & xs :as ls]]
(if-not (seq ls)
'()
(cons (func x) (mapcar func xs))))
;; フィルター
(defn remove-if [pred [x & xs :as ls]]
(cond
(not (seq ls)) '()
(pred x) (remove-if pred xs)
:elses (cons x (remove-if pred xs))))
;; 畳み込み
(defn foldl [func a [x & xs :as ls]]
(if-not (seq ls)
a
(recur func (func a x) xs)))
(defn foldr [func a [x & xs :as ls]]
(if-not (seq ls)
a
(func x (foldr func a xs))))
ベクタは doseq や for を使って要素を順番に取り出すことができます。
user=> (doseq [x [1 2 3 4 5]] (println x)) 1 2 3 4 5 nil user=> (for [x [1 2 3 4 5]] (* x x)) (1 4 9 16 25) user=> (doseq [x [1 2 3] y [4 5 6]] (println x y)) 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 nil user=> (for [x [1 2 3] y [4 5 6]] [x y]) ([1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6])
doseq と for は分配束縛を使うことができます。
user=> (def xs (for [x [1 2 3] y [4 5 6]] [x y])) #'user/xs user=> xs ([1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]) user=> (doseq [[x y] xs] (println x y)) 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 nil user=> (for [[x y] xs] (* x y)) (4 5 6 8 10 12 12 15 18)
最後に簡単な例題として、組み合わせの数 \({}_n \mathrm{C}_r\) を求めるプログラムを作ってみましょう。\({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。(1) と (2) の公式を使うと簡単に (高速に) 答えを求めることができます。ただし、(3) の公式をそのままプログラムすると二重再帰になるので、大きな値を求めると時間がかかってしまいます。実際にプログラムを作って確かめてみましょう。
リスト : 組み合わせの数 (1)
(defn combination [n r]
(if (or (zero? r) (== n r))
1
(+ (combination (dec n) r) (combination (dec n) (dec r)))))
user=> (time (combination 28 14)) "Elapsed time: 443.9282 msecs" 40116600 user=> (time (combination 30 15)) "Elapsed time: 1780.54389 msecs" 155117520 user=> (time (combination 32 16)) "Elapsed time: 6646.08361 msecs" 601080390
このように、公式 (3) を使うと時間がかかります。公式 (1), (2) を使えば高速に答えを求めることができますが、今回はベクタの例題として、あえてこのプログラムの高速化に挑戦してみましょう。
公式からわかるように、\({}_n \mathrm{C}_r\) の値は \({}_{n-1} \mathrm{C}_r\) と \({}_{n-1} \mathrm{C}_{r-1}\) を足したものです。n = 0 から順番に組み合わせの数を求めて表 (ベクタ) に格納しておけば、n が大きな値でも簡単に求めることができるはずです。プログラムは次のようになります。
リスト : 組み合わせの数 (2)
;; 大域変数
(def pascal-table)
;; パスカルの三角形を作る
(defn pascal [n]
(loop [i 0 a [[1]]]
(if (> i n)
a
(let [xs (conj (peek a) 0)
ys (reverse xs)]
(recur (inc i) (conj a (mapv + xs ys)))))))
(defn combination [n r]
(when-not (bound? #'pascal-table)
(def pascal-table (pascal 65))) ; Long ではこれが限界
(get (get pascal-table n) r))
関数 pascal は累積変数 a に「パスカルの三角形」を作ります。次の図を見てください。
[1 2 1] の次を求める [1 2 1 0] ; 末尾に 0 を加える + [0 1 2 1] ; それを反転する ------------ [1 3 3 1] ; 足し算する [1 3 3 1] の次を求める [1 3 3 1 0] + [0 1 3 3 1] -------------- [1 4 6 4 1] これを繰り返すと「パスカル」の三角形ができる
簡単に言うと、末尾に 0 を加えたベクタと先頭に 0 を加えたベクタを足し算すればいいわけです。関数 pascal はこれをそのままプログラムしただけです。作成した表は大域変数 pascal-table にセットします。
関数 combination では、pascal-table に表がセットされているかチェックします。関数 bound? は Var Object に値が束縛されていれば真を返します。そうでなければ、pascal を呼び出して表をセットします。最後に、pascal-table から値を求めて返すだけです。
それでは実際に試してみましょう。
user=> (doseq [x (pascal 10)] (println x)) [1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1] [1 5 10 10 5 1] [1 6 15 20 15 6 1] [1 7 21 35 35 21 7 1] [1 8 28 56 70 56 28 8 1] [1 9 36 84 126 126 84 36 9 1] [1 10 45 120 210 252 210 120 45 10 1] [1 11 55 165 330 462 462 330 165 55 11 1] nil user=> (time (combination 32 16)) "Elapsed time: 12.545491 msecs" 601080390 user=> (time (combination 60 30)) "Elapsed time: 0.08 msecs" 118264581564861424 user=> (time (combination 64 32)) "Elapsed time: 0.0702 msecs" 1832624140942590534
最初に combination を呼び出すとき、65 段のパスカルの三角形を生成しますが、とても高速に実行することができます。あとは表を引くだけなので、実行時間は極めて高速です。
今回はここまでです。簡単に復習しておきましょう。