読者です 読者をやめる 読者になる 読者になる

@uents blog

Code wins arguments.

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符号化木」から。


※「SICP読書ノート」の目次はこちら