第9章 より進んだデータ型とジェネリックプログラミング
配列、ハッシュテーブル、構造体といったデータ構造について学ぶ。
9.1 配列
配列はリストに似通っている。リストと配列。配列の利点はどの場所にも低数時間でアクセスできることだそうだ。その定義やら使い方やらだ。
配列を使う
> (make-array 3) ;;此の関数で配列を定義する 3個で添字は0から始まる
#(NUL NIL NIL) ;;配列は#を頭につけてリストと区別する
> (defparameter x (make-array 3))
X
> (aref x 1) ;;此の関数で配列の要素にアクセスする
NIL
> (defparameter x (make-array 3)) ;;配列xを定義したときは全部nil
X ;;配列名が返る
> (setf (aref x 1) 'foo) ;;2番めの要素に'fooをセット
FOO ;;セットした値が返る
> x ;;配列xを指定
#(NIL FOO NIL) ;;配列xの内容
> (aref x 1) ;;配列xの2番めの要素をアクセス
FOO ;;2番めの要素が返るここまでが基本。更に、setfの動作に注意する。
> (setf foo (list 'a 'b 'c))
(A B C)
> (second foo)
B
> (setf (second foo) 'z) ;;注目 Bの位置が返って'zを設定している
Z
> foo
(A Z C)ジェネリックなセッター
setfの第1引数は半変数呼ばれる、特別なミニ言語だそうだ。その威力は下記の通り。
> (setf foo (make-array 4)) ;;配列foo作成
#(NIL NIL NIL NIL)
> (setf (aref foo 2) (list 'x 'y 'z)) ;;配列fooの3番目にリストを格納
(X Y Z)
> foo
#(NIL NIL (X Y Z) NIL) ;;配列がネストした
> (setf (car (aref foo 2)) (make-hash-table)) ;;配列fooの3番めのリストの1番目を
#S(HASH-TABLE) ;;HASH-TABLEに置換
> (setf (gethash 'zoink (car (aref foo 2))) 5) ;;上記のHASH-TABLEに値を追加
5
> foo
#(NIL NIL (#S(HASH-TABLE (ZOINK . 5)) Y Z) NIL) ;;このように複雑な構造となる配列とリスト
リストでできることは配列でも実装可能。ただ、配列のほうが特定の要素にアクセスするのが速い。
> (nth 1 '(foo bar baz)) ;;nth関数は先頭から類っていくので、こんなときは速い
BAR ;;しかし1000番目の要素だとかなりな時間がかかるのだ
> (aref x 1000) ;;配列では何番目でもアクセス速度に差がない配列は値の変更に際してもリストより速い。高速処理なら配列である。
9.2 ハッシュテーブル
ハッシュテーブルはalistよりも高速で動作する。どの言語でもその傾向らしい。
ハッシュテーブルを使う
> (make-hash-table) ;;此の関数でハッシュテーブルを作る
#S(HASH-TABLE ...)
> (defparameter x (make-hash-table)) ;;ハッシュテーブルxを作る
#S(HASH-TABLE ...)
> (gethash 'yup x) ;;此の関数でアクセスる
NIL ; ;;まだ空なので値はNIL
NIL ;;キーがヒットしなかったのでNIL
> (setf (gethash 'yup x) '25) ;;'yupに'25をセットして格納
25
> (gethash 'yup x) ;;'yupでアクセスると25が返る
25 ; ;;ヒットした値
T ;;ヒットしたから真値以前のカフェでの注文票を作ってみよう。簡単になるんだ。
> (defparameter *drink-order* (make-hash-table)) ;;ハッシュの定義
#S(HASH-TABLE ...)
> (setf (gethash 'bill *drink-order*) 'double-espresso) ;;billの注文を格納
DOUBLE-ESPRESSO
> (setf (gethash 'lisa *drink-order*) 'small-drip-coffee) ;;lisaの注文を格納
SMALL-DRIP-COFFEE
> (setf (gethash 'john *drink-order*) 'midium-latte) ;;johnの注文を格納
MIDIUM-LATTE
> (gethash 'lisa *drink-order*) ;;lisaの注文を取り出す
SMALL-GRIP-COFFEE
T複数の値を返す
あまり使われなくなっているようだが、関数から複数の値を返すことができる。リスト形式ではなく、独立した値として。
> (round 2.4) ;;此の関数は2個の値を返している
2 ;
0.4
> (defun foo () ;;valuesで複数の値を返す
(values 3 7))
FOO
> (foo)
3 ;
7
> (+ (foo) 5) ;;そのまま返り値を使うと先頭のが使われる
8
>(multi-value-bind (a b) (foo) ;;全部使う時はmulti-value-bindでマップする
(* a b))
21ハッシュテーブルの性能
ハッシュテーブルは高速に値を取り出せるが、注意も必要。
- 仮想メモリとキャッシュミス
目盛り制限を超えるような大きさになると仮想メモリペジを使うので、また、CPUのキャッシュミスも増加していくのだ。 - ハッシュ値の衝突
ハッシュ関数はまれに異なるキー同士に同じ場所を計算してしまうことがある。衝突してもきちんと動作はするが速度は落ちる。 - 小さなテーブルの効率
ほんの小さなテーブルだった場合、alistの方が早かったりする。 - 操作速度の不均一性
make-hash-table関数は小さなハッシュテーブルを想定しているので、ある程度の大きさを超えると時間がかかるようになる。ハッシュテーブルはある程度以上の大きさで本領を発揮する。
最初は伝統的にリストを基本に設計してゆき、性能に問題が見受けられたら、ハッシュテーブルを試してみる。こんな感じ。
グランド・セフト・ワンプスの性能をハッシュテーブルで改善する
結果だけ書いておく。
time関数で実行時間を測った結果、1分かかった処理が1秒で済むようになった。
的確に使えば素晴らしい結果をもたらすのだ。クセはあるけどねえ。
9.3 構造体
いくつかのデータ型をまとめるには構造体を使うのだ。
構造体を使う
OOPのように、属性を持つオブジェクトを表現する構造体を定義するにはdefstructコマンドを使う。
> (defstruct person name age waist-size favorite-color)
PERSON ;;person構造体はname、age、waist-size、favorite-colorの属性(スロット)を持つ
> (defparameter *bob* (make-person :name "Bob" :age 35 :waist-size 32 :favorite-color "blue")) ;;make-personは自動的に作られる
*BOB*
>*bob*
#S(PERSON :NAME "Bob" :AGE 35 :WAIST-SIZE 32 :FAVORITE-COLOR "blue")
> (person-age *bob*) ;;person-ageも自動的に作られる
35
> (setf (person-age *bob*) 36) ;;setfで年齢を変更する
36
> (defparameter *that-guy* #S(PERSON :NAME "Bob" :AGE 35 :WAIST-SIZE 32 :FAVORITE-COLOR "blue")) ;;#S()の内容で構造体が*that-guy*に定義されている
> (person-age *that-guy*)
36defstructは構造体のインスタンスを作る関数や、属性へのアクセス関数をずべ手自動で作ってくれる、強力なコマンドだ。
構造体をいつ使うか
OOPスタイルは現代の大規模なアプリケーションを作る際に必須だと考えられている。一方、多くのLisperはOOPスタイルに拘らずとも高品質ソフトは書けると思っている。
14章からはそのへんを考察してゆこう。その前にこんなことを。
> (defun make-person (name age wast-size favorite-color)
(list name age wast-size favorite-color))
MAKE-PERSON
> (defun person-age (person) (cadr person))
PERSON-AGE
> (defparameter *bob* (make-person *bob* 35 32 ""blue))
*BOB*
> *bob*
("bob" 35 32 "blue")
> (person-age *bob*)
35関数を沢山書かなければいけないし、それは間違いのもとだ。属性の名前と値を読み取るのも難しい。属性の値を変更することも中々大変なのだ。
OOPに興味がある貴方へはこのCLOSというオブジェクトシステムをおすすめする。
正にCommon LispのおけるOOP対応のシステムであるので。
9.4 データをジェネリックに扱う
Common Lispには沢山のデータ型が備わっているが、多用することによって性能やエレガントさに影響ないよう注意されたい。
リストと配列に格納されている数値を足し合わせたい際などに、データ型によらず使える関数があれば便利だ。此のような関数をジェネリックであると呼ぶ。
Common Lispには沢山なジェネリック関数が備わっていて、ジェネリックライブラリ関数、型述語、defmethod、ジェネリックアクセサと呼ばれる。これらによって書くデータ型ばかりではなく、defstructで作られたユーザ定義型に対しても、共通のコードで対応できることになる。
シーケンスを使う
例えばlength関数はシーケンス関数の一つだ。この関数は3種類のシーケンス型に対して使える。
シーケンス関数はLispにおいて値の列(シーケンス)を表す3種類の主要な型、リスト、配列、文字列を統一的に扱える関数群だ。
(length '(a b c)) ;;リストの要素数
3
(length "blub") ;;文字列の文字数
4
(length (make-array 5)) ;;配列の要素数
5
;;全て同じ関数で足りる勿論リスト専用の長さを求めるlist-length関数も存在する。此の関数はlength関数がデータ型を判断するに要する時間を節約したいような、タイトな場合に使用される。
ほとんどの場合にはlength関数が使われている。
探索のためのシーケンス関数
シーケンスの中から何かを探し出す機能を持つ、シーケンス関数のお話し。
- find-ifは与えた述語を満たす最初の要素を見つける
- countは特定の要素がいくつのシーケンスにあるかを数える
- positionは特定の要素がシーケンスのどの位置にあるかを教えてくれる
- someとeveryはそれぞれ、シーケンス中に条件を満たす要素が非トルあるか、あるいはシーケンス中の要素が全て条件を満たすかを調べる
(find-if #'numberp '(a b 5 d)) ;;此のリストの中に数値はありますか
5 ;;5がありました
(count #\s "mississippi") ;;この文字列にsが何個ありますか
4 ;;4個ありました
(position #\4 "2kewl4skewl") ;;此の文字列内の4の位置はどこですか
5 ;;5の位置です(0から)
(some #'numberp '(a b 5 d)) ;;このリストに数値は含まれますか
T ;;T含まれています
(every #'numberp '(a b 5 d)) ;;此のリストは全て数値ですか
NIL ;;NILいいえ違いますシーケンスの要素について繰り返す関数
rduce関数はシーケンス内全ての要素に対して働きかける。此の様は働きを蒸留すると言っている。
reduceに渡す関数を「縮約関数(reduction function)」と呼ぶ。
map関数は全てのシーケンスに使える。mapcarと同じように動作するが、リストばかりでなく全てのシーケンスに使える。map関数へはどのシーケンス型を返すかを指定できる。
(reduce #'+ '(3 4 6 5 2)) ;;此のリストの中を合計する 全てが数値
20 ;;20でした
(reduce (lambda (best item) ;;リスト中から最大の偶数を見つける lambdaは縮約関数
(if (and (evenp item) (> item best)) ;;この辺が難しい
item
best))
'(7 4 6 5 2)
:initial-value 0) ;;此の場合初期値を与えないとご動作する(7になる)
(drfun sum (lst) ;;新しい関数の中でreduceを使う
(reduce #'+ lst))
SUM
(sum '(1 2 3))
6
(sum (make-array 5 :initial-contents '(1 2 3 4 5)))
15
(sum "blablabla")
Error: The value #\b is not type NUMBER.
(map 'list ;;listを返せと言っている
(lambda (x) ;;文字列内のsをSに変換している
(if (eq x #\s)
#\S
x))
"This is a String") ;;list指定だからこうなる string指定なら文字列で返る
(#\t #\h #\i #\S ... #\g)さらに二つの重要なシーケンス関数
subseq関数はシーケンスの一部を扱うものである。
sort関数はシーケンスをソートする。
(subseq "america" 2 6) ;;文字列を取り出す
"eric"
(subseq '(a b c d) 2 4) ;;リストの要素を取り出す
(C D)
(sort '(5 8 2 4 9 3 6) #'<) ;;小さい方からソートする
(2 3 4 5 6 8 9)
(sort '(5 8 2 4 9 3 6) #'>) ;;大きい方からソートする
(9 8 6 5 4 3 2)型述語を使って自分でジェネリック関数を作る
Lispは動的型付け言語だ。変数や引数はどんな方でも格納できる。同じ変数や引数が実行の別時点で異なる型のデータをもつこともよくある。
従って方を調べる関数が揃っているんだ。
(numberp 5)
T
;;他にはarrayp,characterp,consp,functionp,hash-tablep,listp,stringp,symbolpなどがある。
;;これらは型述語である。
(defun add (a b) ;;add関数を定義
(cond ((and (numberp b)) (+ a b)) ;;数値なら計算
((and (listp a) (listp b)) (append a b)))) ;;リストなら追加
ADD
(add 3 4) ;;数値
7
(add '(a b) '(c d)) ;;リスト
(A B C D)これは例題である。下記の理由で此のような定義は行わないだろう。
- すべての型への対応コードが一つの関数に固まる
上の例では2つだけだったが、調べる型が他に10個もあったとすると、関数が膨れ上がってしまう - 新しい型のサポートを追加するのが大変
型を判定するコーディングの全てに手が入る。新たな型のサポートがそれまでのコードに影響しないのが一番だが - 理解しにくい
大きなcond文や伴う分岐が正しいパスを通っているのか理解し難い - 性能
LISPコンパイラがコードの意図を汲み取れないことによる性能劣化も考えられる
そこで、こんな解決方法が。
defmethod関数を使えば上のadd関数は下記のように書ける。
(defmethod add ((a numeric) (b numeric))
(+ a b))
ADD
(defmethod add ((a list) (b list))
(append a b))
(add 3 4)
7
(add '(a b) '(c d))
(A B C D)以前のコードに影響はない。コンパイラは引数の型の上布を使うことで最適化をやりやすくなる。
defmethodはオブジェクト指向に関係している。defstructで定義した構造体にも使えるのだ。
defstructとdefmethodを合わせて使えば、簡単なオブジェクトシステムになる。
次はそのオブジェクトシステムを使ってゲームを書いてみる。
9.5 オーク・バトル
今回ここを省略する。ゲームをやるときにね。
プレーヤーとモンスターのグローバル変数
ゲームのメイン関数
プレーヤーを管理する関数
プレーヤーの攻撃に使う補助関数
モンスターを管理する関数
モンスターたち
ジェネリックなモンスター
邪悪なオーク
手強いヒドラ
べたべたスライム
狡猾なブリガンド
戦いだ！
9.6 本章で学んだこと
- 配列はリストと似ているが、指定した位置にある要素により効率よくアクセスできる。
- ハッシュテーブルはalistと似ているが、キーに結びついた値をより効率よく検索できる。
- 配列とハッシュテーブルを適切な場所で使えば、プログラムを高速化できる。
- データ構造やアルゴリズムの変更によってプログラムが早くなったかどうかを判断する唯一の正しい方法は、timeコマンドによって計測して見ることだ。
- Common Lispでは、複数のデータ型のオブジェクトに統一的に適用できるジェネリックな関数を持っている。特にシーケンス関数はリスト、配列、文字列の区別をせずに処理できる、便利な関数だ。
- 属性を持つオブジェクトをdefstructコマンドを使って定義できる。
コメント