練習問題 2.59 - 2.60 (or - 2.62)
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)