ベクタのソートと二分探索
今回はベクタの「ソート (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 は、スタックがオーバーフローしたことを示します。データ数が少ない場合、スタックオーバーフローは発生しませんが、実行時間はとても遅くなります。ほかのデータでは、とても高速にソートすることができました。やっぱり、クイックソートは速いですね。
●クイックソートの改良
それでは、クイックソートのプログラム (1) を改良してみましょう。まずは枢軸の選び方を工夫します。区間の中からいくつかの要素を選び、その中で真ん中の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、真ん中の値を選ぶのに時間がかかってしまいます。そこで、実際には 3 つから 5 つの要素を選んで、その中で真ん中の値を持つ要素を枢軸とする場合が多いようです。
次に再帰呼び出しをループに展開します。2 つに分割した区間の長い方を自分で用意したスタックに積み、短い区間からソートしていきます。そうすると、スタックの深さは要素数を N とすると log 2 N 程度におさまります。たとえば、100 万個の要素をソートする場合でも、スタックの大きさは 20 程度あれば十分です。ひとつの区間の処理が終わったら、スタックから次の区間を取り出して処理を行います。これを図に示すと次のようになります。
スタック
[ 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 をスタックより取り出す
・・・・・あとはスタックが空になるまで繰り返す・・・・・
図 : クイックソートでのスタックの動作
最後に、要素数が少なくなったらクイックソートを打ち切ります。そして、最後に挿入ソートで仕上げます。データ数が少ない場合は、クイックソートよりも単純なソートアルゴリズムの方が高速です。また、全体をソートする場合でも、すでに大まかにソートされているので、挿入ソートでも高速にソートすることができます。
まずは枢軸を選択する関数 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 に書き換えて処理を繰り返します。
1. 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
●実行時間の計測 (2)
山型データの実行時間は次のようになりました。
表 : 山型データの実行時間 (単位 : 秒) 個数 : 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 に比例する時間でデータを探すことができる高速なアルゴリズムです。ただし、探索するデータはあらかじめソートしておく必要があります。次の図を見てください。
図 : 二分探索
二分探索はベクタ向きのアルゴリズムで、探索する区間を半分に分けて調べます。キーが 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)」を使ってみるといいでしょう。