2.3.3 例: 集合を表現する

union-set
intersection-set
element-of-set?
adjoin-set

2.3.3 (a) 順序なしリストとしての集合

リストを表現するやり方のひとつは、要素が二回以上現れることがないリストというものです。空集合は空リストとして表現します。

順序なしかつ unique なリストとして表現.

今回の実装で生じるステップ数:

関数	順序なしuniqueリスト (p.164 より)
`union-set`	$O(\text{set} * \text{element-of-set?})$ = $O(n^2)$
`intersection-set`	$O(\text{set} * \text{element-of-set?})$ = $O(n^2)$
`element-of-set?`	$O(\text{set})$ = $O(n)$
`adjoin-set`	$O(\text{element-of-set?})$ = $O(n)$

実装

; [sec-2.3.3-a.scm]
;
(define (sec-2.3.3-a)
	(print "(element-of-set? 1 odds)")
	(print ";==> " (element-of-set? 1 odds))
	(print "(element-of-set? 2 odds)")
	(print ";==> " (element-of-set? 2 odds))

	(newline)
	(print "(element-of-set? 1 primes)")
	(print ";==> " (element-of-set? 1 primes))
	(print "(element-of-set? 2 primes)")
	(print ";==> " (element-of-set? 2 primes))

	(newline)
	(print "(adjoin-set 11 odds)")
	(print ";==> " (adjoin-set 11 odds))
	(print "(adjoin-set 9 odds)")
	(print ";==> " (adjoin-set 9 odds))

	(newline)
	(print "(intersection-set odds primes)")
	(print ";==> " (intersection-set odds primes))
	#t)


(define odds (list 1 3 5 7 9))
(define primes (list 2 3 5 7 11))


(define (element-of-set? x set)
	(cond
		((null? set) #f)
		((equal? x (car set)) #t)
		(else (element-of-set? x (cdr set)))))


(define (adjoin-set x set)
	(if
		(element-of-set? x set)
		set
		(cons x set)))


(define (intersection-set set1 set2)
	(cond
		((or (null? set1) (null? set2)) '())
		((element-of-set? (car set1) set2)
			(cons (car set1) (intersection-set (cdr set1) set2)))
		(else (intersection-set (cdr set1) set2))))

実行結果

gosh> (sec-2.3.3-a)
(element-of-set? 1 odds)
;==> #t
(element-of-set? 2 odds)
;==> #f

(element-of-set? 1 primes)
;==> #f
(element-of-set? 2 primes)
;==> #t

(adjoin-set 11 odds)
;==> (11 1 3 5 7 9)
(adjoin-set 9 odds)
;==> (1 3 5 7 9)

(intersection-set odds primes)
;==> (3 5 7)

ex. 2.59. union-set 演算の実装

union-set は、二つの集合の和集合、つまりどちらかの引数に含まれる要素をすべて含む集合を計算します。
(p.162)

set1 の要素のうち, set2 には含まれないもののみを追加する.

重複不可としていることから, set2 に含まれなかった set1 の要素は, その要素を除けば set1 にも含まれない.
このためその際の処理は (union-set (cdr set1) (cons (car set1) set2)) と記述することもでき, この場合は末尾再帰となる.
set1 の要素がひとつも set2 に含まれていない場合に最大の差が生じ, $n + (n-1) + ... + 1 = n*(n+1)/2$ 回追加で不要な判定が増加することになる.
$O(n^2)$ の違いが生じることから末尾再帰よりも処理量増加のほうがインパクトが大きくなる模様.

処理量増加を抑制しつつ末尾再帰を行うには, (define (iter set1 set2 result) ...) とし, result は初期値で set2, 要素が追加された場合は result にのみ追加で set2 は最後まで不変とし, set1 の確認が終わったら result の方を返すとするのがよさそう.
修正が面倒なので実装はパス（事前の検討がたりてない←）

実装

; [ex-2.59.scm]
;
(define (ex-2.59)
	(print "(union-set odds primes)")
	(print ";==> " (union-set odds primes))
	(print "(union-set primes odds)")
	(print ";==> " (union-set primes odds))
	#t)


(load "./sec-2.3.3-a")


(define (union-set set1 set2)
	(cond
		((null? set1) set2)
		((element-of-set? (car set1) set2)
			(union-set (cdr set1) set2))
		(else (cons (car set1) (union-set (cdr set1) set2)))))

実行結果

gosh> (ex-2.59)
(union-set odds primes)
;==> (1 9 2 3 5 7 11)
(union-set primes odds)
;==> (2 11 1 3 5 7 9)

ex. 2.60. 内部データに重複データを許容する場合の実装.

adjoin-set では重複の判定のために $O(n)$ だったものが, 判定が不要になるため$O(1)$ にて処理できるようになる.

union-set では, set1 の各要素を set2 に対して存在判定していたため $O(n^2)$ だったものが, 単純に追加でよくなるため $O(n)$ にて処理できるようになる.

element-of-set? 及び intersection-set は, コードに変更はなくオーダーも同一ではあるが, n が adjoin-set 及び union-set のたびに伸張し続けるため, $n$ の値自体は増大する.

要素数は増大するものの, 全体的に処理オーダーは削減される模様. ちょっと意外・ω・；

関数	順序なしuniqueリスト (p.164 より)	順序なし重複許容リスト (今回)
`union-set`	$O(\text{set} * \text{element-of-set?})$ = $O(n^2)$	$O(\text{set})$ = $O(n)$
`intersection-set`	$O(\text{set} * \text{element-of-set?})$ = $O(n^2)$	同左 = $O(n * n)$ = $O(n^2)$
`element-of-set?`	$O(\text{set})$ = $O(n)$	同左 = $O(n)$
`adjoin-set`	$O(\text{element-of-set?})$ = $O(n)$	$O(1)$

(最初 intersection-set の処理量考えるとき element-of-set? の処理量じゃなくて adjoin-set の処理量を間違えて使ってて $O(n)$ にしちゃってたぽいノω＜

実装

; [ex-2.60.scm]
;
(define (ex-2.60)
	(print "odds")
	(print ";==> " odds)
	(print "primes")
	(print ";==> " primes)
	(print "(adjoin-set 13 primes)")
	(print ";==> " (adjoin-set 13 primes))
	(print "(union-set odds primes)")
	(print ";==> " (union-set odds primes))
	(print "(union-set primes odds)")
	(print ";==> " (union-set primes odds))
	(print "(intersection-set primes odds)")
	(print ";==> " (intersection-set primes odds))
	(print "(element-of-set? 11 (union-set primes odds))")
	(print ";==> " (element-of-set? 11 (union-set primes odds)))
	(print "(element-of-set? 11 (intersection-set primes odds))")
	(print ";==> " (element-of-set? 11 (intersection-set primes odds)))
	#t)


(load "./ex-2.59")


; override
(define (adjoin-set x set)
	(cons x set))


; override
(define (union-set set1 set2)
	(append set1 set2))

実行結果

gosh> (ex-2.60)
odds
;==> (1 3 5 7 9)
primes
;==> (2 3 5 7 11)
(adjoin-set 13 primes)
;==> (13 2 3 5 7 11)
(union-set odds primes)
;==> (1 3 5 7 9 2 3 5 7 11)
(union-set primes odds)
;==> (2 3 5 7 11 1 3 5 7 9)
(intersection-set primes odds)
;==> (3 5 7)
(element-of-set? 11 (union-set primes odds))
;==> #t
(element-of-set? 11 (intersection-set primes odds))
;==> #f

2.3.3 (b) 順序つきリストとしての集合

この集合演算を速くする方法のひとつとして、集合の要素が昇順に並ぶように表現を変えるというものがあります。
〜〜
ここでは話を簡単にするため、集合の要素が数値である場合についてのみ考えることにします。

関数	順序なしuniqueリスト (p.164 より)	順序なし重複許容リスト (ex-2.60)	順序付きuniqueリスト
`union-set`	$O(\text{set} * \text{element-of-set?})$ = $O(n^2)$	$O(\text{set})$ = $O(n)$	$O(\text{set1} + \text{set2})$ = $O(n*2)$ = $O(n)$ (ex-2.62)
`intersection-set`	$O(\text{set} * \text{element-of-set?})$ = $O(n^2)$	同左 = $O(n * n)$ = $O(n^2)$	$O(\text{set1} + \text{set2})$ = $O(n*2)$ = $O(n)$
`element-of-set?`	$O(\text{set})$ = $O(n)$	同左 = $O(n)$	$O(\text{set}/2)$ = $O(n/2)$ = $O(n)$
`adjoin-set`	$O(\text{element-of-set?})$ = $O(n)$	$O(1)$	$O(\text{set}/2)$ = $O(n/2)$ = $O(n)$ (ex-2.61)

intersection-set 及び element-of-set? において, $O(n)$ から $O(n/2)$ になって, 処理量自体は同じ $O(n)$ だけれど定数項で $1/2$ になっている.
しかしその分 union-set が $O(n)$ から $O(2*n)$ へと定数項の増加, そして adjoin-set が $O(1)$ から $O(n)$ と処理量自体の増加となっている.

実装

; [sec-2.3.3-b.scm]
;
(define (sec-2.3.3-b)
	#t)


(define (element-of-set? x set)
	(cond
		((null? set) #f)
		((= x (car set)) #t)
		((< x (car set)) #f)
		(else (element-of-set? x (cdr set)))))


(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)))))))

実行結果

なし.

ex-2.61. adjoin-set の実装

element-of-set? から類推して、順序つきであることの利点を生かして、順序なしの表現に比べて平均的に半分のステップを必要とする手続きを作るやり方を示せ。

実装

; [ex-2.61.scm]
;
(define (ex-2.61)
	(print "(adjoin-set 1 ())")
	(print ";==> " (adjoin-set 1 ()))
	(print "(adjoin-set 5 '(3 5 10))")
	(print ";==> " (adjoin-set 5 '(3 5 10)))
	(print "(adjoin-set 7 '(3 5 10))")
	(print ";==> " (adjoin-set 7 '(3 5 10)))
	(print "(adjoin-set 13 '(3 5 10))")
	(print ";==> " (adjoin-set 13 '(3 5 10)))
	#t)


(define (adjoin-set x set)
	(cond
		((null? set) (list x))
		((= x (car set)) set)
		((< x (car set)) (cons x set))
		(else (cons (car set) (adjoin-set x (cdr set))))))

実行結果

gosh> (load "./ex-2.61")
# t
gosh> (ex-2.61)
(adjoin-set 1 ())
;==> (1)
(adjoin-set 5 '(3 5 10))
;==> (3 5 10)
(adjoin-set 7 '(3 5 10))
;==> (3 5 7 10)
(adjoin-set 13 '(3 5 10))
;==> (3 5 10 13)

ex-2.62. union-set の実装

順序つきリストとして表現された集合に対して、 union-set を $O(n)$ で実装せよ。

実装

; [ex-2.62.scm]
;
(define (ex-2.62)
	(print "(union-set '(2 3 5) '(1 3 5))")
	(print ";==> " (union-set '(2 3 5) '(1 3 5)))
	#t)


(define (union-set set1 set2)
	(cond
		((null? set1) set2)
		((null? set2) set1)
		(else
			(let ((x1 (car set1)) (x2 (car set2)))
				(cond
					((= x1 x2)
						(cons x1 (union-set (cdr set1) (cdr set2))))
					((< x1 x2)
						(cons x1 (union-set (cdr set1) set2)))
					((< x2 x1)
						(cons x2 (union-set set1 (cdr set2)))))))))

実行結果

gosh> (ex-2.62)
(union-set '(2 3 5) '(1 3 5))
;==> (1 2 3 5)