Ｃ言語や Pascal が「手続き型言語」と呼ばれるのに対し、Lisp は「関数型言語」と呼ばれています。関数型言語は、データに関数を適用していくことでプログラムを実行します。たとえば、数学の関数を考えてください。
f(x, y) = 2x + 3y
関数 f(x, y) は引数 x と y を与えると値を返します。そして、同じ値の引数を与えれば、結果はいつも同じ値になります。関数型言語の基本的な考え方は、このような数学の関数と同じです。
ところが、Lisp は完全な関数型言語ではありません。引数以外の変数を定義して、setq などで値を代入することができるからです。つまり、変数の値を書き換えることでプログラムを実行する「手続き型言語」の機能もあるわけです。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
それから、関数型言語の場合、関数はほかのデータと同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができるのです。また、値として関数を返すこともできるので、関数を作る関数を定義することができます。
関数を引数として受け取る関数を「汎関数 (functional) 」と呼ぶことがあります。ここでは、汎関数とラムダ式について説明します。
Common Lisp の場合、単純な繰り返しは dotimes, dolist, while, loop などを使って簡単にプログラムできます。もっと複雑な処理ならば、再帰定義でプログラムを作成することができます。このほかに、Common Lisp にはマップ関数 (mapping function) という便利な関数が用意されています。
簡単な例題として、リストの要素どうしを足し算して、その結果をリストに格納する関数を作ってみましょう。次の例を見てください。
( 1 2 3 4 5)
+ (10 20 30 40 50)
---------------------
(11 22 33 44 55)
これを再帰定義でプログラミングすると、次のようになるでしょう。
| List 1 : リストの要素を足し算する |
|---|
(defun add-element (x y)
(if (and (consp x) (consp y))
(cons (+ (car x) (car y))
(add-element (cdr x) (cdr y)))))
|
関数名は add-element としました。実は、この処理はマップ関数 mapcar だけで実現できるのです。まずは、実行例を見てください。
(add-element '(1 2 3 4 5) '(10 20 30 40 50))
=> (11 22 33 44 55)
(mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))
=> (11 22 33 44 55)
mapcar の引数に見慣れぬ記号 #' がありますね。#'+ は (function +) の省略形です。function は特殊形式で、シンボルに格納されている関数を取り出す働きをします。#'+ であれば、シンボル + から加算を行う処理を取り出します。つまり、mapcar にはシンボル + に格納されている値ではなく、「関数」を渡しているのです。実際に function を実行してみましょう。
(function +) => #<function: +>
このように、関数を引数として渡すことができるのが Lisp の特徴のひとつです。mapcar は、渡された関数をリストの各要素に適用して、その結果をリストに格納して返します。もし、各要素に対して乗算 * を実行したい場合は、#'* を mapcar に渡せばいいのです。
(mapcar #'* '(1 2 3 4 5) '(10 20 30 40 50))
=> (10 40 90 160 250)
もちろん、私達が定義した関数も渡すことができます。もし、リストの要素を 2 乗したい場合は、数を 2 乗する関数 square を定義して、それを mapcar に渡せばいいのです。
(defun square (x) (* x x))
=> square
(mapcar #'square '(1 3 4 5 7))
=> (1 9 16 25 49)
このように、マップ関数を使ってデータを簡単に変換することができますが、それだけではなく、リストからデータを取り出すことも簡単にできます。
(mapcar #'car '((a . 1) (b . 2) (c . 3)))
=> (a b c)
(mapcar #'cdr '((a . 1) (b . 2) (c . 3)))
=> (1 2 3)
それから、指定した関数に必要な引数を用意しないと、当然のことですがエラーになります。引数のリストの長さが異なる場合は、短いリストの要素がなくなった時点で処理を終了します。次の例を見てください。
(mapcar #'cons '(a b c d) '(1 2 3 4 5))
=> ((a . 1) (b . 2) (c . 3) (d . 4))
mapcar のように、関数を引数として受け取る関数を汎関数 (functional) と呼ぶことがあります。Lisp の世界では、汎関数は特別なものではありません。Lisp には便利な汎関数がいろいろと用意されていますし、私達ユーザーが定義することもできるのです。そのためには、重要な 2 つの汎関数 funcall と apply が必要になります。
まず apply から説明しましょう。
(apply function args-list)
apply は、最初の引数 func を第 2 引数に適用して、その結果を返します。第 2 引数はリストでなければいけません。簡単な使用例を示しましょう。
(apply #'+ '(1 2 3)) => 6
(+ 1 2 3) => 6
(apply #'car '(1 2 3)) => 1
(apply #'car '((1 2 3))) => 1 2002/1/21:修正
(car '(1 2 3)) => 1
また、apply は次のように func と args-list の間に引数を与えることができます。
(apply #'+ 4 5 6 '(1 2 3)) => 21
apply は、リストに格納されている要素を、引数として関数に渡す場合に便利です。たとえば、リストに格納された文字列の文字数の合計を求める処理を考えてみましょう。mapcar に関数 length を渡せば、各要素の文字数を数えることができます。
(mapcar #'length '("abc" "defg" "hijkl" "mnopqr")) => (3 4 5 6)
あとは各要素を足し算するだけですが、リストのままでは関数 + を使うことができません。この場合は apply を使うといいのです。
(apply #'+ (mapcar #'length '("abc" "defg" "hijkl" "mnopqr"))) => 18
dolist のような繰り返し関数を使うと、次のようになるでしょう。
| List 2 : 文字数の合計を求める |
|---|
(let ((total 0))
(dolist (x '("abc" "defg" "hijkl" "mnopqr") total)
(setq total (+ total (length x)))))
|
dolist を使うとレキシカル変数 total が必要になるので、プログラムが少しだけ複雑になります。
次は funcall を説明しましょう。
(funcall func args ... )
funcall は最初の引数 func を残りの引数 args に適用し、その結果を返します。簡単な使用例を示しましょう。
(funcall #'+ 1 2 3) => 6
(+ 1 2 3) => 6
(funcall #'car '(a b c)) => a
(car '(a b c)) => a
さて、これだけでは funcall が何の役に立つのかわかりませんね。ところが funcall を使うことで、関数を引数として扱う汎関数を定義することができるのです。次の例を見てください。
| List 3 : 汎関数の定義（誤例） |
|---|
(defun execfunc (func arg1 arg2) (func arg1 arg2)) |
関数 execfunc は第 1 引数に処理を行う関数を受け取り、残りの引数をその関数に適用します。上記のリストを実際に試してみると、「関数が定義されていません」というエラーが表示されます。
(execfunc #'+ 1 2) => エラー
シンボルは変数の値と関数を別々に格納しています。この場合、シンボル func に定義されている関数を実行しようとします。ところが、シンボル func には関数が定義されていないのでエラーとなるのです。ここで実行しようとする関数は変数 func に値として格納されているので、リストの先頭に func を書いてはいけません。変数 func に格納された関数を実行する場合は funcall を使います。
| List 4 : 汎関数の定義（正解） |
|---|
(defun execfunc (func arg1 arg2) (funcall func arg1 arg2)) |
これで、変数 func に格納されている値（関数）が取り出され、それが funcall に渡されるので正常に動作します。
(execfunc #'+ 1 2) => 3
Lisp はリストの先頭要素がシンボルの場合、それを関数として呼び出しました。実は、もうひとつ関数として呼び出す形式があります。それは、リストの先頭要素がリストで、そのリストの先頭要素が lambda というシンボルの場合です。言葉で説明すると難しいので、さっそく例をみてください。
((lambda (x) (* x x)) 2) => 4 ~~~~~~~~~~~~~~~~~~~~
下線で示した部分がリストの先頭要素です。リストになっていますね。このリストの先頭要素が lambda になっています。このように、先頭要素が lambda のリストをラムダ式 (lambda expression) といいます。ラムダはギリシャ文字λのことです。ラムダ式の構造は関数を定義する defun とよく似ています。次の図を見てください。
| 図 1 : ラムダ式の構文 |
|---|
(lambda (defun <関数名>
(<仮引数名> ... ) (<仮引数名> ... )
処理１ 処理１
処理２ 処理２
・・・ ・・・
処理Ｍ) 処理Ｍ)
(1) ラムダ式 (2) defun による関数定義
|
defun と関数名の代わりに lambda を書けば、あとは defun とまったく同じです。実は、defun で定義する関数の実体が、このラムダ式なのです。
Lisp はリストの先頭要素がラムダ式の場合、それを関数として実行します。残りの要素はラムダ式に与える実引数となります。この場合、2 がラムダ式の仮引数 x に代入され、S 式 (* x x) が評価されて 4 という結果になります。このように、ラムダ式を使えば名前の無い関数を定義することができます。
ところで、汎関数を使うようになると、数を 2 乗する square のような小さな関数を、いちいち定義するのが面倒になります。汎関数に与える関数はラムダ式でも有効です。たとえば、リストの要素を 2 乗する処理は、次のようにラムダ式を使って実現できます。
(mapcar #'(lambda (x) (* x x)) '(1 2 3 4 5)) => (1 4 9 16 25)
わざわざ関数 square を定義しなくてもいいので簡単ですね。このように、汎関数でラムダ式を使うのはとても便利で、なおかつ、その場で実行される処理内容が確認できるという利点があります。
しかし、同じラムダ式があちこちに現れるようでは問題があります。プログラムに変更はつきものです。もし、その処理を変更しようとした場合、該当するラムダ式をすべて修正しなくてはなりません。これではラムダ式を使う意味がありませんね。このような場合、defun で関数を定義した方がよいでしょう。そうすると、その関数を修正するだけで済みます。
ソートはある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。Lisp はリストにデータを格納するので、リストの要素をソートする関数があると便利です。Common Lisp には関数 sort が用意されていますが、私達でも簡単にソートプログラムを作ることができます。最初に、簡単な「挿入ソート」を作ってみましょう。
挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト (2 4 6) に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
ソートするリストは、cdr で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。データを比較する関数は引数として渡せばいいでしょう。プログラムは次のようになります。
| List 5 : 挿入ソート |
|---|
; データをひとつリストに挿入
(defun insert-element (f n l)
(cond ((atom l) (cons n nil))
((funcall f n (car l)) (cons n l))
(t (cons (car l) (insert-element f n (cdr l))))))
; 挿入ソート
(defun insert-sort (f l)
(if (atom l)
nil
(insert-element f (car l) (insert-sort f (cdr l)))))
|
リストにデータをひとつ挿入する関数が insert-element です。再帰呼び出しでリストをたどり、データ n を挿入する位置を探します。比較関数 f の返り値が真であれば、その位置にデータを挿入します。関数 insert-sort は引数のリストを再帰呼び出しで分解します。空リストになると再帰呼び出しが停止します。そして、car で取り出した要素を insert-element でソート済みのリストに挿入します。
ところで、insert-sort は再帰定義を使いましたが、繰り返しでも簡単にプログラムできます。興味のある方は、dolist などの繰り返しを使って書き換えてみてください。
それでは実行してみましょう。
(insert-sort #'< '(9 5 3 7 6 4 8))
=> (3 4 5 6 7 8 9)
(insert-sort #'> '(9 5 3 7 6 4 8))
=> (9 8 7 6 5 4 3)
要素がリストの場合でも、ラムダ式を使うと簡単にソートできます。
(insert-sort #'(lambda (x y) (< (first x) (first y)))
'((9 1) (5 5) (3 7) (6 4) (2 8)))
=> ((2 8) (3 7) (5 5) (6 4) (9 1))
先頭の要素を基準にソートしています。first を second に変更すれば、第 2 要素を基準にソートすることができます。
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を n とすると、実行時間は n の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート」は高速なソートアルゴリズムとして有名です。もちろん、Lisp でもクイックソートをプログラムすることができます。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを枢軸といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の箇所を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
| 図 2 : クイックソート |
|---|
5 3 7 6 9 8 1 2 4
5 を枢軸に分割
(3 1 2 4) 5 (7 6 9 8)
3を枢軸に分割 7を枢軸に分割
(1 2) 3 (4) | 5 | (6) 7 (9 8)
・・・分割を繰り返していく・・・
|
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを append で結合すればいいわけです。プログラムは次のようになります。
| List 6 : クイックソート |
|---|
(defun quick-sort (f l)
(unless (atom l)
(let ((p (car l)) l1 l2)
(dolist (n (cdr l))
(if (funcall f n p) (push n l1) (push n l2)))
(append (quick-sort f l1) (cons p (quick-sort f l2))))))
|
変数 p が枢軸を表します。dolist でリストから要素を取り出し、関数 f で枢軸と比較します。f の返り値が真であれば、要素 n を l1 のリストに格納し、そうでなければ l2 のリストに格納します。これで枢軸を基準にデータを 2 つのリストに分けることができました。あとは、quick-sort を再帰呼び出しして、その結果を append で結合します。
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するまで劣化します。つまり、挿入ソートと同じくらい遅くなってしまうのです。この欠点については「ソート（その２）」で説明します。
配列 (array) はプログラミングを経験したことがある人ならばお馴染みのデータ構造でしょう。Common Lisp の配列は S 式であればどんなデータでも格納することができます。
配列は関数 make-array を使って生成します。
make-array dimensions
引数 dimensions は非負の整数を要素とするリストを与えます。そのリストの長さが配列の次元を表し、各要素がその次元のサイズを表します。次の図を見てください。
| 図 3 : 配列の生成 |
|---|
(setq table1 (make-array 5)) => #(nil nil nil nil nil)
|
+-- 第 1 次元( 0 - 4 )
+--- 第 1 次元( 0 - 1 )
| +- 第 2 次元( 0 - 2 )
| |
(setq table2 (make-array '(2 3))
=> #2A((nil nil nil) (nil nil nil))
(setq table3 (make-array '(2 3 4))
|
+- 第 3 次元( 0 - 3 )
=> #3A(((nil nil nil nil) (nil nil nil nil) (nil nil nil nil))
((nil nil nil nil) (nil nil nil nil) (nil nil nil nil)))
|
配列型データは数値や文字列と同じく自己評価フォームです。# の次の数字が次元を表し、A が配列であることを表します。とくに、1 次元の配列をベクタ (vector) といいます。ベクタを生成する場合、引数はリストではなく整数値を与えてもかまいません。ベクタは #( ... ) で表示されます。
Lisp の場合、配列をリストのように表示しているので、ちょっとわかりにくいかもしれません。リストの階層構造と配列の次元を比較してください。
| 図 4 : 配列の表記法 |
|---|
┌──────→ ０ １
│ ------------ -----------
(make-array '( 2 3 )) => #2A((nil nil nil) (nil nil nil) )
│ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^
└────→ 0 1 2 0 1 2
(make-array '(2 3 4))
=> #3A(┌─[０]─────────────────────────┐
│ ０ １ ２ │
│ ---------------- ---------------- ---------------- │
│((nil nil nil nil) (nil nil nil nil) (nil nil nil nil)) │
│ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ │
│ 0 1 2 3 0 1 2 3 0 1 2 3 │
└────────────────────────────┘
┌─[１]─────────────────────────┐
│((nil nil nil nil) (nil nil nil nil) (nil nil nil nil)) │
└────────────────────────────┘
)
|
上図に示すように、第 1 次元はリストのトップレベルに対応し、第 2 次元は格納されているリストに対応します。つまり、次元の数だけリストが入れ子になっているのです。dimensions を (2 3 4) とした場合は、最初のリストが 2 つのリストを格納し、そのリストが 3 つのリストを格納し、さらにそのリストが 4 つの要素を格納していることに対応します。
make-array が生成した配列は nil で初期化されますが、この値を変更したい場合はキーワード (keyword) を使います。次の例を見てください。
(setq c (make-array 5 :initial-element 0))
=> #(0 0 0 0 0)
(setq d (make-array 5 :initial-contents '(1 2 3 4 5)))
=> #(1 2 3 4 5)
コロン ( : ) から始まる引数がありますね。Common Lisp では、これをキーワードといいます。キーワードの次がキーワード引数です。キーワードを指定することで、関数の動作を変更することができます。指定できるキーワードは関数によって異なります。
初期値を nil 以外の値に変更するには、キーワード :initial-element で指定します。各要素に異なった初期値を設定するには、キーワード :initial-contents で初期値をリストで与えます。
配列からデータを取り出すには関数 aref を使います。
(aref array subscripts ...)
subscripts (添字) の個数は配列 array の次元と等しくて、それぞれの添字は次元の範囲内に収まっていなければいけません。簡単な例を示しましょう。
(setq x (make-array 3 :initial-contents '(10 20 30)))
=> #(10 20 30)
(aref x 0)
=> 10
(aref x 2)
=> 30
(setq x (make-array '(2 3) :initial-contents '((10 20 30) (40 50 60))))
=> #2A((10 20 30) (40 50 60))
(aref x 0 0)
=> 10
(aref x 1 2)
=> 60
Lisp の配列はＣ言語と同じく、添字は 0 から順番に数えます。2 次元配列の場合、(aref x 0 0) では最初の 0 で (10 20 30) を指定し、次の 0 で要素 10 を指定します。(aref 1 2) では最初の 1 で (40 50 60) を指定して、次の 2 で要素 60 を指定します。
配列に値を代入する場合、処理系によっては配列専用の関数が用意されていますが、Common Lisp では setf を使います。setf は変数に値を代入するだけではなく、配列にも値を代入することができるのです。Common Lisp では、データの代入は setf で統一することを推薦しています。setf の構文を示します。
(setf アクセス関数 データ)
アクセス関数は評価したときにデータを取り出す関数のことです。配列の場合、aref がアクセス関数になります。変数は評価するとその値を返すので、アクセス関数とみなすことができます。setf はアクセス関数が示す位置へデータを代入します。簡単な例を示しましょう。
(setq a (make-array 3)) => #(nil nil nil) (setf (aref a 1) 10) => 10 a => #(nil 10 nil) (setq a (make-array '(2 3))) => #2A((nil nil nil) (nil nil nil)) (setf (aref a 1 2) 10) => 10 a => #2A((nil nil nil) (nil nil 10))
seft による代入は配列を直接書き換えること、つまり破壊的であることに注意してください。
Lisp にはリストがあるので、配列を使う機会はほかの言語よりもずっと少ないのですが、アルゴリズムによっては配列を使った方が便利な場合があります。そこで、配列 (表) を使った応用例として表計算法という手法を紹介します。例題として、フィボナッチ数列を求める関数を作ってみましょう。フィボナッチ関数は次のように定義されます。
| 図 5 : フィボナッチ関数の定義 |
|---|
┌ 1 n = 0
f(n) = ─┤ 1 n = 1
└ f(n-1) + f(n-2) n > 1
1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列
|
フィボナッチ関数は、階乗と同じく再帰を使えば簡単にプログラムできます。
| List 7 : フィボナッチ関数（再帰版） |
|---|
(defun fibo (x)
(if (or (= 0 x) (= 1 x))
1
(+ (fibo (- x 1)) (fibo (- x 2)))))
|
関数 fibo は fact と違い、自分自身を 2 回呼び出しています。このことを二重再帰といいます。fibo の呼び出しをトレースすると次のようになります。
| 図 6 : フィボナッチ関数のトレース |
|---|
f(5)─┬─f(4)─┬─f(3)─┬─f(2)─┬─f(1)
│ │ │ │
│ │ │ └─f(0)
│ │ └─f(1)
│ │
│ └─f(2)─┬─f(1)
│ │
│ └─f(0)
│
└─f(3)─┬─f(2)─┬─f(1)
│ │
│ └─f(0)
└─f(1)
|
図を見てもらえばおわかりのように、同じ値を何回も求めているため効率はとても悪いのです。この処理は、表を使うと高速化することができます。
同じ値を何度も計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めるようにします。この処理は、引数 x と配列 (ベクタ) の添字を対応させることで実現できます。つまり、ベクタの x 番目には、(fibo x) の結果を格納しておくわけです。ただし、この方法では引数 x の範囲がベクタのサイズに限定されるという欠点があることに注意してください。これをプログラムすると次のようになります。
| List 8 : フィボナッチ関数（ベクタ版その１） |
|---|
; グローバル変数の定義
(setq *fibo-table-limit* 100
*fibo-table* (make-array (1+ *fibo-table-limit*)))
; フィボナッチ関数本体
(defun fibo1 (n)
(if (<= 0 n 1)
1
(if (aref *fibo-table* n)
(aref *fibo-table* n)
(setf (aref *fibo-table* n)
(+ (fibo1 (1- n)) (fibo1 (- n 2)))))))
; フィボナッチ関数
(defun fibo (n)
(if (<= 0 n *fibo-table-limit*)
(fibo1 n)))
|
最初にベクタをグローバル変数にセットします。ベクタの大きさは *fibo-table-limit* で定義します。関数 fibo は範囲チェックだけを行い、実際の計算は fibo1 で行います。fibo1 は配列 *fibo-table* をチェックし、値があればそれを返します。そうでなければ再帰呼び出しで計算し、その結果を配列に格納します。これで高速にフィボナッチ数列を計算することができます。
この方法でも高速化することはできますが、データの総数が高々 100 個程度であれば、あらかじめ 0 から 100 までの値を計算してベクタに格納しておけば、もっと簡単にフィボナッチ数列を求めることができます。次のリストを見てください。
| List 9 : フィボナッチ関数（ベクタ版その２） |
|---|
; グローバル変数の定義
(setq *fibo-table-limit* 100
*fibo-table* (make-array (1+ *fibo-table-limit*)))
; ベクタの初期化
(defun init-fibo-table ()
(setf (aref *fibo-table* 0) 1
(aref *fibo-table* 1) 1)
(dotimes (x (1- *fibo-table-limit*))
(setf (aref *fibo-table* (+ x 2))
(+ (aref *fibo-table* x)
(aref *fibo-table* (1+ x))))))
; フィボナッチ関数
(defun fibo (n)
(if (<= 0 n *fibo-table-limit*)
(aref *fibo-table* n)))
|
make-array でベクタを作るところは同じです。次に、関数 init-fibo-table でフィボナッチ数列の値を求めてベクタにセットします。ベクタに値を格納する処理はフィボナッチ数列の定義そのままですね。小さい値から順番にベクタへセットしていくので、簡単に値を計算することができます。
実際に値を取り出す関数が fibo です。したがって、fibo を呼び出す前に必ず init-fibo-table を呼び出すことを忘れないでください。
Lisp の場合、スタックはリストを使って簡単に実現できます。実際 Common Lisp には、リストをスタックとして操作するマクロ push と pop が用意されています。Lisp の主役はリストですが、配列 (ベクタ) でもスタックを実現することができます。
ベクタでスタックを実現する場合、データを格納するためのベクタ本体と、スタックのトップを表す変数が必要になります。この変数のことをスタックポインタ (stack pointer) と呼びます。次の図を見てください。
| 図 7 : ベクタによるスタックの実現 |
|---|
buffer 0 1 2 3 4 5 top (1) [ ] 0 空の状態 (2) [ A ] 1 PUSH A (3) [ A B ] 2 PUSH B (4) [ A B C ] 3 PUSH C (5) [ A B ] 2 POP => C (6) [ A ] 1 POP => B (7) [ ] 0 POP => A |
まず、配列 buffer とスタックポインタ top を用意します。top の値は 0 に初期化しておきます。データをプッシュするときは (aref buffer top) にデータを格納してから、top の値をインクリメントします。逆にポップするときは、top の値をデクリメントしてから、(aref buffer top) にあるデータを取り出します。スタックを操作するたびに、top の値は上図のように変化します。
データをプッシュしていくと、top の値は配列の大きさと等しくなります。配列はリストと違って大きさに限りがあるので、これ以上データを追加することはできません。つまり、スタックは満杯となります。したがって、データをプッシュするとき、スタックに空きがあるかチェックする必要があります。また、top が 0 のときはスタックが空の状態なので、ポップすることはできません。このチェックも必要です。実際のプログラムは次のようになります。
| List 10 : ベクタによるスタックの実装 |
|---|
; 初期化
(defun init-stack (n)
(setq *stack-size* n
*top* 0
*stack* (make-array n)))
; データをスタックに積む
(defun push-down (data)
(when (< *top* *stack-size*)
(setf (aref *stack* *top*) data)
(incf *top*)))
; スタックからデータを取り出す
(defun pop-up ()
(when (plusp *top*)
(decf *top*)
(aref *stack* *top*)))
|
関数 init-stack は大きさ n のスタックを初期化します。ここでは、スタック本体とサイズ、スタックポインタをスペシャル変数として定義しています。関数 push-down は、最初にスタックに空きがあるかチェックしてから、データをスタックに格納します。スタックからデータを取り出す関数 pop-up では、スタックにデータがあることを確認します。
このように、ベクタをスタックとして操作する関数は簡単に作ることができます。実をいうと、Common Lisp には関数 vector-push と vector-pop が用意されていて、ベクタをスタックとして簡単に操作することができます。
vector-push item vector
vector-pop vector
vector-push はスタックとして利用するベクタ vector に item をプッシュします。スタックが満杯で item をプッシュできない場合は nil を返します。逆に、vector-pop は vector からデータをポップします。データをポップできない場合はエラーとなります。
これらの関数は単なるベクタに適用することはできません。make-array でベクタを生成するときに、キーワード :fill-pointer に nil 以外の値を指定することが必要です。指定できる値は 0 からベクタのサイズまでの整数値と t です。t を指定するとベクタのサイズと同じ値になります。この値がフィルポインタ (スタックポインタ) の初期値となります。フィルポインタの値が 0 だとスタックは空の状態で、スタックが満杯になるとフィルポインタはベクタのサイズと同じ値になります。
簡単な使用例を示しましょう。
(setq stack (make-array 10 :fill-pointer 0))
=> #()
(fill-pointer stack)
=> 0
(vector-push 1 stack)
=> 0
stack
=> #(1)
(fill-pointer stack)
=> 1
(vector-pop stack)
=> 1
stack
=> #()
まず最初に、make-array で :fill-pointer を指定してベクタを生成します。この場合、0 を指定したのでスタックは空の状態です。ベクタの表示もフィルポインタの値に左右されます。関数 fill-pointer は、指定したベクタのフィルポインタの値を返します。vector-push はフィルポインタの示す位置にデータを書き込み、フィルポインタの値をひとつ増やします。返り値はデータを書き込んだ位置、つまり、フィルポインタの前の値となります。
次に、vector-pop でデータを取り出します。vector-pop はフィルポインタの値をひとつ減らし、その位置に格納されているデータを返します。この場合、フィルポインタをひとつ減らすと 0 になり、そこに格納されている値 1 を返します。フィルポインタは 0 に戻ったので、スタックは空の状態となります。
スタックをベクタで実装した場合、リストと違ってスタックのサイズには限りがあるので、vector-push を使う場合は返り値を確認しておいた方がよいでしょう。もしも、最初に設定したスタックのサイズを越えてデータをプッシュしたい場合は、関数 vector-push-extend を使います。この関数を使う場合、make-array でキーワード :adjustable に nil 以外の値を指定し、ベクタの大きさを動的に変更できるように設定しておく必要があります。
vector-push-extend item vector &optional extension
ベクタを拡張する以外は vector-push と同じです。extension はベクタに追加する要素の個数を指定します。まあ、これは Lisp システムに任せておけばいいので、特に指定する必要はないでしょう。簡単な使用例を示します。
(setq stack (make-array 3 :fill-pointer t :adjustable t))
=> #(nil nil nil)
(vector-push 1 stack)
=> nil
(vector-push-extend 1 stack)
=> 3
stack
=> #(nil nil nil 1)
:adjustable に t を指定してベクタを生成します。:fill-pointer に t を指定したので、スタックは満杯の状態です。この場合、vector-push はデータをプッシュできないので nil を返します。vector-push-extend はベクタを拡張するので、データをプッシュすることができます。
素数を求める では、リストに素数を格納しました。このプログラムでは、新しい素数をリストの最後尾に追加するため append を使っていますが、append は第 1 引数のリストをコピーするので、リストが長くなると効率が悪くなります。そこで、リストではなくベクタに素数を格納してみましょう。次のリストを見てください。
| List 11 : 素数を求める（ベクタ版） |
|---|
; 素数のチェック
(defun prime-p (n k prime-list count)
(dotimes (m count)
(cond ((zerop (mod n (aref prime-list m))) (return))
((<= k (aref prime-list m)) (return t)))))
; n 個の素数のベクタを返す
(defun prime-vector (n)
(let ((prime-list (make-array n))
(count 0))
(setf (aref prime-list count) 2)
(incf count)
(do ((m 3 (+ m 2)))
((<= n count) prime-list)
(when (prime-p m (sqrt m) prime-list count)
(setf (aref prime-list count) m)
(incf count)))))
|
配列はリストと違って大きさを簡単に変更できません。そこで、prime-vector には求める素数の個数を与えることにします。10000 までの素数を求める場合、素数は全部で 1229 個あるので引数 n の値は 1229 になります。
最初に、大きさ n のベクタを生成して変数 prime-list にセットし、素数を数える変数 count を 0 に初期化します。そして、素数 2 をベクタにセットします。素数をベクタに登録したら、incf で count をインクリメントすることをお忘れなく。あとは、do の終了条件を (<= n count) に変更することと、prime-p で dolist を dotimes に変更するくらいで、とくに難しいところはないでしょう。リストを読んでくださいね。
それでは、どの程度の差がつくのか、M.Hiroi のオンボロマシン (Pentium 166 MHz) で試してみました。プログラムはバイトコンパイルすることをお忘れなく。10000 以下の素数 1229 個を求めたところ、ベクタ版は 1.3 秒になりました。リストを使ったプログラムが 1.7 秒だったので、少しだけ速くなりました。求める素数の個数が多くなるほど、その差は大きくなるはずです。興味のある方は試してみてください。