SICP 読み会 2022-04-19

2022年5月17日 21:44

趣味で読んでいるもの。読んでいるときのメモ

2.3.3 集合の表現

以下が実装されていれば、集合とみなす
- ある要素が集合の構成要素か? (element-of-set?)
- 集合への追加 (adjoin-set)
- 積集合 (intersection-set)
- 和集合 (union-set)

実装方針1:
- (element-of-set? x set) : 全走査する
- (adjoin-set x set) : (element-of-set? x set) ? set : cons(x set)
- (intersection-set set1 set2) :
  1. set1から1つ取り出す (=xとする)
  2. xがset2になければ、set1からxを抜いた集合と、set2をintersection-set。
  3. xがset2にあれば、2の結果のあと、xと結合する。※2の結果にはxは絶対にない. set1からxが消えているから。
- (union-set set1 set2) :
  - set1から1つずつとりだし、set2にadjoin-setする
    - (cond (null? (cdr set1) (adjoin-set (car set1) set2)) (else (cons (car set1) (union-set (cdr set1) set2))
計算量
- element-of-set? は全走査しているのでO(N)
- adjoin-setはelement-of-set?を内部で1度使うので O(N)
- intersection-setはset1の各要素においてelement-of-set?を使うのでO(N**2)
- union-setは、set1の各要素でadjoin-setを使うのでO(N**2)
実装方針2:
- 順序をつけておく
計算量2:
- element-of-set?では大きさを判定すれば早期に終了させられる。平均してO(N/2)になる。
- adjoin-setはO(N/2)
- intersection-setでは、それぞれの要素を左から順番に捜査すれば良くなるので、O(N)になる
- union-set。書いてないけど、1個ずつ取り出して、小さい方を要素であると確定していく捜査になるはず。これもO(N)になる気がする。

(element-of-set? x tree)
- x == (entry tree) true
- x < (entry tree) (element-of-set? x (left-branch tree))
- x > (entry tree) (element-of-set? x (right-branch tree))

2分岐で探索していけばいいので、探索はO(logN)で効率的。均衡してないと非効率。treeへの追加の仕方がポイント。挿入もO(logN)でできるだろうか？ -> B-treeとred black treeへ

固定長 : 通信文中の各文字を同じビット数で表現
可変長 : 文字によってビット数を変えて表現。符号化された文は短くなるが、どこからどこまでが1つの文字なのか？がわからなくなる問題がある。語頭符号(prefix code)にする、といった解決策が一般的。
語頭符号 : ある記号の符号全体が他の記号の符号のはじめとかぶらないように符号化を設計すること。