xyzzy Lisp Programming

列関数

Common Lisp はリスト (list)、文字列 (string)、ベクタ (vector) を、列 (sequence) として統一して扱うことができます。

列型データを操作する関数を列関数と呼びます。列関数には有用な関数が多数用意されています。

●単純な列関数

まずは単純な列関数を説明します。表 1 を見てください。

列はベクタと同様に 0 から数えます。elt で指定する index の範囲は、列の長さを len とすると 0 から len - 1 までとなります。subseq の start と end はコピーする範囲を指定します。end を省略すると列の最後尾が範囲となります。start 位置の要素はコピー範囲に含まれますが、end 位置の要素は範囲外になることに注意してください。次の図を見てください。

1 番目の要素 b は範囲内ですが 5 番目の要素 f は範囲外なので、コピーされたリストに f は含まれません。

関数 make-sequence は type で指定した列型データを作成します。キーワード :initial-element を指定すると、列はその値で初期化されます。

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

(setq a '(10 11 12 13 14 15)) => (10 11 12 13 14 15)

(elt a 0) => 10

(subseq a 1 4) => (11 12 13)

(copy-seq a) => (10 11 12 13 14 15)

(length a) => 6

(reverse a) => (15 14 13 12 11 10)

(make-sequence 'list 10 :initial-element 0)
=> (0 0 0 0 0 0 0 0 0 0)

●文字

文字列から取り出した要素は 文字 (character) として扱われます。Common Lisp には文字型データが用意されていて、#\ に続けて文字自身を書いて表します。xyzzy Lisp は日本語を 1 文字として扱うことができます。簡単な例を示しましょう。

(setq a "abcdeあいうえお") => "abcdeあいうえお"

(elt a 0) => #\a
(elt a 5) => #\あ

(length a) => 10

(reverse a) => "おえういあedcba"

(make-sequence 'string 10 :initial-element #\a)
=> "aaaaaaaaaa"

(make-sequence 'string 10 :initial-element #\あ)
=> "ああああああああああ"

文字列から文字を取り出すには、elt のほかに関数 char を使うことができます。

char string index

(char "あいうえお" 3) => #\え

char の引数 string は文字列でなければいけません。

●列の探索

次に、列を探索する関数を説明します。表 2 を見てください。

名前の最後に -if, -if-not がつく関数は述語 predicate を受け取る高階関数です。それから、単純な列関数以外では、表 3 に示すキーワードを使用することができます。

もっともよく使われるキーワードは :start と :end です。これは subseq の start, end と同様に部分列を指定します。簡単な例を示しましょう。

(setq a '(10 11 12 13 14 15 16 17 18 19))
=> (10 11 12 13 14 15 16 17 18 19)

(find-if #'oddp a :start 2) => 13

(position-if #'oddp a :start 4) => 5

(count-if #'oddp a :start 3 :end 7) => 2

find-if の例では、2 番目から奇数を探すので 11 ではなく 13 を返します。position-if では、4 番目から奇数を探すので 15 の位置 5 を返します。count-if では部分列 (13 14 15 16) の奇数をカウントするので 2 を返します。

:test, :test-not は述語を指定します。このキーワードは、-if, -if-not がついている列関数で使うことはできません。-if, -if-not 以外の関数では、デフォルトで要素の比較に述語 eql を使います。たとえば、文字列を格納しているリストからデータを探す場合、eql では探すことができません。次の例を見てください。

(find "def" '("abc" "def" "ghi")) => nil

(find "def" '("abc" "def" "ghi") :test #'equal) => "def"

この場合、:test に equal を指定することで文字列を検索することができます。:test-not は :test の逆で、指定した述語が偽となる要素を探します。

列に格納されたデータがリストの場合、その中の要素をキーにして探索できると便利です。この場合はキーワード :key を使います。次の例を見てください。

(find 'b '((a . 1) (b . 2) (c . 3))) => nil

(find 'b '((a . 1) (b . 2) (c . 3)) :key #'car) => (b . 2)

:key を指定しないと b と要素 (リスト) を eql で比較することになるので、データを見つけることができません。:key に car を指定することで、要素に car を適用した結果と b を比較することができるので、(b . 2) を見つけることができます。:from-end に t を指定すると、列の最後尾から検索を開始します。:count は列を修正する関数で説明します。

●列の修正

次は列を修正する関数を説明します。表 4 を見てください。

remove と substitute は引数を変更しませんが、fill は引数 sequence を破壊的に修正します。このほかに、引数を破壊的に修正する関数 delete と nsubstitute があります。簡単な例を示しましょう。

(setq a '(10 11 12 13 14 15 16 17 18 19))
=> (10 11 12 13 14 15 16 17 18 19)

(remove-if #'oddp a) => (10 12 14 16 18)

(remove-if #'oddp a :start 2 :end 8) => (10 11 12 14 16 18 19)

(substitute-if 99 #'oddp a) => (10 99 12 99 14 99 16 99 18 99)

(substitute-if 99 #'oddp a :start 3 :end 7)
=> (10 11 12 99 14 99 16 17 18 19)

(fill a 99 :start 3 :end 7) => (10 11 12 99 99 99 99 17 18 19)

a => (10 11 12 99 99 99 99 17 18 19)

キーワード :count は、処理する要素の個数を制限します。たとえば、remove であれば item と等しい要素を列からすべて削除しますが、:count で個数が指定されていると、それ以上の削除は行いません。次の例を見てください。

(remove 'a '(a b c a b c a b c)) => (b c b c b c)

(remove 'a '(a b c a b c a b c) :count 2) => (b c b c a b c)

(remove 'a '(a b c a b c a b c) :count 2 :from-end t)
=> (a b c b c b c)

このように、:count に 2 を指定すれば、a は 2 つしか削除されません。:from-end を設定すれば、後ろから 2 つ a を削除します。また、:test-not を指定することで、item と等しくないデータを削除する、つまり、item と等しいデータを取り出すこともできます。

(remove 'b '((a . 1) (b . 2) (c . 3) (b . 4)) :test-not #'eql :key #'car)
=> ((b . 2) (b . 4))

remove-duplicates は sequence の要素を順番に比較し、一致する要素が 2 つあれば sequence の前にある要素を削除します。等しい要素が複数個ある場合、結果として一番最後の要素だけが 1 つ残ります。:form-end が真の場合、sequence の後ろにある要素が削除されるので、一番前の要素だけが 1 つ残ります。このほかに、引数を破壊的に修正する delete-duplicates があります。簡単な使用例を示します。

(remove-duplicates '(a b c b d d d e))
=> (a c b d e)
(remove-duplicates '(a b c b d d d e) :from-end t)
=> (a b c d e)
(remove-duplicates '("abc" "def" "abc" "ghi") :test #'equal)
=> ("def" "abc" "ghi")
(remove-duplicates '("abc" "def" "abc" "ghi") :test #'equal :from-end t)
=> ("abc" "def" "ghi")

●マッピング

マップ関数 mapcar はリストにしか適用できませんが、Common Lisp には列型データに適用できるマップ関数が用意されています。

関数 map は、引数の列の要素に関数 func を適用し、その結果を要素とする列型データを返します。返り値のデータ型は result-type で指定します。関数 map-into は、map と同様に引数の列の要素に関数 func を適用しますが、その結果を列 result-seq に代入します。result-seq の内容は書き換えられることに注意してください。

それから、map-into の result-seq には文字列を指定できません。リストかベクタだけなので注意してください。簡単な例を示します。

(map 'list #'+ '(1 2 3) '(10 20 30 40)) => (11 22 33)

(map 'vector #'* '(10 20 30) '(1 2 3)) => #(10 40 90)

(setq a #(10 20 30 40)) => #(10 20 30 40)

(map-into a #'+ '(1 2 3) '(4 5 6)) => #(5 7 9 40)
a => #(5 7 9 40)

●列の連結

複数の列を連結するには関数 concatenate を使います。

concatenate は複数の列を連結し、結果を result-type で指定したデータ型で返します。concatenate の場合、ふつう list, string, vector のどれかを指定します。簡単な使用例を示しましょう。

(concatenate 'list '(a b c) '(d e f g)) => (a b c d e f g)

(concatenate 'vector '(a b c) '(d e f g)) => #(a b c d e f g)

(concatenate 'string '(#\a #\b #\c) '(#\d #\e #\f #\g)) => "abcdefg"

リストやベクタを文字列に変換する場合、列の要素は文字でなければいけません。

●縮約 (2005/04/17 追加)

関数 reduce は 2 つの引数を取る関数 function と sequence を引数に取ります。

reduce function sequence

reduce は sequence の各要素に対して関数 function (F) を次のように適用します。

(A1 A2 A3 ... An-1 An) = reduce F => (F (F ... (F (F A1 A2) A3) ...) An-1) An)

:from-end t の場合
(A1 A2 A3 ... An-1 An) = reduce F => (F A1 (F A2 (F A3 ... (F An-1 An) ...)))

たとえば、関数 F が単純な加算関数とすると、reduce の結果は列の要素の和になります。

F(x, y) = x + y の場合 : reduce => A1 + A2 + A3 + ... + An-1 + An

このような操作を「縮約」とか「畳み込み」といいます。簡単な例を示しましょう。

(reduce #'+ '(1 2 3 4 5 6)) => 21
(reduce #'list '(1 2 3 4 5 6)) => (((((1 2) 3) 4) 5) 6)
(reduce #'list '(1 2 3 4 5 6) :from-end t) => (1 (2 (3 (4 (5 6)))))

キーワード :initial-value が指定された場合、reduce は関数 F を次のように適用します。

:initial-vallue G の場合

(G A1 A2 A3 ... An-1 An) = reduce F => (F (F ... (F (F G A1) A2) ...) An-1) An)

(reduce #'list '(1 2 3 4 5 6) :initial-value 0) => ((((((0 1) 2) 3) 4) 5) 6)

:initial-vallue G :from-end t の場合
(A1 A2 A3 ... An-1 An G) = reduce F => (F A1 (F A2 (F A3 ... (F An G) ...)))

(reduce #'list '(1 2 3 4 5 6) :from-end t :initial-value 7)
=> (1 (2 (3 (4 (5 (6 7))))))

:initial-value がなくて列の要素が 1 つしかない場合、reduce はその要素を返します。列が空で :initial-value が指定されている場合、reduce は :initial-value の値を返します。もしも、列が空で :initial-value も指定されていない場合、reduce は関数 function を引数無しで呼び出してその結果を返します。簡単な例を示します。

(reduce #'+ '(1)) => 1
(reduce #'+ nil :initial-value 2) => 2
(reduce #'+ nil) => 0

reduce と 2 引数の関数を組み合わせることで、いろいろな関数を実現することができます。たとえば、length と append は次のようになります。

(reduce #'(lambda (x y) (+ x 1)) '(a b c d e) :initial-value 0)
=> 5
(reduce #'cons '(a b c d e) :initial-value '(1 2 3 4 5) :from-end t)
=> (a b c d e 1 2 3 4 5)

●ソートとマージ

ソート (sort) はデータを昇順または降順に整列させる操作です。マージ (merge) は整列済みの 2 つのデータ列を 1 つの整列済みのデータ列にまとめる操作です。Common Lisp には関数 sort と merge が用意されています。

関数 sort は引数の sequence を破壊的にソートし、関数 merge はソート済みの 2 つの列 seq1 と seq2 をマージします。簡単な使用例を示しましょう。

(setq a #(9 1 8 2 7 3 4 6 5))

(sort a #'<) => #(1 2 3 4 5 6 7 8 9)
a => #(1 2 3 4 5 6 7 8 9)

(setq a #((9 a) (1 b) (8 c) (2 d) (7 e) (3 f) (4 g) (6 h) (5 i)))
=> #((9 a) (1 b) (8 c) (2 d) (7 e) (3 f) (4 g) (6 h) (5 i))

(sort a #'< :key #'car)
=> #((1 b) (2 d) (3 f) (4 g) (5 i) (6 h) (7 e) (8 c) (9 a))

(merge 'list '(1 3 5 7 9) '(2 4 6 8) #'<)
=> (1 2 3 4 5 6 7 8 9)

キーワード :key を設定することで、複雑なデータでもソートやマージを簡単に行うことができます。

ちょっと寄り道

■パスカルの三角形

組み合わせの数 では、組み合わせの数を求める関数 ncr を使って「パスカルの三角形」を作りました。ここでは ncr を使わずにパスカルの三角形を作ってみましょう。リストとベクタどちらを使っても簡単にプログラムできます。

パスカルの三角形は、両側がすべて 1 で内側の数はその左上と右上の和になっています。したがって、n 段の三角形を作る場合、一段前の値を記憶しておいて隣同士の要素を足し算すればいいわけです。一段前の値をリストに格納すると、プログラムは次のようになります。

List 1 : パスカルの三角形（リスト版）

(defun pascal-sub (num-list)
  (if (second num-list)
      (cons (+ (first num-list) (second num-list))
            (pascal-sub (rest num-list)))
    '(1)))

(defun pascal-list (n)
  (let (buf)
    (dotimes (i n)
      (setq buf (pascal-sub (cons 0 buf)))
      (print buf))))

関数 pascal-sub は、リストの隣同士の要素を足した値をリストに格納して返します。この処理は再帰呼び出しを使えば簡単です。num-list の先頭要素と次の要素を足し算し、その値を再帰呼び出しの返り値に cons で追加すればいいわけです。リストの要素がひとつになると、second は nil を返すので再帰呼び出しが停止します。ここでリスト (1) を返します。また、pascal-sub を呼び出すときは num-list の先頭に 0 を追加します。これで、リストの先頭と最後尾を 1 にすることができます。あとは、関数 pascal-list で pascal-sub を n 回呼び出すだけです。

実行結果は次のようになります。

(pascal-list 6)

(1) 
(1 1) 
(1 2 1) 
(1 3 3 1) 
(1 4 6 4 1) 
(1 5 10 10 5 1) 
nil

次は、ベクタを使ってプログラムを作ります。n 段の三角形を作る場合、大きさが n + 1 のベクタを用意します。たとえば、6 段の三角形を作ってみましょう。次の図を見てください。

  図 3 : パスカルの三角形の求め方

最初にベクタの内容を 0 に初期化し、1 番目に 1 をセットします。これが 1 段目になります。あとは図のように、隣の要素を足し算するだけです。プログラムは次のようになります。

List 2 : パスカルの三角形（ベクタ版）

(defun pascal (n)
  (let ((buff (make-array (1+ n) :initial-element 0)))
    (setf (aref buff 1) 1)
    (dotimes (i n)
      (do ((j (1+ i) (1- j)))
          ((zerop j))
        (format t "  ~3D" (setf (aref buff j)
                                (+ (aref buff j) (aref buff (1- j))))))
      (terpri))))

ベクタはひとつあれば十分です。ただし、ベクタの値を書き換えていくので、ベクタの後方から計算していくことに注意してください。前方から計算すると、値がおかしくなります。実行結果は次のようになります。

(pascal 6)
    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1
    1    5   10   10    5    1
nil

ラムダリストキーワード

Common Lisp は defun やラムダ式の仮引数を定義するリスト (ラムダリスト) で、ラムダリストキーワードを使うことができます。表 8 を見てください。

ラムダリストキーワードは & で始まり、その後ろに引数 (パラメータ) が続きます。それでは &optional から説明しましょう。

●&optional

&optional で指定された引数をオプションパラメータといい、その引数のデフォルト値を設定することができます。指定範囲は次のラムダリストキーワードまで、またはラムダリストの終わりまでです。次の例を見てください。

((lambda (a &optional (b 10)) (+ a b)) 1 2)
=> 3
((lambda (a &optional (b 10)) (+ a b)) 1)
=> 11

b がオプションパラメータです。デフォルト値は (パラメータ デフォルト値）で指定します。また、&optional b のように引数名だけ指定すると、デフォルト値は nil になります。オプションパラメータは対応する実引数が省略された場合、その引数にはデフォルト値がセットされます。実引数が指定された場合は、その値がセットされます。最初の例では実引数 1 と 2 があるので、b には 2 がセットされます。次の例では、実引数が 1 しかないので、b にはデフォルト値 10 がセットされます。

簡単な例題として、リストを反転する関数 reverse を再帰定義で作ってみましょう。Common Lisp には列関数 reverse が用意されているので、関数名は my-reverse とします。reverse はリストを car と cdr で分解して、残りのリストを反転させてから先頭の要素を最後尾に追加することで実現できます。プログラムは次のようになります。

List 3 : リストの反転

(defun my-reverse (l)
  (if (atom l)
      l
      (append (my-reverse (cdr l)) (list (car l)))))

append で反転したリストの最後尾に先頭の要素を追加します。簡単なプログラムですが append を使っているので、リストが長くなると時間がかかるのが欠点です。そこで、次に示すように補助的な関数を用意します。

List 4 : リストの反転（改良版）

(defun my-rev-sub (l z)
  (if (atom l)
      z
      (my-rev-sub (cdr l) (cons (car l) z))))

(defun my-reverse (l) (my-rev-sub l nil))

関数 my-rev-sub は、リスト l の先頭要素を引数 z の先頭に追加していきます。したがって、(my-rev-sub l nil) と呼び出せば、リスト l を反転することができます。my-rev-sub の呼び出しを図に示すと、次のようになります。

(my-rev-sub '(1 2 3 4) nil)
  (my-rev-sub '(2 3 4) '(1))
    (my-rev-sub '(3 4) '(2 1))
      (my-rev-sub '(4) '(3 2 1))
        (my-rev-sub nil '(4 3 2 1))
        => z の値 (4 3 2 1) を返す
      => (4 3 2 1)
    => (4 3 2 1)
  => (4 3 2 1)
=> (4 3 2 1)

引数 z には反転途中の値が格納されていることがわかりますね。このような補助的な関数を使う場合、引数 z をオプションパラメータとして指定すれば、ひとつの関数で my-reverse を実現することができます。プログラムは次のようになります。

List 5 : リストの反転(&optionalを使用)

(defun my-reverse (l &optional z)
  (if (atom l)
      z
      (my-reverse (cdr l) (cons (car l) z))))

これで (my-reverse '(1 2 3 4)) と呼び出せば、リストの反転 (4 3 2 1) を求めることができます。

●&rest

&rest で指定された引数をレストパラメータといい、引数をひとつのリストにまとめて関数へ渡します。&rest の後ろには引数が定義され、その後ろにはほかのラムダリストキーワードか、ラムダリストの終わりでなければいけません。&rest を使うことで、可変個の引数を受け取る関数を定義することができます。

たとえば、2 個以上の引数を受け取る関数は次のように定義します。

(defun foo (a b &rest z)  ・・・・・  )

2 個の実引数は a と b に代入され、残りの引数はリストに格納され z に代入されます。それでは、実際に試してみましょう。

(defun foo (a b &rest z) (format t "a = ~S, b = ~S, z =~S\n" a b z))
=> foo

(foo 1 2 3 4 5)
a = 1, b = 2, z = (3 4 5)

(foo 1 2)
a = 1, b = 2, z = nil

format の ~S は S 式を表示する指定子です。引数が 2 つしかない場合、z には nil が代入されます。また、引数が 2 つに満たない場合はエラーとなります。つまり、&rest で指定した変数に、余った実引数がすべてリストに格納されて渡されるのです。

(defun foo (&rest x) ・・・・・ )

この場合、仮引数は &rest だけで指定します。実引数がない場合、x には nil が代入されます。もし、複数の引数があれば、それらをリストにまとめて x に代入します。それでは、実際に試してみましょう。

(defun foo z (format t "z =~S\n" z)) (訂正 2004/12/02)
(defun foo (&rest z) (format t "z = ~S\n" z))
=> foo

(foo 1 2 3 4 5)
z = (1 2 3 4 5)

(foo)
z = nil

●&key

&key で指定された引数をキーパラメータといい、キーワードを設定することができます。有効範囲は次のラムダリストキーワードまで、またはラムダリストの終わりまでです。次の例を見てください。

; &key の使用例
((lambda (a &key b c) (list a b c)) 10)
=> (10 nil nil)
; デフォルト値の指定
((lambda (a &key (b 1) (c 2) (d 3)) (list a b c d)) 10 :c 20 :b 30 :d 40)
=> (10 30 20 40)

; オプションパラメータとの比較
((lambda (a &key (b 1) (c 2) (d 3)) (list a b c d)) 10 :d 20)
=> (10 1 2 20)
((lambda (a &optional (b 1) (c 2) (d 3)) (list a b c d)) 10 1 2 20)
=> (10 1 2 20)

キーパラメータは、オプションパラメータと同様にデフォルト値を設定することができます。複数の引数にデフォルト値を設定する場合、オプションパラメータよりもキーパラメータを使った方が便利です。最後の例を見てください。引数 d の値を設定する場合、オプションパラメータで定義すると、引数 b と c の値を省略することはできません。キーパラメータを利用することで、引数の個数や順番を気にせずに値を設定することができます。

●&aux

&aux で指定された引数を補助 (AUX) パラメータといいます。補助パラメータはどの実引数にもマッチしません。let* でレキシカル変数を定義することと同じ働きをします。

let* は let と同様にレキシカル変数を定義しますが、変数の初期化が逐次的に行われるところが異なります。つまり setq と同様に、先に初期化された変数の値を参照することができます。次の例を見てください。

(let* ((a 10)
       (b (* a 10)))
  (format t "a = ~D, b = ~D~%" a b))

a = 10, b = 100

変数 b の初期化で変数 a の値を参照しています。a の値は先に初期化された 10 なので、変数 b の値は 100 になります。let の場合、変数 b の初期化で変数 a の値を参照することはできません。

それでは &aux の使用例を示します。

; &aux の使用例
((lambda (a b &aux (c (car a))) (list a b c)) '(10 20) 30)
((10 20) 30 10)

; このプログラムと同じ
((lambda (a b) (let* ((c (car a))) (list a b c))) '(10 20) 30)
((10 20) 30 10)

&aux c のように引数名だけ指定すると、変数は nil に初期化されます。

●注意事項

これらのキーワードはいっしょに使うことができます。その場合、通常の引数の後ろに &optional を定義し、その後ろで &rest だけを定義、最後に &key と &aux を定義するようにしてください。

ちょっと寄り道

■ソート（その２）

ソート（その１）では、挿入ソートとクイックソートを説明しました。今回はクイックソートの弱点とマージソートを説明します。

■クイックソートの弱点

クイックソートは高速なアルゴリズムですが、枢軸の選び方によっては遅いソートと同じになってしまいます。たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。次の図を見てください。

クイックソートは、ソートするデータの中で中間の値を枢軸に選ぶと、データをほぼ半分に分割することができます。この場合がいちばん効率が良いのですが、上図のようにデータの最大値を枢軸として選ぶと、その要素と残りの要素にしか分割されません。これが最悪の場合で、分割のたびに最大値もしくは最小値を枢軸に選ぶと、実行時間は要素数の 2 乗に比例する、つまり遅いソートと同じ結果になるのです。

このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。

ただし、この改良はベクタであれば簡単に実現できるのですが、リストには不向きであることに注意してください。たとえば、データが 1000 個ある場合、ベクタであれば 0, 500, 999 番目のデータを取り出すのは簡単ですが、リストではデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。クイックソートは、リストよりもベクタに向いているソートアルゴリズムといえます。

次は、クイックソートと同様に高速なアルゴリズムであるマージソートを説明します。

■マージ

マージ (併合) とは、複数のソート済み列をひとつのソート済みの列にまとめる操作です。最初にマージから説明します。次の図を見てください。

2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。

Common Lisp には列関数 merge が用意されていますが、実際にプログラムを作ってみましょう。次のリストを見てください。

List 6 : リストのマージ

(defun merge-list (f l1 l2)
  (cond ((atom l1) l2)
        ((atom l2) l1)
        ((funcall f (car l1) (car l2))
         (cons (car l1) (merge-list f (cdr l1) l2)))
        (t (cons (car l2) (merge-list f l1 (cdr l2))))))

関数 merge-list の引数 f がデータを比較する述語、l1 と l2 がマージするリストです。最初に、述語 atom でリスト l1 と l2 にデータがあるかチェックします。どちらかが空リストであれば、もう一方のリストを返します。これが再帰呼び出しの停止条件になります。

l1 と l2 にデータがあれば、先頭要素を述語 f で比較します。f が真であれば l1 の先頭要素を、そうでなければ l2 の先頭要素をmerge-list が返すリストに追加します。merge-list を再帰呼び出しするときは、追加する先頭要素をリストから取り除くことに注意してください。これでリストをマージすることができます。

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

(merge-list #'< '(2 4 6 8) '(1 3 5 7 9))
=> (1 2 3 4 5 6 7 8 9)
(merge-list #'< '(10 20 30) '(1 2 3 4))
=> (1 2 3 4 10 20 30)

■マージソート

マージソートは、このマージを使ってデータをソートします。次の図を見てください。

マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。

それではプログラムを作りましょう。マージソートの場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単にプログラムを作ることができます。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。

再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。

List 7 : マージソート

(defun merge-sort (f l n)
  (cond ((= n 1) (list (car l)))   ; 新しいリストを返す
        ((= n 2)
         (let ((x (first l)) (y (second l)))
           (if (funcall f x y) (list x y) (list y x))))
        (t (let ((m (truncate n 2)))
             ; リストを二分割し再帰呼び出しの結果をマージする
             (merge-list f
                         (merge-sort f l m)
                         (merge-sort f (nthcdr m l) (- n m)))))))

関数 merge-sort の引数 f がデータを比較する述語、l がソートするリスト、n がリストの長さを表します。merge-list はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。

merge-sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は l と n / 2 で表し、後半部分を l1 と n / 2 で表します。l1 は cdr を n / 2 回繰り返せば求めることができます。Common Lisp には cdr を繰り返す関数 nthcdr が用意されています。

nthcdr n list

nthcdr は list に対して n 回だけ cdr を適用します。n は非負の整数でなければなりません。簡単な例を示しましょう。

(nthcdr 0 '(a b c d)) => (a b c d)
(nthcdr 2 '(a b c d)) => (c d)
(nthcdr 5 '(a b c d)) => nil

あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。リストの長さが 2 の場合は簡単なので、2 つの要素を比較してソート済みのリストを作成して返します。そして、merge-sort の返り値を merge-list でマージすればいいわけです。

それでは実行してみましょう。

(merge-sort #'< '(9 5 3 7 6 4 2 8) 8)
=> (2 3 4 5 6 7 8 9)
(merge-sort #'> '(9 5 3 7 6 4 2 8) 8)
=> (9 8 7 6 5 4 3 2)

■実行結果

マージソートの実行時間は、データ数を N とすると平均して N * log₂ N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。ただし、マージソートは単純にリストを二分割するため、クイックソートと違いデータによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれるわけです。

それでは、挿入ソート、クイックソート、マージソートの実行時間を比較してみましょう。データは整数値 1000 個とし、ランダム、昇順 (ソート済み)、降順 (逆順のこと) に要素を並べたリストを昇順にソートします。M.Hiroi のオンボロマシン (Pentium 166 MHz, Windows95) で実行しました。

クイックソートは乱数データではいちばん速いのですが、昇順または降順のデータでは極端に遅くなります。今回のプログラムでは、これらのデータが最悪の結果になります。これがクイックソートの弱点です。これに対し、マージソートはデータの種類にかかわらず高速にソートできることがわかります。挿入ソートはとても遅いのですが、ソート済みのデータだけはとても速いですね。これが挿入ソートの特徴です。もしも、リストがほとんどソートされている状態であれば、挿入ソートでも高速にソートすることができます。

また、要素数が少ない場合は単純なアルゴリズムである挿入ソートの方が速いです。クイックソートやマージソートでも、要素数が少なくなったら挿入ソートに切り換えると少しだけ速くなります。切り換えるタイミングですが、一般には 10 がその境目になるといわれています。この値は使用するプログラミング言語や実行環境によって変わるので、興味のある方は試してみてください。