xyzzy Lisp Programming

構造体

構造体は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能です。Ｃ言語ユーザーにはおなじみの機能ですね。Common Lisp は構造体をサポートしていて、xyzzy Lisp でも構造体を利用することができます。ちなみに、拙作の X68000 用 Lisp インタプリタ VTOL には構造体は実装されていませんが、オブジェクト指向のクラスで代用することができます。

Ｃ言語の構造体はデータ型を定義するだけですが、Common Lisp の構造体はそれだけではなく、データを生成する関数 (コンストラクタ) やアクセス関数を自動的に生成します。

●構造体の定義

構造体はマクロ defstruct を使って定義します。

(defstruct 構造体名
    (スロット名 デフォルト値)
    ・・・・
    (スロット名 デフォルト値))

スロット (slot) とは、構造体で定義した変数のことです。defstruct は構造体の定義のほかに、次の関数を生成します。

• 定義したデータを作るコンストラクタ make-構造体名 を生成する。
• スロットの値をリードするアクセス関数 構造体名+変数名 を生成する。
• スロットへの書き込みは setf とアクセス関数 で行うことができる。
• データをコピーする関数 copy-構造体名 を生成する。
• データ型を判定する述語 構造体名-p を生成する。

defstruct はデータ型を定義して必要な関数を生成するだけで、実際のデータを作り出すわけではないことに注意してください。それでは、簡単な例を示しましょう。

(defstruct foo (a 10) (b nil) c)
=> #<structure-definition: foo>

(setq z1 (make-foo))
=> #S(foo a 10 b nil c nil)
(setq z2 (make-foo :b 20 :c 30))
=> #S(foo a 10 b 20 c 30)

(foo-a z1)
=> 10
(setf (foo-a z1) 100)
=> 100
z1 => #S(foo a 100 b nil c nil)

(setq z3 (copy-foo z2))
=> #S(foo a 10 b 20 c 30)
(equal z2 z3)
=> nil
(equalp z2 z3)
=> t

(foo-p z1)
=>t

xyzzy Lisp の場合、構造体は #S(名前 スロット名 値 ... ) と表示されます。また、スロット c のように、デフォルト値を省略すると nil に初期化されます。コンストラクタでは、スロット名をキーワードとして使用することで、その初期値を設定することができます。

スロットのリード・ライトとデータ型の判定は簡単ですね。copy-foo はデータをコピーします。コピーしたデータは equal で判定すると nil になりますが、equalp で判定すると t になります。構造体を使うと、これらの関数が自動的に生成されるのでとても便利です。

●defstruct のオプション

defstruct はいろいろなオプションを指定することができます。その中で、生成される関数の名前を変更するオプションと、ほかの構造体を取り込むオプション :include を説明します。

オプションの指定方法は、次のように行います。

(defstruct (name (option1 data1) (option2 data1) ...) ... )

それでは簡単な例を示しましょう。

(defstruct (bar (:conc-name get-)
                (:constructor create-bar))
  (a 10) (b 20))
=> #<structure-definition: bar>

(setq z1 (create-bar))
=> #S(bar a 10 b 20)
(get-b z1)
=> 20

:include オプションを使うと、既存の構造体を取り込むことができます。

(defstruct foo (a 10) (b 20))
=> #<structure-definition: foo>
(defstruct (bar (:include foo)) (c 30))
=> #<structure-definition: bar>

(setq z1 (make-foo))
=> #S(foo a 10 b 20)
(setq z2 (make-bar))
=> #S(bar a 10 b 20 c 30)

(foo-a z1)
=> 10
(bar-a z2)
=> 10
(foo-a z2)
=> 10

bar は foo を inlcude しているので、foo の構造を取り込むことができます。したがって、foo のスロット a, b と bar で定義したスロット c を持っています。このとき、foo で生成したアクセス関数は、bar のスロット a, b にもアクセスできることに注意してください。

構造体 bar を定義するときに、foo で指定したデフォルト値を変更することができます。次の例を見てください。

(defstruct (bar (:include foo (a 100))) (c 30))
=> #<structure-definition: bar>

(setq z1 (make-foo))
=> #S(foo a 10 b 20)
(setq z2 (make-bar))
=> #S(bar a 100 b 20 c 30)

:include の後ろにスロットのデフォルト値を記述します。例のように (a 100) と設定すれば、構造体 bar のスロット a は 100 に初期化されます。

