SICP §2.3.3（集合の表現　その２　[順序づけられたリストとしての集合]）

Scheme SICP

このセクションでは集合演算を加速（効率化？）するための内容が記載されている。
概略としては、要素をなんらかの規則（シンボルなら辞書順、あるいは要素に数値を付加するなりしてその大きさ順等）整列させて考えてみようという話。

ここでは話を簡単にするために要素が数値で、昇順に整列された集合を考えるようだ。
つまり、



{1 3 6 10}
という集合を考える場合、今までは


(6 1 10 3)
という表現も可能だったが、このセクションでは


(1 3 6 10)
という表現しか許可しないということになる。
で、そういう制限をつけるとどんなご利益があるかというと、element-of-set? の性能が飛躍的に向上する。
というのは、例えば、56 という要素が、ある集合に含まれているかチェックをする場合、対象とする集合の先頭をチェックし、これが 56 より大きかった場合、もはやそれ以降の要素は全て 56 より大きいわけだからすべて走査する必要がなくなるということ。

実装を記載してみよう。

(define (element-of-set?  x set)
  (cond ((null? set) '())
	((= x (car set)) #t) ;数値比較なので = を使う。
	((< x (car set)) #f) ;集合の先頭要素が x より大きい場合は先頭以降の要素は全てxより大きいことが保証されるので #f を返却
	(else
	 (element-of-set? x (cdr set)))))

これで、探査回数は最小で1回、最大は集合の要素数となる。（仮に n 個の要素があったとしたら n回ね。）
平均すれば n/2 回で、Θ(n)のオーダーになる。
次に intersection-set について説明されていて、「更に目覚ましい加速が出来る」とある。
順序づけられない集合では set1（要素数 a）の要素に対して a 回の走査、set2（要素数 b）に対して b 回の走査。回数でいうと a × b 回で、オーダーとしては Θ(n^2) だった。

これが順序づけられた表現だともっとうまい方法で効率的にチェックできる。う〜ん、set1 と set2 を並行してチェックしていく感じ？



set1 の先頭要素を x1、set2 の先頭要素を x2 とすると、
・x1 = x2 → 積集合に付け加え、set1、set2、両方とも残りの要素で再びチェック。

・x1 < x2 → x1 は積集合に入らない。set1 は x1 を除外した残りの要素で、また set2 はそのままの要素で再びチェック。

・x1 > x2 → x2 は積集合に入らない。set1 はそのままの要素で、また set2 は x2 を除外した残りの要素で再びチェック。
これだと set1 の要素数を a、set2 の要素数を b とした場合、最大でも a + b 回の探査で完了する。つまりオーダーで言えば Θ(n) になるわけだ。
こいつを実装するとこんな感じ。

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1))
	    (x2 (car set2)))
	(cond ((= x1 x2)
	       (cons x1 (intersection-set (cdr set1) (cdr set2))))
	      ((< x1 x2)
	       (intersection-set (cdr set1) set2))
	      ((< x2 x1)
	       (intersection-set set1 (cdr set2)))))))

ま〜、Θ(n^2) と Θ(n) の違いはでかいよね〜。