今回は 4 つの数字を当てるゲームを作りましょう。これは「マスターマインド」とか「ヒット・アンド・ブロー」と呼ばれているゲームです。
コンピュータは 0 から 9 までの中から重複しないように数字を 4 つ選びます。私たちは数字だけではなく、その位置も当てなくてはいけません。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。つまり、bulls が 4 になると正解というわけです。
言葉で説明するとわかりにくいので、ゲームの進行状況を見てみましょう。
(6 2 8 1)
---------------------------------
1. (0 1 2 3) : bulls 0 : cows 2
2. (1 0 4 5) : bulls 0 : cows 1
3. (2 3 5 6) : bulls 0 : cows 2
4. (3 2 7 4) : bulls 1 : cows 0
5. (3 6 0 8) : bulls 0 : cows 2
6. (6 2 8 1) : bulls 4 : cows 0 ＊＊！正解！＊＊
図 : マスターマインドの動作例
4 つの数字はリストに格納することにします。コンピュータが選んだ数字は (6 2 8 1) です。プレーヤーは、最初に (0 1 2 3) を入力しました。0 と 3 は (6 2 8 1) に含まれていませんね。1 と 2 は (6 2 8 1) の中にあるのですが、位置が異なっているので、cows が 2 となります。この場合の bulls は 0 です。
あとは bulls が 4 になるように数字を選んで入力していきます。4 番目の入力では、2 の位置が合っているので bulls は 1 となります。この例では 6 回で正解となりました。
それでは、順番に処理内容を考えていきましょう。まず、コンピュータが数字を決めないことには、ゲームを始めることができません。コンピュータで適当な数字を選ぶためには、「乱数 (random numbers)」という方法を使います。
私たちが適当な数字を決める場合、たとえばサイコロを使えば、1 から 6 までの数字を簡単に決めることができます。サイコロを振って出た目を記録したら、次のようになったとしましょう。
5, 2, 1, 2, 6, 3, 4, 3, 1, 5, .....
サイコロの目は、イカサマをしないかぎり、出る確率が 1/6 で規則性はまったくありません。いま 2 が出たから次は 1 が出るとか、3, 4 と続いたから次は 5 が出るといったように、前に出た数字から次に出る数字を予測することはできないのです。このように、でたらめに並んだ数列を「乱数列 (random sequence)」といい、乱数列の中のひとつひとつつの数字を「乱数 (random numbers)」といいます。
コンピュータは、決められた手順 (プログラム) を高速に実行することは得意ですが、まったくでたらめな数を作れといわれると、とたんに困ってしまいます。そこで、何かしらの数式をプログラムして、それを実行することで乱数を発生させます。厳密にいえば乱数ではありませんが、それを乱数としてみなして使うことにするのです。このような乱数を「疑似乱数 (pseudo-random numbers)」といいます。現在では、ほとんどのコンピュータが疑似乱数を使っています。
Common Lisp には、乱数を発生させる関数 random が用意されています。
random n &optional state
引数 n は正の整数または浮動小数点数です。random は 0 以上 n 未満の n と同じ型の数を返します。
それでは、乱数を 5 個作ってみましょう。
* (dotimes (x 5) (print (random 100000))) 41858 98020 3273 25824 17546 NIL * (dotimes (x 5) (print (random 1.0))) 0.8319478 0.9061605 0.20890021 0.68792355 0.13638473 NIL * (dotimes (x 5) (print (random 1d0))) 0.5842392115421822d0 0.2585348121546005d0 0.19923622591180323d0 0.39123123326359543d0 0.5524594407331214d0 NIL
SBCL の場合、起動したあと最初に random を評価すると、必ずこの乱数列が発生します。一般に、乱数を発生させるためには「種 (seed, シード)」となる数値が必要になります。Common Lisp ではシードを random-state 型のデータとして扱います。そして、random はスペシャル変数 *RANDOM-STATE* に格納されている値を使って乱数列を発生させます。SBCL を起動すると *RANDOM-STATE* は同じ値に初期化されるため、同じ乱数列が発生するというわけです。
違う乱数列を発生させるためには、新しい random-state 型のデータ state を *RADOM-STATE* にセットするか、state を random の引数として渡します。新しい state を生成するには関数 make-random-state を使います。
make-random-state &optional state
引数 state を省略するか NIL の場合、make-random-state は *RANDOM-STATE* のコピーを返します。state が random-state 型のデータであれば、そのコピーを返します。そして、state が T の場合は、何らかの方法を用いてランダムに初期化された random-state 型のデータを返します。それでは実際に試してみましょう。
* (setq *random-state* (make-random-state t))
#S(RANDOM-STATE :STATE #.(MAKE-ARRAY 627 :ELEMENT-TYPE '(UNSIGNED-BYTE 32)
:INITIAL-CONTENTS
'(0 2567483615 624 2147483648 ... 省略 ...)))
* (dotimes (x 5) (print (random 100000)))
39409
46615
18270
72726
91492
NIL
* (dotimes (x 5) (print (random 1.0)))
0.46975803
0.7336695
0.30920708
0.61585224
0.94505703
NIL
* (dotimes (x 5) (print (random 1d0)))
0.5842840759855281d0
0.14658467112831142d0
0.3921419705988862d0
0.8429755650054664d0
0.38248834150473043d0
NIL
SBCL の場合、random-state 型のデータは「構造体」で定義されています。このように、*RANDOM-STATE* に新しい値をセットすることで、異なる乱数列を発生させることができます。
それではプログラムを作りましょう。まず、コンピュータが数字を 4 つ選ばないことには、ゲームを始めることができません。0 - 9 の数字を生成する処理は、乱数を使えば簡単に実現できます。今回はこの数字をリストに格納することにします。リストは空リストに初期化しておきます。数字をリストに追加する前に、同じ数字があるかチェックします。もし、同じ数字があればリストには追加しません。違う数字であればリストに追加します。あとは数字が 4 つそろうまで、この処理を繰り返します。
プログラムは次のようになります。
リスト : 4 つの数字を決める
(defun make-answer ()
(do ((ans nil)
(n (random 10) (random 10)))
((= (length ans) 4) ans)
(unless (member n ans)
(push n ans))))
関数名は make-answer としました。変数 ANS はリストです。ここに選んだ数字を格納します。変数 N は乱数で生成した数字をセットします。(length ans) が 4 になったとき、do ループを終了して ANS を返します。そうでなければ、member で N が ANS にあるかチェックします。同じ数字がなければ push で N を ANS に追加します。
それでは実際に試してみましょう。
* (make-answer) (1 5 9 6) * (make-answer) (7 0 4 5) * (make-answer) (7 3 1 9) * (make-answer) (7 1 9 8)
次は、私たちがコード (4 つの数字) を入力する処理を作りましょう。今回はプログラムを簡単にするため、コードはリストで入力することにします。次のリストを見てください。
リスト : 数字を入力する
;;; 入力コードのチェック
(defun check-input-code (code)
(and (consp code)
(= (length code) (length (remove-duplicates code)) 4)
(every (lambda (x) (and (integerp x) (<= 0 x 9))) code)))
;;; コードの入力
(defun input-code ()
(loop
(princ ">>> ")
(finish-output)
(let ((code (read)))
(if (check-input-code code)
(return code))
(format t "異なる 4 つの数字 (0 - 9) を入力してください~%"))))
関数 input-code はコードの入力処理を行います。最初に、princ でプロンプト >>> を表示します。ところが、このままでは画面にプロンプトが表示されません。一般に、ストリームはバッファを持っていて、データは一時的にバッファに格納されます。バッファが満杯になったとき、バッファ内のデータをすべて出力します。この動作を「バッファリング」といいます。
標準出力の場合、バッファが満杯になったときだけではなく、改行文字が書き込まれたときにもバッファ内のデータが出力されます。この動作を「行バッファリング」といいます。関数 finish-output はバッファリングされているデータを強制的に出力する働きをします。これでプロンプトが画面に表示されます。
次に read でコードを S 式として読み込み、変数 CODE にセットします。入力された CODE のチェックは関数 check-input-code で行います。正しいコードであれば return で CODE を返します。そうでなければメッセージを表示して入力処理を繰り返します。
関数 check-input-code は簡単です。まず consp で引数 CODE がリストであることを確認します。次に CODE の長さが 4 であることと、重複要素がないことを確認します。これは関数 remove-duplicates で重複要素を削除したあと、その長さが 4 であれば重複要素が無いことがわかります。最後に、各要素が整数で 0 以上 9 以下であることを確認します。これは列関数 every を使うと簡単です。
some pred sequence &rest more-sequence every pred sequence &rest more-sequence
関数 some は引数 sequence の要素に述語 pred を適用し、その値が真であればただちに真を返します。すべての要素が偽と判定されれば NIL を返します。関数 every は偽と判定された要素があれば、すぐに NIL を返します。すべての要素が真と判定されれば真を返します。
簡単な使用例を示しましょう。
* (some #'evenp '(1 3 5 8 9)) T * (some #'evenp '(1 3 5 7 9)) NIL * (every #'oddp '(1 3 5 7 9)) T * (every #'oddp '(1 3 4 7 9)) NIL
それでは実際に input-code を動かしてみましょう。
* (input-code) >>> 0 異なる 4 つの数字 (0 - 9) を入力してください >>> (a b c d) 異なる 4 つの数字 (0 - 9) を入力してください >>> (1 2 3 4 5) 異なる 4 つの数字 (0 - 9) を入力してください >>> (1 2 3) 異なる 4 つの数字 (0 - 9) を入力してください >>> (1 2 3 10) 異なる 4 つの数字 (0 - 9) を入力してください >>> (1 2 3 1) 異なる 4 つの数字 (0 - 9) を入力してください >>> (1 2 3 4) (1 2 3 4)
次は bulls と cows を数える処理を作ります。プログラムは次のようになります。
リスト : bulls と cows を求める
;;; bulls をカウントする
(defun count-bulls (answer code)
(count t (mapcar #'= answer code)))
;;; 同じ数字をカウントする
(defun count-same-number (answer code)
(let ((c 0))
(dolist (x code c)
(if (member x answer) (incf c)))))
bulls を数える関数 count-bulls は簡単です。mapcar で ANSWER と CODE を述語 = で比較し、T の個数を count で求めるだけです。
次に cows を数える処理ですが、いきなり cows を数えようとすると難しくなるので、2 つのリストに共通の数字を数える処理を作ります。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。
関数名は count-same-number としました。局所変数 c を 0 に初期化します。これがカウンタになります。dolist で CODE から数字 X を取り出し、member で X が ANSWER にあるかチェックします。そうであれば incf で C の値を +1 します。dolist が終了したら C を返します。
それでは実行してみましょう。
* (count-bulls '(1 2 3 4) '(1 2 3 4)) 4 * (count-bulls '(1 2 3 4) '(4 3 2 1)) 0 * (count-bulls '(1 2 3 4) '(4 2 3 1)) 2 * (count-same-number '(1 2 3 4) '(4 3 2 1)) 4 * (count-same-number '(1 2 3 4) '(5 6 7 8)) 0
必要な関数がそろったので、ゲーム本体を作りましょう。
リスト : ゲーム本体
(defun mastermind ()
(let ((ans (make-answer)))
(dotimes (x 10 (format t "残念！ 正解は ~a でした" ans))
(let* ((code (input-code))
(bulls (count-bulls ans code))
(cows (- (count-same-number ans code) bulls)))
(format t "~2d: ~a, bulls = ~d, cows = ~d~%" (1+ x) code bulls cows)
(when (= bulls 4)
(format t "おめでとう！!~%")
(return))))))
最初に make-answer で正解のコードを作成し、変数 ANS にセットします。次に dotimes で 10 回だけ処理を繰り返します。10 回以内で当てられなかった場合はゲーム終了とします。format でメッセージと正解を表示します。
ループの中では、input-code でコードを読み取り、それを変数 CODE にセットします。次に count-bulls と count-same-number を使って bulls と cows を求めます。これらのデータは format で表示します。BULLS が 4 であれば正解です。format でメッセージを表示したあと return でループを脱出します。
プログラムはこれで完成です。それでは実行してみましょう。
* (progn (setq *random-state* (make-random-state t)) nil) NIL * (mastermind) >>> (0 1 2 3) 1: (0 1 2 3), bulls = 0, cows = 0 >>> (4 5 6 7) 2: (4 5 6 7), bulls = 1, cows = 2 >>> (4 6 7 8) 3: (4 6 7 8), bulls = 1, cows = 2 >>> (4 7 6 9) 4: (4 7 6 9), bulls = 2, cows = 2 >>> (4 7 9 6) 5: (4 7 9 6), bulls = 4, cows = 0 おめでとう！! NIL
5 回で当てることができました。今回は 4 つの数字ですが、簡単だと思ったら 5 つに増やしてみる、逆に難しいと思ったら 3 つに減らしてみる、などいろいろ改造してみてください。
ソートはある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。Lisp はリストにデータを格納するので、リストの要素をソートする関数があると便利です。Common Lisp には列関数 sort が用意されていますが、私達でも簡単にソートプログラムを作ることができます。最初に、簡単な「挿入ソート」を作ってみましょう。
挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト (2 4 6) に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
ソートするリストは、cdr で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。データを比較する述語は引数として渡せばいいでしょう。プログラムは次のようになります。
リスト : 挿入ソート
;;; データをひとつリストに挿入
(defun insert-element (x xs pred)
(cond
((null xs) (list x))
((funcall pred x (car xs)) (cons x xs))
(t (cons (car xs)
(insert-element x (cdr xs) pred)))))
;;; 挿入ソート
(defun insert-sort (xs pred)
(if (null xs)
nil
(insert-element (car xs) (insert-sort (cdr xs) pred) pred)))
リストにデータをひとつ挿入する関数が insert-element です。再帰呼び出しでリスト XS をたどり、データ X を挿入する位置を探します。述語 PRED の返り値が真であれば、その位置にデータを挿入します。関数 insert-sort は引数のリスト XS を再帰呼び出しで分解します。空リストになると再帰呼び出しが停止します。そして、car で取り出した要素を insert-element でソート済みのリストに挿入します。
それでは実行してみましょう。
* (insert-sort '(5 6 4 7 3 8 2 0 1 9) #'<) (0 1 2 3 4 5 6 7 8 9) * (insert-sort '(5 6 4 7 3 8 2 0 1 9) #'>) (9 8 7 6 5 4 3 2 1 0) * (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)
要素がリストの場合でも、ラムダ式を使うと簡単にソートできます。
* (insert-sort '((5 6) (4 7) (3 8) (2 0) (1 9)) (lambda (x y) (< (first x) (first y)))) ((1 9) (2 0) (3 8) (4 7) (5 6))
先頭の要素を基準にソートしています。first を second に変更すれば、第 2 要素を基準にソートすることができます。
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート」は高速なソートアルゴリズムとして有名です。もちろん、Lisp でもクイックソートをプログラムすることができます。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストはランダムアクセスができないので、適当な要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
5 3 7 6 9 8 1 2 4
5 を枢軸に分割
(3 1 2 4) 5 (7 6 9 8)
3を枢軸に分割 7を枢軸に分割
(1 2) 3 (4) | 5 | (6) 7 (9 8)
・・・分割を繰り返していく・・・
図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを append で結合すればいいわけです。プログラムは次のようになります。
リスト : クイックソート
;;; リストの分割
(defun partition (p xs pred)
(let (ys zs)
(dolist (x xs (list ys zs))
(if (funcall pred x p) (push x ys) (push x zs)))))
;;; クイックソート
(defun quick-sort (xs pred)
(if (null xs)
nil
(let ((ys (partition (car xs) (cdr xs) pred)))
(append (quick-sort (first ys) pred)
(list (car xs))
(quick-sort (second ys) pred)))))
関数 partition は引数 P とリスト XS の要素を述語 PRED で比較し、真偽で 2 つのリストに分けて返します。たとえば、変数 P に枢軸を渡して PRED に #'< を渡すと、変数 YS のリストには枢軸未満の要素、ZS には枢軸以上の要素が格納されます。
関数 quick-sort は partition を呼び出して、リスト (cdr xs) を二分割します。このとき (car xs) が枢軸となります。あとは、quick-sort を再帰呼び出しして、その結果を append で結合します。間に枢軸 (car xs) を入れることをお忘れなく。
それでは実行してみましょう。
* (quick-sort '(5 6 4 7 3 8 2 0 1 9) #'<) (0 1 2 3 4 5 6 7 8 9) * (quick-sort '(5 6 4 7 3 8 2 0 1 9) #'>) (9 8 7 6 5 4 3 2 1 0) * (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) * (quick-sort '((5 6) (4 7) (3 8) (2 0) (1 9)) (lambda (x y) (< (first x) (first y)))) ((1 9) (2 0) (3 8) (4 7) (5 6))
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するまで劣化します。つまり、挿入ソートと同じくらい遅くなってしまうのです。たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。次の図を見てください。
9 8 7 6 5 4 3 2 1
9 を枢軸に分割
(8 7 6 5 4 3 2 1) 9 ()
8を枢軸に分割
(7 6 5 4 3 2 1) 8 () | 9 | ()
・・・分割を繰り返していく・・・
図 : クイックソート (最悪の場合)
クイックソートは、ソートするデータの中で中間の値を枢軸に選ぶと、データをほぼ半分に分割することができます。この場合がいちばん効率が良いのですが、上図のようにデータの最大値を枢軸として選ぶと、その要素と残りの要素にしか分割されません。これが最悪の場合で、分割のたびに最大値もしくは最小値を枢軸に選ぶと、実行時間は要素数の 2 乗に比例する、つまり遅いソートと同じ結果になるのです。
このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。
ただし、この改良はベクタであれば簡単に実現できるのですが、リストには不向きであることに注意してください。たとえば、データが 1000 個ある場合、ベクタであれば 0, 500, 999 番目のデータを取り出すのは簡単ですが、リストではデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。クイックソートは、リストよりもベクタに向いているソートアルゴリズムといえます。
次は、クイックソートと同様に高速なアルゴリズムであるマージソートを説明します。「マージ (併合)」とは、複数のソート済み列をひとつのソート済みの列にまとめる操作です。最初にマージから説明します。次の図を見てください。
┌─ (1 3 5) ; リスト a
() ←┤
└─ (2 4 6) ; リスト b
小さい方をセットする
┌─ (3 5) ; リスト a
(1) ←┘
(2 4 6) ; リスト b
1 をセットする
(3 5) ; リスト a
(1 2) ←┐
└─ (4 6) ; リスト b
2 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
2 つのリスト a と b があります。これらのリストは昇順でソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
Common Lisp には列関数 merge が用意されていますが、実際にプログラムを作ってみましょう。次のリストを見てください。
リスト : リストのマージ
(defun merge-list (xs ys pred)
(cond
((null xs) ys)
((null ys) xs)
((funcall pred (car xs) (car ys))
(cons (car xs) (merge-list (cdr xs) ys pred)))
(t (cons (car ys) (merge-list xs (cdr ys) pred)))))
関数 merge-list の引数 XS と YS がマージするリスト、PRED がデータを比較する述語です。最初に、述語 null でリスト XS と YS が空リストかチェックします。そうであれば、もう一方のリストを返します。これが再帰呼び出しの停止条件になります。
XS と YS が空リストでなければ、先頭要素を述語 PRED で比較します。返り値が真であれば XS の先頭要素を、そうでなければ YS の先頭要素を merge-list が返すリストに追加します。merge-list を再帰呼び出しするときは、追加する先頭要素をリストから取り除くことに注意してください。これでリストをマージすることができます。
簡単な実行例を示しましょう。
* (merge-list '(1 3 5 7 9) '(0 2 4 6 8) #'<) (0 1 2 3 4 5 6 7 8 9) * (merge-list '(1 3 5 7 9) '(0 2 4 6) #'<) (0 1 2 3 4 5 6 7 9) * (merge-list '(1 3 5 7) '(0 2 4 6 8) #'<) (0 1 2 3 4 5 6 7 8)
マージソートは、このマージを使ってデータをソートします。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。
それではプログラムを作りましょう。マージソートの場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単にプログラムを作ることができます。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。
リスト : マージソート
(defun merge-sort (xs n pred)
(cond
((null xs) nil) ; 新しいリストを返す
((= n 1) (list (car xs)))
(t (let ((m (floor n 2)))
;; リストを二分割し再帰呼び出しの結果をマージする
(merge-list (merge-sort xs m pred)
(merge-sort (nthcdr m xs) (- n m) pred)
pred)))))
関数 merge-sort の引数 XS がソートするリスト、N がリストの長さ、PRED がデータを比較する述語でます。merge-list はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。
引数 xs
｜
｜←── 長さn ──→｜
（１ ２ ３ ４ ５ ６ ７ ８）
｜←n/2→｜ ｜←n/2→｜
｜ ｜
引数 xs 引数 ys 再帰呼び出し
図 : リストの分割
merge-sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は xs と n / 2 で表し、後半部分を ys と n / 2 で表します。ys は cdr を n / 2 回繰り返せば求めることができます。これは nthcdr を使えば簡単ですね。あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。そして、merge-sort の返り値を merge-list でマージすればいいわけです。
それでは実行してみましょう。
* (merge-sort '(5 6 4 7 3 8 2 9 1 0) 10 #'<) (0 1 2 3 4 5 6 7 8 9) * (merge-sort '(5 6 4 7 3 8 2 9 1 0) 10 #'>) (9 8 7 6 5 4 3 2 1 0) * (merge-sort '(9 8 7 6 5 4 3 2 1 0) 10 #'<) (0 1 2 3 4 5 6 7 8 9) * (merge-sort '(0 1 2 3 4 5 6 7 8 9) 10 #'<) (0 1 2 3 4 5 6 7 8 9)
マージソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。ただし、マージソートは単純にリストを二分割するため、クイックソートと違いデータによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれるわけです。
それでは、挿入ソート、クイックソート、マージソートの実行時間を比較してみましょう。データは整数値 5000 個とし、ランダム、昇順 (ソート済み)、降順 (逆順のこと) に要素を並べたリストを昇順にソートします。処理が速すぎる場合は dotimes で 1000 回ほど繰り返して時間を計測しています。
| insert | quick | merge | |
| 乱数 | 161.4 | 1.89 | 1.94 |
| 昇順 | 0.18 | 1507.0 | 0.93 |
| 降順 | 319.8 | 1712.9 | 1.215 |
クイックソートは乱数データではいちばん速いのですが、昇順または降順のデータでは極端に遅くなります。今回のプログラムでは、これらのデータが最悪の結果になります。これがクイックソートの弱点です。これに対し、マージソートはデータの種類にかかわらず高速にソートできることがわかります。挿入ソートはとても遅いのですが、ソート済みのデータだけはとても速いですね。これが挿入ソートの特徴です。もしも、リストがほとんどソートされている状態であれば、挿入ソートでも高速にソートすることができます。
また、要素数が少ない場合は単純なアルゴリズムである挿入ソートの方が速いです。クイックソートやマージソートでも、要素数が少なくなったら挿入ソートに切り換えると少しだけ速くなります。切り換えるタイミングですが、使用するプログラミング言語や実行環境によって変わります。興味のある方はいろいろ試してみてください。