●位置によるコンストラクタ (2010/10/16)

defstruct のオプション :constructor はコンストラクタの名前だけではなく、次の書式で標準とは異なるコンストラクタを定義することができます。

(:constructor name arglist)

name はコンストラクタの名前、arglist はリストで、スロットを初期化するための引数を指定します。このとき、仮引数名がスロットと同じ名前であれば、実引数の値がスロットの初期値となります。つまり、キーワードではなく引数の位置によりスロットの初期値を指定するわけです。

簡単な例を示しましょう。

(defstruct (foo
            (:constructor create-foo (a b)))
  a b)
=> #<structure-definition: foo>
(create-foo 1 2)
=> #S(foo a 1 b 2)

(make-foo)
=> #S(foo a nil b nil)
(make-foo :a 10 :b 20)
=> #S(foo a 10 b 20)

構造体 foo のスロットは a, b です。コンストラクタ create-foo の引数も a, b で、スロットと同じ名前です。(create-foo 1 2) を評価すると、foo のスロット a は 1 に b は 2 に初期化されます。xyzzy Lisp の場合、デフォルトで生成されるコンストラクタ make-foo も使用することができますが、CLISP (ver 2.44) と SBCL (ver 1.0.29) は make-foo を生成しません。ご注意くださいませ。

:constructor は複数回用いることができるので、異なるコンストラクタを定義することができます。また、arglist の中ではラムダリストキーワード &key, &optional, &rest, &aux を使用することができます。

簡単な例を示しましょう。

(defstruct (bar
            (:constructor create-bar (a b))
            (:constructor create-bar-x (x &aux (a (* x 10)) (b (* x 20)))))
  a b)
=> #<structure-definition: bar>

(create-bar 1 2)
=> #S(bar a 1 b 2)
(create-bar-x 5)
=> #S(bar a 50 b 100)

create-bar はスロット a, b を初期化します。create-bar-x は引数 x の値を使ってスロット a, b を初期化します。&optional (x 5) とすれば、x のデフォルト値を設定することができますし、&key (x 5) とすればキーワード :x を使って x の値を指定することができます。このように、ラムダリストキーワードを使ってスロットの初期化を柔軟に行うことができます。

●データ抽象（またはカプセル化）

ところで、わざわざ構造体を使わなくてもリストで十分ではないか、と思われる方もいるでしょう。実際、リストを使って新しいデータ型を表すことも可能です。たとえば、リストの第 1 要素をデータ型名 foo とし、第 2 要素をスロット a 、第 3 要素をスロット b 、第 4 要素をスロット c としましょう。コンストラクタやアクセス関数だって、わざわざ定義することもありません。

