今回はベクタの「ソート (sorting)」と「二分探索 (binary search)」を取り上げます。拙作のページ「ソートとマージ」ではリストをソートしましたが、このとき新しいリストを生成しました。ベクタの場合、入力されたベクタそのものを操作してソートするアルゴリズムのほうが一般的です。これを in-place アルゴリズムといいます。
クイックソートはベクタ向きのソートアルゴリズムですが、シンプルに再帰呼び出しで実装するとスタック (コールスタック) を消費するので、厳密にいえば in-place アルゴリズムではありません。ですが、最悪のデータでもメモリを大量消費しないように工夫することは可能です。
ベクタのソートアルゴリズムはたくさんありますが、ここでは単純挿入ソートとクイックソートを取り上げることにします。
単純挿入ソートはソート済みのベクタに新しいデータを挿入していくことでソートします。最初は先頭のデータひとつがソート済みと考え、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 単純挿入ソート
プログラムは次のようになります。
リスト : 単純挿入ソート
(defun insert-sort (buff)
(do ((i 1 (1+ i)))
((>= i (length buff)) buff)
(do ((x (aref buff i))
(j (- i 1) (1- j)))
((or (minusp j) (<= (aref buff j) x))
(setf (aref buff (1+ j)) x))
(setf (aref buff (1+ j)) (aref buff j)))))
最初の do ループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ (添字では 1) を取り出して挿入していきます。2 番目の do ループで挿入する位置を探しています。探索は後ろから前に向かって行います。このとき、挿入位置の検索と同時にデータの移動も行っています。ループが最後まで回れば、そのデータは先頭に挿入されることになります。
それでは実行してみましょう。
* (insert-sort #(5 6 4 7 3 8 2 9 1 0)) #(0 1 2 3 4 5 6 7 8 9) * (insert-sort #(9 8 7 6 5 4 3 2 1 0)) #(0 1 2 3 4 5 6 7 8 9) * (insert-sort #(0 1 2 3 4 5 6 7 8 9)) #(0 1 2 3 4 5 6 7 8 9)
単純挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。単純挿入ソートは簡単ですが遅いアルゴリズムなのです。ただし、ソート済みのデータはとても速い、という特徴があります。もしも、ベクタがほとんどソートされている状態であれば、単純挿入ソートでも高速にソートすることができます。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々の区間を同様に分割して 2 つの区間に分けます。最後は区間の要素がひとつになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つの区間について再び同様な分割を行う
図 : クイックソート
基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は区間の真ん中にある要素を選ぶことにしましょう。上図を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つの区間に適用します。これは再帰定義を使えば簡単に実現できます。分割した区間の要素数が 1 になったときが再帰の停止条件になります。プログラムは次のようになります。
リスト : クイックソート (1)
(defun qsort (buff low high)
(let ((p (aref buff (floor (+ low high) 2)))
(i low)
(j high))
(loop
(loop (if (<= p (aref buff i)) (return)) (incf i))
(loop (if (>= p (aref buff j)) (return)) (decf j))
(if (>= i j) (return))
(psetf (aref buff i) (aref buff j)
(aref buff j) (aref buff i))
(incf i)
(decf j))
(when (< low (1- i)) (qsort buff low (1- i)))
(when (> high (1+ j)) (qsort buff (1+ j) high))))
(defun quick-sort (buff)
(qsort buff 0 (1- (length buff)))
buff)
関数 qsort の引数 BUFF がソートするベクタ、LOW が区間の下限値、HIGH が区間の上限値です。qsort は BUFF の LOW から HIGH までの区間をソートします。最初に、区間の真ん中にあるデータを枢軸として選んで変数 P にセットします。そして、最初の loop で P を基準にして区間を 2 つに分けます。
次の loop で、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。同様に次の loop で右側から枢軸以下の要素を探します。お互いの探索位置 I, J が交差したら分割は終了です。return で loop から脱出します。そうでなければお互いの要素を交換します。psetf は psetq と同じ働きをします。交換したあとは I と J の値を更新しておくことを忘れないでください。
そして、分割した区間に対して qsort を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
それでは実行してみましょう。
* (quick-sort #(5 6 4 7 3 8 2 9 1 0)) #(0 1 2 3 4 5 6 7 8 9) * (quick-sort #(9 8 7 6 5 4 3 2 1 0)) #(0 1 2 3 4 5 6 7 8 9) * (quick-sort #(0 1 2 3 4 5 6 7 8 9)) #(0 1 2 3 4 5 6 7 8 9)
クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中央値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数を N とすると N * log N に比例する時間でソートすることができます。逆に、区間での最大値または最小値を枢軸に選ぶと、その要素と残りの要素の 2 つに分割にされることになります。
これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。つまり、挿入ソートと同じくらい遅いソートになるのです。それだけでなく、要素数が多くなるとスタックがオーバーフローする危険性もあります。今回は区間の中間に位置する要素を枢軸としたので、真ん中付近に大きい要素 (または小さな要素) があるデータが最悪の場合にあてはまります。
それでは実際に試してみましょう。データは乱数のほかにも、山型データ (中央のデータがいちばん大きく端にいくほど小さいデータになる)、ソート済みのデータ (昇順)、逆順にソートされたデータ (降順) の 4 種類を用意して、実行時間を比較してみましょう。これらのデータは次のプログラムで簡単に作成することができます。
リスト : テストデータの作成
;;; 乱数データ
(defun make-random-data (n)
(let ((buff (make-array n)))
(dotimes (i n buff)
(setf (aref buff i) (random 1000000)))))
;;; 昇順データ
(defun make-sort-data (n)
(let ((buff (make-array n)))
(dotimes (i n buff)
(setf (aref buff i) i))))
;;; 逆順データ
(defun make-rev-data (n)
(let ((buff (make-array n)))
(dotimes (i n buff)
(setf (aref buff i) (- n i 1)))))
;;; 山型データ
(defun make-yama-data (n)
(let ((buff (make-array n)))
(dotimes (i (floor n 2) buff)
(setf (aref buff i) i
(aref buff (- (length buff) 1 i)) i))))
* (make-random-data 10) #(113500 958198 129774 204665 144684 505823 196613 372705 150458 264491) * (make-sort-data 10) #(0 1 2 3 4 5 6 7 8 9) * (make-rev-data 10) #(9 8 7 6 5 4 3 2 1 0) * (make-yama-data 10) #(0 1 2 3 4 4 3 2 1 0)
実行結果は次のようになりました。
表 : クイックソート (単位 : 秒) 個数 : 乱数 : 昇順 : 逆順 : 山型 ------+------+------+------+------ 10000 : 0.002: 0.005: 0.003: 0.236 20000 : 0.004: 0.005: 0.004: 1.200 40000 : 0.014: 0.007: 0.008: NG 80000 : 0.043: 0.012: 0.014: NG 実行環境 : Ubunts 18.04 (Windows Subsystem for Linux), Intel Core i5-6200U 2.30GHz
山型データの NG は、スタックがオーバーフローしたことを示します。データ数が少ない場合、スタックオーバーフローは発生しませんが、実行時間はとても遅くなります。ほかのデータでは、とても高速にソートすることができました。やっぱり、クイックソートは速いですね。
スタック
[ A ][ B ] ( ) : 分割する。スタックは最初は空
(A) : A をスタックに積む
[ C ][D] (A) : B を分割する
[D] (C A) : C をスタックに積む
[ ] (C A) : D をソートする
[ C ][ ] (A) : C をスタックから取り出す
[ E ][F][ ] (A) : 分割する
[F][ ] (E A) : E をスタックに積む
[ ][ ] (E A) : F をソートする
[ E ] (A) : E をスタックより取り出す
・・・・・あとはスタックが空になるまで繰り返す・・・・・
図 : クイックソートでのスタックの動作
それでは、クイックソートのプログラム (1) を改良してみましょう。まずは枢軸の選び方を工夫します。区間の中からいくつかの要素を選び、その中で真ん中の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、真ん中の値を選ぶのに時間がかかってしまいます。そこで、実際には 3 つから 5 つの要素を選んで、その中で真ん中の値を持つ要素を枢軸とする場合が多いようです。
次に再帰呼び出しをループに展開します。2 つに分割した区間の長い方を自分で用意したスタックに積み、短い区間からソートしていきます。そうすると、スタックの深さは要素数を N とすると log 2 N 程度におさまります。たとえば、100 万個の要素をソートする場合でも、スタックの大きさは 20 程度あれば十分です。ひとつの区間の処理が終わったら、スタックから次の区間を取り出して処理を行います。これを図に示すと次のようになります。
最後に、要素数が少なくなったらクイックソートを打ち切ります。そして、最後に挿入ソートで仕上げます。データ数が少ない場合は、クイックソートよりも単純なソートアルゴリズムの方が高速です。また、全体をソートする場合でも、すでに大まかにソートされているので、挿入ソートでも高速にソートすることができます。
まずは枢軸を選択する関数 select-pivot を作ります。
リスト : 枢軸の選択
(defun select-pivot (buff low high)
(let ((a (aref buff low))
(b (aref buff (floor (+ low high) 2)))
(c (aref buff high)))
(when (> a b)
(psetq a b b a))
(when (> b c)
(setq b c)
(when (> a b) (setq b a)))
b))
区間 [low, high] から 3 つの要素を選びます。ここでは 先頭の位置 low、中間の位置 (low + high) / 2、最後尾の位置 high にある要素を選ぶことにしました。そして、a, b, c の中で真ん中の値を選んで返します。
ところで、枢軸の選択を工夫しても、その方法に対して最悪のデータが存在します。しかしながら、最悪の場合でも再帰呼び出しの削除とスタックの積み方の工夫により、エラーが発生することはありません。ただし、実行時間が遅くなるのは仕方がないところです。なお、参考文献 1 『Ｃ言語による最新アルゴリズム事典』によると、枢軸を乱数で選ぶ方法もあります。興味のある方は試してみてください。
それでは、クイックソート本体を作ります。次のリストを見てください。
リスト : クイックソート (2)
(defconstant qsort-limit 10)
(defun quicksort-fast (buff &aux (low 0) (high (1- (length buff))))
(let (stack)
(loop
(cond
((<= (- high low) qsort-limit)
(unless stack (return))
(setq low (first (car stack))
high (second (car stack)))
(pop stack))
(t
(let ((p (select-pivot buff low high))
(i low)
(j high))
(loop
(loop (if (<= p (aref buff i)) (return)) (incf i))
(loop (if (>= p (aref buff j)) (return)) (decf j))
(if (>= i j) (return))
(psetf (aref buff i) (aref buff j)
(aref buff j) (aref buff i))
(incf i)
(decf j))
(cond
((> (- i low) (- high j))
(push (list low (1- i)) stack)
(setq low (1+ j)))
(t
(push (list (1+ j) high) stack)
(setq high (1- i)))))))))
(insert-sort buff))
最初に、high - low の値をチェックします。QSORT-LIMIT (10) 以下になったらクイックソートを打ち切ります。スタック STACK にデータがなければ return で loop を脱出して、最後に単純挿入ソート (insert-sort) で仕上げます。スタックには区間の上限値と下限値がリストにまとめてセットされています。スタックにデータがある場合は、それを取り出して LOW と HIGH にセットし、処理を繰り返します。
区間が QSORT-LIMIT より大きい場合はクイックソートを行います。区間の分割は今までのプログラムと同じです。そして、長い方の区間をスタックにセットして、短い方の区間からクイックソートします。前半部分が長い場合は、区間 [LOW, I - 1] をスタックに積んで [J + 1, HIGH] をソートします。LOW の値を J + 1 に書き換えて処理を繰り返します。後半部分が長い場合は、[J + 1, HIGH] をスタックに積んで [LOW, i - 1] をソートします。この場合は HIGH を I - 1 に書き換えて処理を繰り返します。
山型データの実行時間は次のようになりました。
表 : 山型データの実行時間 (単位 : 秒) 個数 : 10000 : 20000 : 40000 : 80000 -----+-------+-------+-------+------- (1) : 0.236 : 1.200 : NG : NG -----+-------+-------+-------+------- (2) : 0.007 : 0.019 : 0.031 : 0.060
このように、山型データでもエラーは発生しません。改良の効果は十分にでていると思います。興味のある方はいろいろなデータで試してみてください。
あるデータの中から特定のデータを探す場合、いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching)」といいます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。
これに対し「二分探索 (binary search)」は、log2 N に比例する時間でデータを探すことができる高速なアルゴリズムです。ただし、探索するデータはあらかじめソートしておく必要があります。次の図を見てください。
[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 回程度の比較で探索を完了することができます。
それでは、ベクタから数値を二分探索するプログラムを作ってみましょう。二分探索は再帰定義を使わなくても簡単にプログラムできます。次のリストを見てください。
リスト : 二分探索
(defun binary-search (item buffer)
(do ((low 0)
(high (1- (length buffer))))
((> low high))
(let ((mid (floor (+ low high) 2)))
(cond
((= (aref buffer mid) item)
(return t))
((< (aref buffer mid) item)
(setq low (1+ mid)))
(t
(setq high (1- mid)))))))
最初に、探索する区間を示す変数 LOW と HIGH を初期化します。ベクタの大きさは length で取得し、最後の要素の位置を high にセットします。それから、探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 MID にセットします。cond で MID の位置にある要素と ITEM を比較し、等しい場合は探索成功です。return で do ループから脱出して T を返します。
ITEM が大きい場合は区間の後半を調べます。変数 LOW に MID + 1 をセットします。逆に、ITEM が小さい場合は前半を調べるため、変数 HIGH に MID - 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) T * (binary-search 40 a) NIL * (binary-search 11 a) T * (binary-search 10 a) NIL * (binary-search 99 a) T * (binary-search 100 a) NIL
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。
したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、「ハッシュ法 (hashing)」や「二分探索木 (binary search tree)」を使ってみるといいでしょう。
今回は「ハッシュ表 (hash table)」を取り上げます。ハッシュとは、高速なデータ検索アルゴリズムである「ハッシュ法 (hashing)」のことを指します。ハッシュ法はコンパイラやインタプリタなどで、予約語、関数名、変数名などの管理に使われています。また、Perl, Python, Ruby など連想配列をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。Perl や Ruby で連想配列をハッシュと呼ぶのは、アルゴリズムの名称からきているのです。
Common Lisp の場合、ハッシュ表 (hash-table) というデータ型が用意されているので、簡単にハッシュ法を利用することができます。今回は「ハッシュ表」の使い方を簡単に説明します。
ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を用意します。たとえば、ハッシュ表の大きさを n とすると、ハッシュ関数はデータを 0 から n - 1 までの整数値に変換するように作ります。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを取り扱う場合、異なるデータでも同じハッシュ値が生成されることがあります。これをハッシュ値の「衝突(collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。
ひとつは、ハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納しておく工夫が必要になります。このときによく利用されるデータ構造がリストです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されているリストの中からデータを探索します。これを「チェイン法 (chaining) 」といいます。
この方法ではハッシュ値の衝突が頻繁に発生すると、データを格納するリストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。
第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。この場合、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。この処理を空いている場所が見つかるまで繰り返します。この方法を「オープンアドレス法 (open addressing)」といいます。
この場合、データの最大数はハッシュ表の大きさに制限されます。また、ハッシュ表の空きが少なくなると、探索効率も極端に低下してしまいます。このため、ハッシュ表の空きが少なくなったら、ハッシュ表のサイズを大きくして、ハッシュ表を作り直す作業を行うのがふつうです。これを「リハッシュ (rehash)」といいます。そのあと探索効率は良くなるので、リハッシュにかけた時間のもとは十分にとれます。
Common Lisp の場合、ハッシュ表は特定のキーと特定のデータを関連付けるデータ構造です。つまり、キーのハッシュ値を計算し、ハッシュ表のその場所へデータを格納します。
それでは、ハッシュ表を操作する関数を説明します。ハッシュ表を作るには関数 make-hash-table を使います。
make-hash-table &key :test :size :rehash-size :rehash-threshold
キーワード :test にはキーを比較する関数 eq, eql, equal, equalp のどれかを指定します。省略された場合は eql が使用されます。:size はハッシュ表の初期サイズ、:rehash-size はリハッシュするときにハッシュ表を増やす割合、:rehash-threshold はリハッシュするときのしきい値を指定します。よく使われるキーワードは :test と :size です。リハッシュの処理は Lisp 処理系に任せておけばいいので、ほかのキーワードはとくに指定する必要はないでしょう。
ハッシュ表から値を求めるには関数 gethash を使います。
gethash key hash-table &optional default
gethash は hash-table から key を検索し、格納されているデータを返します。キーが見つからない場合は default を返します。default が省略された場合は NIL を返します。実際には、gethash は多値を返します。2 番目は真偽値で、キーが見つかれば T を、見つからない場合は NIL を返します。それから、ハッシュ表に値を書き込むときは setf を使います。
簡単な使用例を示しましょう。
* (setq a (make-hash-table :test #'equal))
#<HASH-TABLE :TEST EQUAL :COUNT 0 {1001BB50B3}>
* (type-of a)
HASH-TABLE
* (setf (gethash "abc" a) 100)
100
* (gethash "abc" a)
100
T
* (gethash "ABC" a)
NIL
NIL
* (setq b (make-hash-table :test #'equalp))
#<HASH-TABLE :TEST EQUALP :COUNT 0 {1001BF5B23}>
* (setf (gethash "abc" b) 100)
100
* (gethash "abc" b)
100
T
* (gethash "ABC" b)
100
T
文字列をキーにする場合、:test に equal か equalp を指定します。equal は英大小文字を区別するので、abc と ABC は異なるキーと判断されます。したがって、abc の値は 100 ですが、ABC の値は NIL (キーが見つからない) となります。ところが、equalp は英大小文字を区別しません。abc と ABC は同じキーと判断されるため、abc に 100 をセットすれば、ABC の値も 100 となります。
ハッシュ表からデータを削除するには関数 remhash を使い、ハッシュ表をクリアするには関数 clrhash を使います。
remhash key hash-table clrhash hash-table
remhash は hash-table の中の key に対応するデータを削除します。データがあれば真を、なければ偽を返します。clrhash は hash-table からすべてのデータを取り除き、hash-table を返します。
ハッシュ表に格納されたデータ数を求めるには関数 hash-table-count を使います。
hash-table-count hash-table
ハッシュ表が生成された場合や clrhash でクリアされた場合、データの個数は 0 になります。
ハッシュ表にもマップ関数が用意されています。
maphash function hash-table
関数 function には 2 つのデータ、キーとその値が渡されます。maphash はふつうのマップ関数とは異なり、function の評価結果をリストにまとめて返すということはしません。NIL を返すので注意してください。簡単な例を示しましょう。
* (setq a (make-hash-table :test #'equalp))
#<HASH-TABLE :TEST EQUALP :COUNT 0 {1001C0D0D3}>
* (setf (gethash "abc" a) 10)
10
* (setf (gethash "def" a) 20)
20
* (setf (gethash "ghi" a) 30)
30
* (maphash #'(lambda (key val) (format t "key = ~a, val = ~a~%" key val)) a)
key = abc, val = 10
key = def, val = 20
key = ghi, val = 30
NIL
キーの順番ですが、ソートされて出力されるとか、データをセットした順番で出力されるというわけではありません。キーの順番は処理系に依存しますので、ご注意くださいませ。
もうひとつ with-hash-table-iterator というマクロが用意されています。
with-hash-table-iterator (iter hash-table) form ...
with-hash-table-iterator は hash-table からキーと値を取り出す関数 (イテレータ) を生成します。関数名は iter で指定します。イテレータは 3 つの値 (真偽値、キー、値) を返します。キーと値の取得に成功したならば最初の値は真に、そうでなければ偽になります。簡単な使用例を示します。
* (with-hash-table-iterator (iter a)
(loop
(multiple-value-bind (p k v) (iter)
(if (not p) (return))
(format t "~a ~a~%" k v))))
abc 10
def 20
ghi 30
NIL
それでは簡単な例題として、3 次元空間の異なる点 (x y z) を n 個作る関数を作ります。要素 x, y, z は 0 から 99 までの整数値とし、乱数で生成することにします。生成する点の個数が少なければ、ハッシュ表を使わなくても線形探索で十分です。プログラムは次のようになります。
リスト : n 個の異なる点を作る
;;; 点 (x y z) を作る
(defun make-point ()
(list (random 100) (random 100) (random 100)))
;;; 異なる点を N 個作る
(defun make-data (n &optional zs)
(if (zerop n)
zs
(let ((xs (make-point)))
(if (member xs zs :test #'equal)
(make-data n zs)
(make-data (1- n) (cons xs zs))))))
関数 make-data は関数 make-point で点をひとつ生成し、それが今まで生成した点と異なることを member でチェックします。点はリストで表されているので、member のキーワード :test には #'equal を指定します。デフォルトの eql では動作しないことに注意してください。
member は線形探索なので、点の個数が増えると時間がかかるようになります。実際に 10000, 20000, 40000 個の点を作ったときの実行時間を示します。
| 10000 | 20000 | 40000 | |
|---|---|---|---|
| 線形探索 | 0.61 | 2.42 | 9.70 |
点の個数が増えると実行時間が大幅に増加することがわかります。それでは線形探索の代わりにハッシュ法を使ってみましょう。プログラムは次のようになります。
リスト : n 個の異なる点を作る（ハッシュ法）
(defun make-data-fast (n &optional (zs (make-hash-table :test #'equal)))
(if (zerop n)
zs
(let ((xs (make-point)))
(if (gethash xs zs)
(make-data-fast n zs)
(progn
(setf (gethash xs zs) t)
(make-data-fast (1- n) zs))))))
関数 make-data-fast は生成したデータのチェックにハッシュ表を使います。ハッシュ表はオプショナル引数 ZS に用意します。このとき、:test に #'equal を指定することをお忘れなく。そして、make-point でデータを生成したら、gethash で同一データがないかチェックします。gethash の返り値が偽ならば XS は新しいデータです。ハッシュ表 ZS に XS を追加して make-data-fast を再帰呼び出しします。
これでプログラムは完成です。実行時間は次のようになりました。
| 10000 | 20000 | 40000 | |
|---|---|---|---|
| 線形探索 | 0.61 | 2.42 | 9.70 |
| ハッシュ法 | 0.007 | 0.014 | 0.026 |
圧倒的にハッシュ表の方が速いですね。