SICP 読書ノート#16 - 2.3.3 集合の表現 (pp.88-94)
「§2.3.3 集合の表現」から。
順序づけられないリストの集合
写経して動かしてみる。intersection-setは内積（積集合）が求まる。
racket@> (element-of-set? 'a '(a b c d)) #t racket@> (adjoin-set 'z '(a b c d)) '(z a b c d) racket@> (intersection-set '(a b c d) '(c x y b)) '(b c)
問題 2.59
和集合を返す手続き、union-setを実装する。順序づけは意識しない。
(define (union-set set1 set2) (cond ((and (null? set1) (null? set2)) '()) ((null? set1) set2) ((null? set2) set1) ((not (element-of-set? (car set1) set2)) (cons (car set1) (union-set (cdr set1) set2))) (else (union-set (cdr set1) set2))))
racket@> (union-set '(a b c d) '(c x y b)) '(a d c x y b)
問題 2.60
要素の重複をありとして、これまでの手続きを設計せよ。
これまでの手続きについて、
- element-of-set? : 変更なし
- adjoin-set : 無条件にconsアップ
- union-set : 無条件にappend
- intersection-set : 変更なし
adjoin-setとunion-setを書き直してみる。
(define (adjoin-set x set) (cons x set)) (define (union-set set1 set2) (append set1 set2))
テスト。
racket@> (adjoin-set 'd '(a b c d)) '(d a b c d) racket@> (union-set '(a b c d) '(c x y b)) '(a b c d c x y b)
順序づけられたリストとしての集合
写経して動かす。引数のsetも昇順でソート済みの想定。
racket@> (element-of-set? 1 '(1 2 3 4)) #t racket@> (intersection-set '(1 2 3 4) '(2 4 6 7)) '(2 4) ;; ソートされていない集合を渡しても上手く動かない racket@> (intersection-set '(1 2 3 4) '(4 6 7 2)) '(4)
問題 2.61
adjoin-setを実装する。
反復的に処理を行い、xの挿入ポイントが発見できれば処理を打ち切ればよいので、
x次第だがリストの長さに対してステップ数のオーダー期待値はO(n)となる。
(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))))))
テスト。
racket@> (adjoin-set 4 '(1 3 6 9)) '(1 3 4 6 9) racket@> (adjoin-set 10 '(1 3 6 9)) '(1 3 6 9 10) racket@> (adjoin-set 3 '(1 3 6 9)) '(1 3 6 9) racket@>
問題 2.62
少なくともset1、set2のいずれかの要素を削って行けるため、O(n)オーダーでの処理となる。
(define (union-set set1 set2) (cond ((and (null? set1) (null? set2)) '()) ((null? set1) set2) ((null? set2) set1) ((< (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2))) ((> (car set1) (car set2)) (cons (car set2) (union-set set1 (cdr set2)))) (else (cons (car set1) (union-set (cdr set1) (cdr set2))))))
テスト。
racket@> (union-set '(1 2 3 4) '(1 3 5 7)) '(1 2 3 4 5 7) racket@> (union-set '(1 3 5 7) '(1 2 3 4)) '(1 2 3 4 5 7)
二進木としての集合
問題 2.63
まずは動かしてみた。
racket@> (define tree nil) racket@> (map (lambda (n) (set! tree (adjoin-set n tree))) (shuffle (range 1 10))) racket@> tree '(5 (3 (2 (1 () ()) ()) (4 () ())) (7 (6 () ()) (8 () (9 () ())))) racket@> (tree->list-1 tree) '(1 2 3 4 5 6 7 8 9) racket@> (tree->list-2 tree) '(1 2 3 4 5 6 7 8 9)
同じ結果になる模様。
ステップ数のオーダーはよくわからない。tree->list-2の方が反復的プロセスなので軽い気がするが。
いずれにせよ、全ての要素をなめる必要があるのでO(n)以上は要するかな。
問題 2.64
このletの入れ子はいったい... let*で書き直してみる。
(define (partial-tree elts n) (if (= n 0) (cons '() elts) (let* ((left-size (quotient (- n 1) 2)) (left-result (partial-tree elts left-size)) (left-tree (car left-result)) (non-left-elts (cdr left-result)) (right-size (- n (+ left-size 1))) (this-entry (car non-left-elts)) (right-result (partial-tree (cdr non-left-elts) right-size)) (right-tree (car right-result)) (remaining-elts (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaining-elts))))
スッキリ。
本題に入って、'(1 3 5 7 9 11)を単純にadjoin-setするだけでは、
racket@> (set! tree nil) racket@> (map (lambda (n) (set! tree (adjoin-set n tree))) '(1 3 5 7 9 11)) racket@> tree '(1 () (3 () (5 () (7 () (9 () (11 () ()))))))
明らかに右寄りな木が作られるが、list->tree手続きを使う場合は、
racket@> (list->tree '(1 3 5 7 9 11)) '(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))
左右のバランスが取れた木が作られる。
理由は、最初にリストの長さを取った上で、中央の要素から再帰的に木を作っているためから。
ステップ数のオーダーは O(n) かな。
問題 2.65
問題 2.63、2.64の結果を使ってunion-setとintersection-setをO(n)で実装せよ。
tree->listしてlist->treeしてもOKなのかな。
(define (union-set-2 tree1 tree2) (list->tree (union-set (tree->list-2 tree1) (tree->list-2 tree2)))) (define (intersection-set-2 tree1 tree2) (list->tree (intersection-set (tree->list-2 tree1) (tree->list-2 tree2))))
テスト。
racket@> (define tree1 (list->tree '(1 2 3 4))) racket@> (define tree2 (list->tree '(1 3 5 7))) racket@> (union-set-2 tree1 tree2) '(3 (1 () (2 () ())) (5 (4 () ()) (7 () ()))) racket@> (intersection-set-2 tree1 tree2) '(1 () (3 () ()))
list->tree、union-set、intersection-set、tree->list-2の
全てがO(n)なので、この手続きもO(n)ということだと思う。
集合と情報検索
テキストのlookupを動作させるにはkey-valueストアを完成させる必要がある。
(define (make-record key value) (cons key value)) (define (key record) (car record)) (define (value record) (cdr record))
テスト。ワールドカップ2014にちなんでコロンビア戦でのブラジル代表のスタメン。
racket@> (define slecao (list (make-record 3 '(Thiago Silva)) (make-record 4 '(David Louis)) (make-record 5 '(Fernandinho)) (make-record 6 '(Marcelo)) (make-record 7 '(Hulk)) (make-record 8 '(Paulinho)) (make-record 9 '(Fred)) (make-record 10 '(Neymar)) (make-record 11 '(Oscar)) (make-record 12 '(Julio Cesar)) (make-record 23 '(Maicon)))) racket@> (lookup 10 slecao) '(10 Neymar) racket@> (lookup 3 slecao) '(3 Thiago Silva)
問題 2.66
レコードの集合が順序づけられている二進木で構造かされている場合のlookup手続きを実装せよ。
テキストのlookupを参考に、二分木を走査できる形に変える。
(define (lookup given-key tree) (cond ((null? tree) false) ((equal? given-key (key (entry tree))) (entry tree)) ((< given-key (key (entry tree))) (lookup given-key (left-branch tree))) (else (lookup given-key (right-branch tree)))))
テスト。
racket@> (define slecao (list->tree (list (make-record 3 '(Thiago Silva)) (make-record 4 '(David Louis)) (make-record 5 '(Fernandinho)) (make-record 6 '(Marcelo)) (make-record 7 '(Hulk)) (make-record 8 '(Paulinho)) (make-record 9 '(Fred)) (make-record 10 '(Neymar)) (make-record 11 '(Oscar)) (make-record 12 '(Julio Cesar)) (make-record 23 '(Maicon))))) racket@> (lookup 3 slecao) ; => '(3 Thiago Silva) racket@> (lookup 10 slecao) ; => '(10 Neymar) racket@> (lookup 13 slecao) ; => #f
まとめ
- 順序なし集合、順序あり集合、二分木集合で見たように、 集合の形に応じて計算オーダーの違いやその他のメリット・デメリットが発生する
- 集合の構造が異なったとしても、adjoin-set、lookupの内部で抽象化することで、 それらの手続きのインターフェースは共通のままである。 (利用者からすると木構造などを意識する必要はない)
次回は「§2.3.4 Huffman符号化木」から。