(setq z (list 'foo 10 20 30))
=> (foo 10 20 30)
(second z)
=> 10
(setf (second z) 100)
100
z => (foo 100 20 30)

簡単にプログラムできるように思えますが、この方法には大きな弱点があるのです。ひとつは、データにアクセスするときに、要素の位置とデータの対応をプログラマが把握していないといけません。スロット c はリストの何番目だったかな、a, b, c の 3 番目か、いや先頭にデータ型のシンボルが入るから 4 番目か、などと考えながらプログラムするのではストレスがたまってしまいますね。

もうひとつは、データ構造を変更するときです。たとえば、スロット a が不用になったので、リストから削除することにしました。すると、スロット b, c の位置がひとつずつ前へずれるので、アクセスしている個所をすべて修正しなければいけません。データへのアクセスは単なるリスト操作関数にすぎないので、その関数が目的のデータを操作しているのか、それとも、それ以外のデータを操作しているのかを区別しながら、すべてのプログラムを修正しなければいけません。この修正作業は、プログラムの規模が大きくなればなるほど困難なものになります。

ようするに、データに直接アクセスするから、このような問題を引き起こすのです。そこで、次のようなアクセス関数を定義してみましょう。

(defun get-a (data)
  (second data))
(defun put-a (data value)
  (setf (second data) value))

(defun get-b (data)
  (third data))
(defun put-b (data value)
  (setf (third data) value))

(defun get-c (data)
  (fourth data))
(defun put-c (data value)
  (setf (fourth data) value))

アクセス関数の仕様さえわかっていれば、スロット a がリストの 2 番目の要素に対応するといった、データ構造の詳細を把握する必要はありませんね。それから、関数名によってスロットの値をリードしていることが明確になります。また、スロット a を削除する場合、関数 get-a を検索すれば、修正個所を簡単に見つけることができます。スロット b, c にしても、関数 get-b, put-b を (second data) に、get-c, put-c を (third data) に修正するだけで、ほかのプログラムを見直す必要はまったくありません。

このように、データ構造に直接アクセスせず、アクセス関数を経由してデータのリード・ライトを行うことを、データ抽象とかカプセル化といいます。わざわざアクセス関数を用意するのは面倒なようですが、そのことによりデータ構造の細かいところを気にしなくてもいいわけです。それだけプログラムも読みやすくなり、修正にも強いプログラムを作ることができます。

Ｃ言語の構造体はデータ構造を定義するだけです。したがって、カプセル化を行うにしても、アクセス関数はプログラマが用意しなければいけません。ところが、Common Lisp の場合は、defstruct を使用するだけでアクセス関数も自動的に用意されるため、カプセル化を簡単に行うことができるのです。これが Common Lisp で構造体を使うメリットです。

このデータ抽象を進めていくと、「オブジェクト指向」 ^[*1] へとつながります。ここでオブジェクト指向の話はしませんが、興味のある方は拙作のページ お気楽 CLOS プログラミング入門 をお読みください。

●単語の出現回数を求める

それでは簡単な例題として、ファイルを読み込んで単語ごとに出現回数を求めるプログラムを作ってみましょう。単語の切り分けですが、xyzzy Lisp には split-string という便利な関数が用意されています。

split-string string separator &optional ignore-empty char-bag

split-string は文字列 string を区切り文字 separator で分割し、リストに格納して返します。separator に文字列を与えると、文字列の文字が区切り文字に指定されます。簡単な例を示しましょう。

(split-string "/usr/work/xyzzy" #\/)
=> ("usr" "work" "xyzzy")

(split-string "xyzzy Lisp\tCommon Lisp" " \t")
=> ("xyzzy" "Lisp" "Common" "Lisp")

最初の例では、文字列を文字 / で分割します。次の例では、文字列を空白とタブで分割します。今回は空白とタブで単語を切り分けることにします。

次は構造体を定義します。次のプログラムを見てください。

List 1 : 構造体の定義

(defstruct (WordCount (:conc-name get-))
  (word nil)
  (count 1))

単語は word に格納し、count で出現回数を数えます。:conc-name に get- を指定しているので、word と count のアクセス関数は get-word と get-count になります。

次はプログラム本体を作りましょう。単語をセットした WordCount はリストに格納しておきます。ファイルから単語を切り出したとき、リストに同じ単語がないか関数 find でチェックします。同じ単語を見つけたら、その単語の出現回数 count をひとつ増やします。そうでなければ、新しい WordCount を生成して単語を word にセットします。プログラムは次のようになります。

List 2 : 単語の出現回数を求める

(defun word-count (filename)
  (with-open-file (in filename :direction :input)
    (let (buffer word-list wc)
      (while (setq buffer (read-line in nil))
        (dolist (word (split-string buffer " \t"))
          (if (setq wc (find word word-list :key #'get-word :test #'equal))
            (incf (get-count wc))
            (push (make-WordCount :word word) word-list))))
      (print-word-count word-list))))

; 単語ごとの出現回数を表示
(defun print-word-count (word-list)
  (dolist (wc (sort word-list #'string< :key #'get-word))
    (format t "~A ~D~%" (get-word wc) (get-count wc))))

関数 word-count の引数 filename はファイル名を表します。まず、with-open-file で filename をリードオープンします。そして、関数 read-line で 1 行ずつ読み込み、split-string で単語に切り分けます。

あとは、dolist で単語 word をひとつずつ取り出して、列関数 find で word-list から同じ単語を検索します。単語は WordCount の word にセットされているので、キーワード :key にはアクセス関数 get-word を指定し、文字列を比較するためキーワード :test には equal を指定することに注意してください。デフォルトの eql では動作しません。また、:test に equalp を指定すると、英大小文字を区別せずに文字列の比較が行われます。

同じ単語を見つけたら incf で WordCount の count をひとつ増やします。incf や decf は setf と同様に、アクセス関数で変数を指定することができます。find は見つけた構造体を返すので、それを wc にセットします。そして、(incf (get-count wc)) とすることで、wc の count を +1 することができます。見つからなければ、make-WordCount で新しい WordCount を生成して word-list にセットします。

●文字列の比較 (修正 2009/02/21)

最後に、print-word-count で単語と出現回数を出力します。単語は昇順にソートします。Common Lisp には文字列を比較する関数が用意されています。

string=  string1 string2
string<  string1 string2
string>  string1 string2
string<= string1 string2
string>= string1 string2
string/= string1 string2

これらの関数は 2 つの文字列を比較します。このとき英大小文字の区別をします。条件を満たせば t 真 ^[*2] を返し、そうでなければ nil を返します。条件はそれぞれ、string1 が string2 と等しい、小さい、大きい、小さいか等しい、大きいか等しい、等しくないです。簡単な例を示します。

(string= "abcd" "abcd") => t
(string= "abcd" "ABCD") => nil
(string< "abcd" "efgh") =>  t  0
(string< "abc" "ABCDE") => nil

英大小文字を区別しないで比較する場合は、次の関数を使います。

string-equal        string1 string2
string-lessp        string1 string2
string-greaterp     string1 string2
string-not-greaterp string1 string2
string-not-lessp    string1 string2
string-not-equal    string1 string2

2 つの文字列を英大小文字の区別をしないで比較し、条件を満たせば t 真を返します。そうでなければ nil を返します。条件はそれぞれ、string1 が string2 と等しい、小さい、大きい、小さいか等しい、大きいか等しい、等しくないです。簡単な例を示します。

(string-equal "ABCD" "abcd") => t
(string-equal "ABCD" "ABCD") => t

これらの関数は、キーワード :start1, :end1, :start2, :end2 を指定することができます。:start1 と :end1 は引数 string1 の範囲、:start2 と :end2 は引数 string2 の範囲を表します。また、引数にシンボルを与えると、シンボルを文字列に変換してから比較を行います。次の例を見てください。

(string= 'abc "abc") => t
(string-equal 'abc "ABC") => t

●実行結果

これでプログラムは完成です。さっそく実行してみましょう。次に示すテストデータを用意しました。

ABCD 0123 ABCD efgh abcd abcd abcd EFGH 
ABCD 0123 0123 0123 EFGH efgh 0123 efgh 
abcd 0123 efgh 0123 abcd 0123 4567 EFGH 
ABCD efgh ABCD 4567 ABCD efgh EFGH abcd 
0123 4567 ABCD 4567 EFGH abcd abcd 0123 
4567 efgh abcd 0123 0123 0123 efgh abcd 
EFGH abcd 4567 abcd abcd EFGH 0123 0123 
4567 EFGH abcd 4567 EFGH 4567 EFGH ABCD 

単語の種類は 6 種類で総数は 64 個です。このデータをファイル test.dat に格納し、word-count を実行しました。結果は次のようになりました。

(word-count "test.dat")
0123 15
4567 9
ABCD 8
EFGH 10
abcd 14
efgh 8
nil

正常に動作していますね。ところで、ファイルのサイズが大きくなり単語の種類が増えると、このプログラムでは実行速度が遅くなります。実は単語の種類が増えると、単語を検索する find の処理で時間がかかるのです。find は列の先頭から順番に要素を比較してデータを探します。これを線形探索といいます。

データ数が少なければ線形探索でも何とかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムがハッシュ法と二分探索木です。次はちょっと寄り道をして、探索アルゴリズムについて簡単に説明します。

ちょっと寄り道

■二分探索

あるデータの中から特定のデータを探す場合、いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを線形探索 (linear searching) といいます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。

これに対し二分探索 (binary search) は、log ₂ N に比例する時間でデータを探すことができる高速なアルゴリズムです。ただし、探索するデータはあらかじめソートしておく必要があります。次の図を見てください。

                    図 1 : 二分探索

二分探索はベクタ向きのアルゴリズムで、探索する区間を半分に分けて調べます。キーが 66 の場合を考えてみます。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありませんね。したがって、後半部分だけを探索すればいいのです。

あとは、これと同じことを後半部分に対して行います。最後には区間の要素がひとつしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。

上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。

それでは、ベクタから数値を二分探索するプログラムを作ってみましょう。二分探索は再帰定義を使わなくても簡単にプログラムできます。次のリストを見てください。

List 3 : 二分探索

(defun binary-search (item table)
  (let ((low 0) (high (1- (length table))) middle)
    (while (<= low high)
      (setq middle (truncate (+ low high) 2))
      (cond ((= (aref table middle) item)
             ; 発見
             (return item))
            ((< (aref table middle) item)
             (setq low (1+ middle)))
            (t (setq high (1- middle)))))))

最初に、探索する区間を示す変数 low と high を初期化します。ベクタの大きさは length で取得し、最後の要素の位置を high にセットします。次の while ループで、探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて middle にセットします。cond で middle の位置にある要素と item を比較し、等しい場合は探索成功です。return で while ループから脱出します。

item が大きい場合は区間の後半を調べます。変数 low に middle + 1 をセットします。逆に、item が小さい場合は前半を調べるため、変数 high に middle - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し、binary-search は nil を返します。

簡単な実行例を示しましょう。

(setq a #(11 22 33 44 55 66 77 88 99))
=> #(11 22 33 44 55 66 77 88 99)

(binary-search 44 a) => 44
(binary-search 40 a) => nil

二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。

したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、ハッシュ法や二分探索木を使うといいでしょう。

ちょっと寄り道

■木構造と二分木

今回は木構造 (tree structure) について簡単に説明しましょう。木構造は節 (ノード) と呼ばれる要素に対して、階層的な関係 (親子関係) を表したデータ構造です。略して木 (tree) と呼ばれる場合も多いです。身近な例では、ディレクトリ (フォルダ) の階層構造が木にあたります。ディレクトリにルートディレクトリがあるように、木にも根 (root) と呼ばれる節が存在します。次の図を見てください。

        図 2 : 一般的な木構造の一例

木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を木の高さといいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを部分木といいます。

木は、ある節からほかの節に至る経路を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。

ある節から根の方向にさかのぼるとき、途中で通っていく節を先祖といい、直接繋がっている節を親といます。これは、逆から見ると子孫と子という関係になります。子を持たない節をとくに葉と呼ぶことがあります。上図の場合、G は J, K の親で、J は G の子になります。J と K は子を持っていないので葉となります。

■二分木

子は、左 < 右 の順番で節に格納するのが一般的です。これを順序木といいます。また、順番が無い木を無順序木と呼びます。そして、節が持っている子の数を次数といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。そして、すべての節の次数を N に揃えた順序木をN 分木と呼びます。とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。

                図 3 : 二分木の一例

上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータ、右側の子には大きいデータが配置されるように木を構成します。

二分木はデータの探索・挿入を高速に行うことができるデータ構造です。たとえば、上図の二分木から 19 を探してみましょう。まず、root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。

二分木の探索は二分探索と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。したがって、データ数を N とすると、線形探索では平均で N / 2 回の比較が必要になりますが、二分木を使うと log₂ N 程度の回数で収まります。たとえばデータが 100 個ある場合、線形探索では平均で 50 回データを比較しなければいけないのに、二分木では高々 7 回の比較で済むわけです。

この二分木を利用して探索を行うのが二分探索木 (binary search tree) です。データの総数を N とすると、二分探索木はデータの探索、挿入、削除といった操作を、log₂ N に比例する実行時間で行うことができます。

ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは、AVL 木、2-3 木、B 木、B* 木、2 色木 (赤黒木) などがあります。

二分探索木の詳細は 二分探索木 をご覧ください。構造体を使って二分探索木をプログラムしています。

ちょっと寄り道

■ハッシュ法

今回は高速な検索アルゴリズムの本命であるハッシュ法 (hashing) を簡単に説明します。ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、Tcl や Perl など連想配列をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。

ハッシュ法は、ハッシュ表 (hash table) と呼ばれるデータを格納する配列と、データを数値に変換するハッシュ関数 (hash function) を用意します。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値をハッシュ値 (hash value) と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。

ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性があります。これをハッシュ値の衝突 (collision) といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。

第 1 の方法はハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納する工夫が必要になります。このときよく利用されるデータ構造がリストです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されているリストの中からデータを探索します。

第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。新しい場所を探すといっても、ハッシュ表の先頭から線形探索するのではなく、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。これを空いている場所が見つかるまで繰り返します。

Common Lisp の場合、ハッシュ表というデータが用意されているので、ハッシュ法を簡単に利用することができます。ハッシュ表の詳細は拙作のページ ハッシュ表 をお読みください。

■簡単な例題

Common Lisp にはハッシュ表が用意されていますが、ここでは実際に第 1 の方法でハッシュ法を実装してみましょう。簡単な例題として、3 次元空間の異なる点 (x y z) を n 個作る関数を作ります。要素 x, y, z は 0 から 99 までの整数値とし、乱数で生成することにします。生成する点の個数が少なければ、ハッシュ法を使わなくても線形探索で十分です。プログラムは次のようになります。

List 4 : n 個の異なる点を作る

; 点 (x y z) を作る
(defun make-point ()
  (let (point)
    (dotimes (x 3 point)
      (push (random 100) point))))

; n 個の異なる点を作る
(defun make-data (n)
  (let ((count 0) point buffer)
    (while (< count n)
      (setq point (make-point))
      ; 線形探索
      (unless (find point buffer :test #'equal)
        (push point buffer)
        (incf count)))
    buffer))

関数 make-data は関数 make-point で点をひとつ生成し、それが今まで生成した点と異なることを find でチェックします。点はリストで表されているので、find のキーワード :test には equal を指定します。デフォルトの eql では動作しないことに注意してください。

find は線形探索なので、点の個数が増えると時間がかかるようになります。実際に xyzzy Lisp で 3000, 4000, 5000 個の点を作ったときの実行時間を示します。実行環境はあいかわらずのオンボロマシン (Pentium 166 MHz) です。プログラムはバイトコンパイルすることをお忘れなく。

点の個数が増えると実行時間が大幅に増加することがわかります。それでは線形探索の代わりにハッシュ法を使ってみましょう。プログラムは次のようになります。

List 5 : n 個の異なる点を作る（ハッシュ法）

; ハッシュ表の大きさ
(defconstant *hash-size* 4001)

; ハッシュ関数
(defun hash-func (point)
  (let ((value 0))
    (dolist (x point (mod value *hash-size*))
      (setq value (+ (* value 100) x)))))

; ハッシュ表に登録
(defun insert-hash (point hash-table)
  (let ((value (hash-func point)))
    (unless (find point (aref hash-table value) :test #'equal)
      (push point (aref hash-table value)))))

; n 個の異なる点を作る
(defun make-data-fast (n)
  (let ((hash-table (make-array *hash-size*))
        (count 0) buffer point)
    (while (< count n)
      (setq point (make-point))
      ; ハッシュ法
      (when (insert-hash point hash-table)
        (push point buffer)
        (incf count)))
    buffer))

第 1 の方法でハッシュ法を実装する場合、ハッシュ値の衝突が頻繁に発生するとデータを格納するリストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。また、リストの代わりに二分探索木を使う方法もあります。

ハッシュ表の大きさは定数 *hash-size* で表します。参考文献 ^[1] によると 『この値が素数だと安心である』 とのことなので、このプログラムでは 4001 としました。5000 よりも少ないですが、ハッシュ法を第 1 の方法で実装する場合は、これでも十分に効果を発揮します。

今回はハッシュ法の例題ということで、ハッシュ値の計算は簡単な方法を採用します。関数 hash-func は点 (x y z) を 100 進数の数字とみなして x * 10000 + y * 100 + z を計算し、それを *hash-size* で割った余りをハッシュ値としています。

データをハッシュ表に登録する関数 insert-hash も簡単です。最初に hash-func でハッシュ値を求め、ハッシュ表 hash-table に格納されているリストを find で線形検索するだけです。見つからない場合は、リストの先頭にデータを登録します。同じデータを見つけた場合、insert-hash はデータを登録せずに nil を返します。

最後の関数 make-data-fast は、生成したデータのチェックにハッシュ法を使います。最初に make-array で大きさが *hash-size* のハッシュ表 hash-table を用意します。そして、make-point でデータを生成したら、関数 insert-hash を呼び出して同一データのチェックを行います。insert-hash の返り値が真ならば point は新しいデータです。buffer に point を追加して count をインクリメントします。

これでプログラムは完成です。実行時間は次のようになりました。

圧倒的にハッシュ法の方が速いですね。簡単なハッシュ関数を使いましたが、ハッシュ法の効果は十分に出ています。今回はハッシュ法を実装しましたが、かわりに Common Lisp のハッシュ表を使ってみるのも面白いと思います。興味のある方はプログラムを改造してみてください。