プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(25)

ブログのテーマを変えました。一行に収まる文字数が少なかったのが改善されました。
それはともかく「Land of Lisp」やっていきます。
本日からは第9章、「より進んだデータ型とジェネリックプログラミング」です。

配列

Common Lispの配列はリストによく似ているそうです。
配列を使うことの主な利点は、どの場所にも定数時間でアクセスできることだそう。

配列を作るには、配列の大きさを指定してmake-arrayを呼びます。

CL-USER> (defparameter x (make-array 3))
X
CL-USER> x
#(NIL NIL NIL)
CL-USER>

配列は先頭に#が付いたリストとして表されるみたいですね。
配列から要素を取り出したり入れたりするのに使う関数はarefだそうです。
そして配列に値をセットするのに使うのは、知っております、setfですね。

CL-USER> (setf (aref x 1) 'hoge)
HOGE
CL-USER> (setf (aref x 2) 'huga)
HUGA
CL-USER> x
#(NIL HOGE HUGA)
CL-USER> (aref x 1)
HOGE
CL-USER>

setfとarefのこの組み合わせが、ジェネリックプログラミングと呼ばれる機能だそうです。

ジェネリックなセッター

Common Lispジェネリックなセッターをサポートしている、と言われるそうです。
その意は、データ構造から値を取り出すコードと、値を入れるコードが同じ形で書けるということだそう。
上のものでいうと、第二引数の(aref x 2)を値を取り出すだけでなく、そこに値を突っ込んでいます。

setfの最初の引数は、汎変数と呼ばれるCommon Lisp内の特別なミニ言語になっているそうです。
その意味するところはよくわかりませんが、かなり複雑なことがそこでできるらしいです。

CL-USER> (setf foo (make-array 4))
#(NIL NIL NIL NIL)
CL-USER> (setf (aref foo 2) (list 'x 'y 'z))
(X Y Z)
CL-USER> foo
#(NIL NIL (X Y Z) NIL)
CL-USER> (setf (car (aref foo 2)) (make-hash-table))
#S(HASH-TABLE :TEST FASTHASH-EQL)
CL-USER> foo
#(NIL NIL (#S(HASH-TABLE :TEST FASTHASH-EQL) Y Z) NIL)
CL-USER> (setf (gethash 'zoink (car (aref foo 2))) 5)
5
CL-USER> foo
#(NIL NIL (#S(HASH-TABLE :TEST FASTHASH-EQL (ZOINK . 5)) Y Z) NIL)
CL-USER>

写経しただけですが、fooの第3要素に何か恨みでもあるのかと勘ぐってしまうぐらいの変更が加えられています。
論点はそこじゃないですね。汎変数とやらの中で行われている処理のことでした。
どれだけデータ構造がネストしようが、どんなデータ型が使われようが、
setfを使えば統一した形でデータを変更できるのだ、と豪語されています。

配列とリスト

配列とリストを比較するようです。
配列のデータをarefで取り出せるように、リストのデータはnthで取り出せるそうです。

CL-USER> (nth 3 '(cat dog human pig))
PIG
CL-USER>

しかしこれはリストの先頭の方の要素にアクセスするときしか実用的でないそうです。
繰り返し言われている通りリストはコンスセルの集まりであるので、
後の要素にアクセスするには先頭の要素から順に辿っていかねばならないからだそう。
これに対して配列ならば、10000個の要素があったとしても(aref x 9999)とすれば一発で辿り着けます。
配列って素晴らしい!

ハッシュテーブル

ハッシュテーブルはalistに似たものだそうです。同じようにキーを探して値を取り出します。
しかし勿論、alistより速いと。もう魔法のように速いそうです。

ハッシュテーブルは先程も例で出てきましたが、make-hash-tableで作ります。
そしてgethashで取り出します。setfで値がセットできます。

CL-USER> (defparameter x (make-hash-table))
X
CL-USER> x
#<HASH-TABLE :TEST EQL :COUNT 0 {1003FB4E93}>
CL-USER> (setf (gethash 'foo x) 'hoge)
HOGE
CL-USER> (gethash 'foo x)
HOGE
T
CL-USER> (gethash 'bar x)
NIL
NIL
CL-USER> 

値が2つ返ってきますね。1つ目が取り出されたデータ、2つ目がキーが存在したか否かです。

複数の戻り値

そういえば皆さん、関数が返す値を「戻り値」と呼びますか?それとも「返り値」?
自分はできるだけ戻り値と呼びたい派ですが、強いこだわりではないので時々返り値と呼んでしまいます。

さて、Common Lispでは複数の戻り値を出す関数がありますね。
例として、小数を含む数を丸めるroundが出ています。

CL-USER> (round 4.8)
5
-0.19999981
CL-USER>

えぇ…(困惑)。まあいいや、とにかく引数を丸めた値と丸めの余りが返ってきます。
複数の値を返す関数を作るには、valueを使えばいいそうです。

CL-USER> (defun foo()
           (values 'fizz 'buzz))
FOO
CL-USER> (foo)
FIZZ
BUZZ
CL-USER> 

とはいえ、戻り値を利用して計算を続ける場合は最初の戻り値だけが使われます。
もし全部の戻り値が欲しいなら、multiple-value-bindというのを使うそうです。

CL-USER> (princ (foo))
FIZZ
FIZZ
CL-USER> (multiple-value-bind (a b) (foo)
           (princ a)
           (princ b))
FIZZBUZZ
BUZZ
CL-USER>

複数の戻り値、使いづらそうですね。便利な場合もあるそうですが。

ハッシュテーブルの性能

ハッシュテーブルから値を取り出すのもやっぱり定数時間でできます。
ハッシュテーブル速い!凄い!
とはいえ常にハッシュテーブルが常に最速だとは限らないそう。

以下が理由です。
・テーブルが大きいと仮想メモリページを読み書きして速度低下。キャッシュミスも増加する。
ハッシュ関数でキーから生成されるハッシュ値が衝突したら、それでも動くが速度が低下する。
・小さなテーブルではalistに効率で負けたりする。
・値を徐々に増やしていってある閾値を超えると、多くのデータを格納するためにテーブルを作り変える。
 その時に時間がかかる。

ハッシュテーブルが最適と限らないもう一つの理由として、
ハッシュテーブルは伝統的なLispのデータ構造に比べて「Lisp的でない」ということがあるそう。
コンスセルのようにREPLで自然に中身を出力したり、
直接リテラルをタイプできないのでデバッグがやりにくいそうです。それは嫌だなあ。

簡単な指針としては、新しいコードを考える時は配列やハッシュテーブルを考えないようにするそうです。
性能に問題が出てきて初めて、ボトルネックになっている部分を書き換えていくと。

ハッシュテーブルによる性能改善

昨日まで作っていたゲームをおそろく効率の悪い部分があるそうで、
その部分をハッシュテーブルに書き換えて改善していきます。

ノードとエッジのリストを作って街のグラフを表現していたわけで、
あるノードを起点とするエッジを探すには毎回リストの頭から順に探していたそうです。
まあ、それでもノードの数は30だったので別に遅いとか感じることはありませんでした。
じゃあいっぱいノードとエッジがあったら?
というわけで性能測定の時間です。

CL-USER> (setf *edge-num* 1000)
1000
CL-USER> (setf *node-num* 1000)
1000
CL-USER> (time (dotimes (i 100) (get-connected 1 (make-edge-list))))
Evaluation took:
  1.442 seconds of real time
  1.437859 seconds of total run time (1.434820 user, 0.003039 system)
  99.72% CPU
  3,173,831,676 processor cycles
  1 page fault
  16,710,368 bytes consed
  
NIL
CL-USER>

…思っていたよりずっと早かったです。参考書では1分近くかかっていますが。
PCの進化はやっぱり凄いってことですかね。

timeコマンドは、コードの実行時間を測る時に便利なユーティリティ関数だそう。
dotimesは指定した回数だけコードを実行する関数であり、ここでは100回街を作っています。
エッジのリストをハッシュテーブルにすれば、get-connectedはノード間の接続を
定数時間で見つけられるようになります。

CL-USER> (defun hash-edges (edge-list)
           (let ((tab (make-hash-table))) ;tabというハッシュテーブルを作成
             (mapc (lambda (x)                              ;edge-listの要素のcar部分をnodeに入れて
                     (let ((node (car x)))                  ;edge-listのcarがキー,cdrがデータな
                       (push (cdr x) (gethash node tab))))  ;ハッシュテーブルを作成
                   edge-list)
             tab))
HASH-EDGES
CL-USER>

エッジのリストをハッシュテーブルにする関数ですね。
pushもハッシュテーブルに対して働けるし、第一引数は汎変数だそう。
色々なんでこれでいいのかの説明が書いてあるのですが…ちょっとまだハッシュテーブルを理解できていません…。
そのうちまた「実践Common Lisp」に行って修行をする必要がありますね。

訪問済みノードのリストもハッシュテーブルにすればさらに早くなるはずです。

CL-USER> (defun get-connected-hash (node edge-tab)
           (let ((visited (make-hash-table)))              ;visitedハッシュテーブルを作成
             (labels ((traverse (node)                     
                        (unless (gethash node visited)     ;nodeキーがvisitedになければ
                          (setf (gethash node visited) t)  ;nodeキーでtを格納
                          (mapc (lambda (edge)             ;edge-tabをnodeキーで検索した結果で
                                  (traverse edge))         ;更にtraverse
                                (gethash node edge-tab)))))
               (traverse node))
             visited))
GET-CONNECTED-HASH
CL-USER>

引数として渡したノードから到達可能な、全てのノードが記録されたvisitedが返ってきます。

新しいコードでまた性能測定をしてみましょう。

CL-USER> (time (dotimes (i 100)
                       (get-connected-hash 1 (hash-edges (make-edge-list)))))
Evaluation took:
  0.003 seconds of real time
  0.003181 seconds of total run time (0.003150 user, 0.000031 system)
  100.00% CPU
  7,092,108 processor cycles
  1,113,296 bytes consed
  
NIL
CL-USER>

はやっ!以前の結果を下にもう一回書いておきます。

CL-USER> (time (dotimes (i 100) (get-connected 1 (make-edge-list))))
Evaluation took:
  1.442 seconds of real time
  1.437859 seconds of total run time (1.434820 user, 0.003039 system)
  99.72% CPU
  3,173,831,676 processor cycles
  1 page fault
  16,710,368 bytes consed
  
NIL
CL-USER>

性能の差は歴然ですね。
ハッシュテーブルって凄い!

ハッシュテーブルの素晴らしさを目の当たりにしたところで今日は終わりにします。
あまり理解できていないまま写経だけしちゃってる感じでした。どうにかしたいところ。