Slides

アルゴリズムとデータ構造入門
第11回教科書2.4節
糸山克寿 [email protected]
大学院情報学研究科知能情報学専攻音声メディア分野
http://winnie.kuis.kyoto-u.ac.jp/Lecture/14/IntroAlgoDataStruct/
Index
2 Building Abstractions with Data
2.4 Multiple Representations for Abstract Data
2.4.1 Representations for Complex Numbers
2.4.2 Tagged data
2.4.3 Data-Directed Programming and Additivity
2
複数の表現をもつデータ
• 複素数：直交座標
，極座標
• 直交座標  極座標
• 極座標  直交座標
3
cos
sin
atan cos
sin
• 多項式：密配列 dense array，疎配列 sparse array
3
3
5
5
1
密配列
疎配列（連想配列）
(3 5 1)
((2 . 3) (1 . 5) (0 . 1))
(3 0 ... 0 5 0 ... 0 1 0)
((100 . 3) (50 . 5) (1 . 1))
• 集合：順序なしリスト，順序付きリスト，二分探索木，ハッシュ表
万能のデータ表現法はない
複数の表現を場合に応じて使い分けられるようにしたい
複素数システムの構築
準備：複素数の直交座標表現と極座標表現
構築法1：タグ付きデータ tagged data
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• 各手続きがタグを参照し，タグに応じて処理を切り替える
構築法2：データ主導プログラミング data-directed programming
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• システムがタグを参照し，タグに対応する手続きを探して実行する
構築法3：メッセージパッシング message passing
• データ本体とそれに対する各種手続きを組み合わせてデータを構築する
• データにメッセージを送り，メッセージに対応する手続きを実行する
4
複素数システムの構築
準備：複素数の直交座標表現と極座標表現
構築法1：タグ付きデータ tagged data
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• 各手続きがタグを参照し，タグに応じて処理を切り替える
構築法2：データ主導プログラミング data-directed programming
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• システムがタグを参照し，タグに対応する手続きを探して実行する
構築法3：メッセージパッシング message passing
• データ本体とそれに対する各種手続きを組み合わせてデータを構築する
• データにメッセージを送り，メッセージに対応する手続きを実行する
5
複素数の2種類の表現法
Imaginary
6
cos
sin
atan
O
Real
複素数の四則演算
•
•
•
•
7
複素数の四則演算
•
•
•
•
8
複素数の抽象データ表現
• 構築子 constructor
(make-from-real-imag x y)
(make-from-mag-ang r a)
• 選択子 selector
(real-part z)
(imag-part z)
(magnitude z)
(angle z)
9
複素数の四則演算
(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2)) ))
(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2)) ))
(define (mul-complex z1 z2)
(make-from-mag-ang (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2)) ))
(define (div-complex z1 z2)
(make-from-mag-ang (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2)) ))
10
複素数の直交座標表現
• 構築子 constructor
(make-from-real-imag x y)
11
(define (make-from-real-imag x y)
(cons x y) )
• 選択子 selector
(define (make-from-mag-ang r a)
(cons (* r (cos a))
(* r (sin a)) ))
(real-part z)
(define (real-part z) (car z))
(imag-part z)
(define (imag-part z) (cdr z))
(magnitude z)
(define (magnitude z)
(sqrt
(+ (square (real-part z))
(square (imag-part z)) )))
(make-from-mag-ang r a)
(angle z)
(define (angle z)
(atan (imag-part z)
(real-part z) ))
複素数の極座標表現
13
• 構築子 constructor
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x)
(make-from-real-imag x y)
(square y) ))
(atan y x) ))
(make-from-mag-ang r a)
• 選択子 selector
(real-part z)
(imag-part z)
(magnitude z)
(angle z)
(define (make-from-mag-angle r a)
(cons r a) )
(define (real-part z)
(* (magnitude z)
(cos (angle z)) ))
(define (imag-part z)
(* (magnitude z)
(sin (angle z)) ))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
複数表現混在時の問題点
15
• 異なる表現のデータを識別できない
• (2 . 3) は 2
3 と2
のどちらを表す？
• (magnitude '(2 . 3)) は何を返すべきなのか？
• データ自身がどの表現（型）で記述されているのかを示す必要がある
複素数システムの構築
準備：複素数の直交座標表現と極座標表現
構築法1：タグ付きデータ tagged data
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• 各手続きがタグを参照し，タグに応じて処理を切り替える
構築法2：データ主導プログラミング data-directed programming
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• システムがタグを参照し，タグに対応する手続きを探して実行する
構築法3：メッセージパッシング message passing
• データ本体とそれに対する各種手続きを組み合わせてデータを構築する
• データにメッセージを送り，メッセージに対応する手続きを実行する
16
タグ付きデータオブジェクトの生成
17
(define (attach-tag type-tag contents)
(cons type-tag contents) )
(define (make-from-real-imag-rectangular x y)
(attach-tag 'rectangular (cons x y)) )
rectangular
x
y
r
a
(define (make-from-mag-ang-polar r a)
(attach-tag 'polar (cons r a)) )
polar
(define (type-tag datum)
(if (pair? datum) (car datum)
(error "Bad tagged datum: TYPE-TAG" datum) ))
(define (contents datum)
(if (pair? datum) (cdr datum)
(error "Bad tagged datum: CONTENTS" datum) ))
タグ付きデータに対する演算
18
(define (real-part z)
(cond ((rectangular? z)
(real-part-rectangular (contents z)) )
((polar? z)
(real-part-polar (contents z)) )
(else (error "Unknown type: REAL-PART" z)) ))
(define (rectangular? z) (eq? (type-tag z) 'rectangular))
(define (polar? z) (eq? (type-tag z) 'polar))
(define (real-part-rectangular z) (car z))
(define (real-part-polar z)
(* (magnitude-polar z) (cos (angle-polar z))) )
rectangular
x
y
polar
r
a
タグ付き直交座標表現複素数
19
(define (make-from-real-imag-rectangular x y) (define (make-from-real-imag x
(attach-tag 'rectangular (cons x y)) )
(cons x y) )
(define (make-from-mag-ang-rectangular r a)
(attach-tag 'rectangular
(cons (* r (cos a)) (* r (sin a))) ))
(define (make-from-mag-ang r a)
(cons (* r (cos a))
(* r (sin a)) ))
(define (real-part-rectangular z) (car z))
(define (real-part z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (imag-part z) (cdr z))
(define (magnitude-rectangular z)
(define (magnitude z)
(sqrt
(sqrt
(+ (square (real-part-rectangular z))
(+ (square (real-part z))
(square (imag-part-rectangular z)) )))
(square (imag-part z)) )
(define (angle-rectangular z)
(atan (imag-part-rectangular z)
(real-part-rectangular z) ))
(define (make-from-real-imag x y)
(make-from-real-imag-rectangular x y) )
(define (angle z)
(atan (imag-part z)
(real-part z) ))
タグ付き極座標表現複素数
20
(define (make-from-real-imag-polar x y)
(define (make-from-real-imag x y)
(attach-tag 'polar
(cons (sqrt (+ (square x)
(cons (sqrt (+ (square x) (square y)))
(square y) ))
(atan y x) )))
(atan y x) ))
(define (make-from-mag-ang-polar r a)
(attach-tag 'polar (cons r a)) )
(define (make-from-mag-ang r a)
(cons r a) )
(define (real-part-polar z)
(* (magnitude-polar z)
(cos (angle-polar z)) ))
(define (real-part z)
(* (magnitude z)
(cos (angle z)) ))
(define (imag-part-polar z)
(* (magnitude-polar z)
(sin (angle-polar z)) ))
(define (imag-part z)
(* (magnitude z)
(sin (angle z)) ))
(define (magnitude-polar z) (car z))
(define (magnitude z) (car z))
(define (angle-polar z) (cdr z))
(define (angle z) (cdr z))
(define (make-from-mag-ang r a)
(make-from-mag-ang-polar r a) )
複素数システムの構築
準備：複素数の直交座標表現と極座標表現
構築法1：タグ付きデータ tagged data
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• 各手続きがタグを参照し，タグに応じて処理を切り替える
構築法2：データ主導プログラミング data-directed programming
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• システムがタグを参照し，タグに対応する手続きを探して実行する
構築法3：メッセージパッシング message passing
• データ本体とそれに対する各種手続きを組み合わせてデータを構築する
• データにメッセージを送り，メッセージに対応する手続きを実行する
23
put と get による手続きテーブルの操作
• (put <op> <type> <item>)
手続き <item> を手続きテーブルに挿入し，
手続きの名前 <op> と引数の型 <type> で索引づける
• (get <op> <type>)
手続きの名前 <op> と引数の型 <type> で索引づけられた手続きを返す
該当する手続きがなければ false を返す
(put 'real-part 'rectangular (lambda (z) (car z)))
(put 'real-part 'polar
(lambda (z) (* (car z) (cos (cdr z)))) )
((get 'real-part 'rectangular) (cons 2 3))  2
((get 'real-part 'polar) (cons 2 3))
 2.236
24
直交座標表現複素数パッケージ
(define (install-rectangular-package)
;; 内部手続き
(define (make-from-real-imag x y)
(cons x y) )
(define (make-from-mag-ang r a)
(cons (* r (cos a))
(* r (sin a)) ))
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
(sqrt (+
(square (real-part z))
(square (imag-part z)) )))
(define (angle z)
(atan (imag-part z)
(real-part z) ))
25
;; システムとのインタフェース
(define (tag x)
(attach-tag 'rectangular x))
(put 'make-from-real-imag
'rectangular
(lambda (x y) (tag
(make-from-real-imag x y) )))
(put 'make-from-mag-ang
'rectangular
(lambda (r a) (tag
(make-from-mag-ang r a) )))
(put 'real-part '(rectangular)
real-part)
(put 'imag-part '(rectangular)
imag-part )
(put 'magnitude '(rectangular)
magnitude )
(put 'angle '(rectangular) angle)
'done )
極座標表現複素数パッケージ
(define (install-polar-package)
;; 内部手続き
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x)
(square y) ))
(atan y x) ))
(define (make-from-mag-ang r a)
(cons r a) )
(define (real-part z)
(* (magnitude z)
(cos (angle z)) ))
(define (imag-part z)
(* (magnitude z)
(sin (angle z)) ))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
26
;; システムとのインタフェース
(define (tag x)
(attach-tag 'polar x))
(put 'make-from-real-imag
'polar
(lambda (x y) (tag
(make-from-real-imag x y) )))
(put 'make-from-mag-ang
'polar
(lambda (r a) (tag
(make-from-mag-ang r a) )))
(put 'real-part '(polar)
real-part )
(put 'imag-part '(polar)
imag-part )
(put 'magnitude '(polar)
magnitude )
(put 'angle '(polar) angle)
'done )
汎用の「手続き適用」手続き
(define (apply-generic op . args)
(let* ((type-tags (map type-tag args))
(proc (get op type-tags)) )
(if proc
(apply proc (map contents args))
(error "No method for types: APPLY-GENERIC"
(list op type-tags) ))))
(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))
27
複素数システムの構築
準備：複素数の直交座標表現と極座標表現
構築法1：タグ付きデータ tagged data
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• 各手続きがタグを参照し，タグに応じて処理を切り替える
構築法2：データ主導プログラミング data-directed programming
• データ本体とその型を表すシンボルを組み合わせてデータを構築する
• システムがタグを参照し，タグに対応する手続きを探して実行する
構築法3：メッセージパッシング message passing
• データ本体とそれに対する各種手続きを組み合わせてデータを構築する
• データにメッセージを送り，メッセージに対応する手続きを実行する
28
復習：cons, car, cdr を手続きで実装
29
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1" m)) ))
dispatch )
(define (car z) (z 0))
(define (cdr z) (z 1))
(define foo (cons 10 25))
(car foo)  (foo 0)  (dispatch 0)  10
(cdr foo)  (foo 1)  (dispatch 1)  25
復習：cons, car, cdr を手続きで実装
(define (cons x y)
(define (dispatch m)
(cond ((= m 'car) x)
((= m 'cdr) y)
(else (error "Unknown message" m)) ))
dispatch )
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define foo (cons 10 25))
(car foo)  (foo 'car)  (dispatch 'car)  10
(cdr foo)  (foo 'cdr)  (dispatch 'cdr)  25
30
メッセージパッシング message passing
(define (make-from-real-imag x y)
(define (dispatch op)
(cond ((eq? op 'real-part) x)
((eq? op 'imag-part) y)
((eq? op 'magnitude)
(sqrt (+ (square x) (square y))) )
((eq? op 'angle) (atan y x))
(else (error "Unknown op" op)) ))
dispatch )
(define z (make-from-real-imag 2 1))
(z 'real-part)  2
(z 'magnitude)  2.236
31
加法性 additivity (Ex. 2.76)
32
• あるシステムに機能（表現や手続き）を追加するときに
既存の機能を修正する必要があるか否か
表現の追加・削除
手続きの追加・削除
その他の特徴
汎用手続き
✗ 既存手続きの修正必要
✓ 既存表現の修正不要
いちいち場合分け
手続きテーブル
✓ 既存手続きの修正不要
✗ 既存表現の修正必要
テーブル肥大化
メッセージパッシング
✓ 既存手続きの修正不要
✗ 既存表現の修正必要
オブジェクト指向
加法性 additivity
表現の追加・削除
33
手続きの追加・削除
その他の特徴
汎用手続き
✗ 既存手続きの修正必要
✓ 既存表現の修正不要
いちいち場合分け
手続きテーブル
✓ 既存手続きの修正不要
✗ 既存表現の修正必要
テーブル肥大化
メッセージパッシング
✓ 既存手続きの修正不要
✗ 既存表現の修正必要
オブジェクト指向
(define (real-part z)
(cond ((rectangular? z)
(real-part-rectangular (contents z)) )
((polar? z)
(real-part-polar (contents z)) )
(else (error "Unknown type: REAL-PART" z)) ))
(define (real-part z)
(cond ((rectangular? z)
(real-part-rectangular (contents z)) )
((polar? z)
(real-part-polar (contents z)) )
((new-complex-repr? z)
(real-part-new-complex-repr (contents z)) )
(else (error "Unknown type: REAL-PART" z)) ))
複数表現混在への現実的な解
• Schemeを使わない。
• 典型的手続きは抽象クラスで規定
• クラスの拡張 (extend) でコード削減
abstract class Complex {
float real() {
return magnitude() * Math.cos(angle());
}
float imag() {
return magnitude() * Math.sin(angle());
}
float magnitude() {
return Math.sqrt(real() * real() + imag() * imag());
}
float angle() {
return Math.atan2(imag(), real());
}
}
class Rectangular extends Complex {
float x;
float y;
Rectangular(float x, float y) {
this.x = x;
this.y = y;
}
float real() {
return x;
}
float imag() {
return y;
}
}
class Polar extends Complex {
float r;
float a;
Rectangular(float r, float a) {
this.r = r;
this.a = a;
}
float magnitude() {
return r;
}
float angle() {
return a;
}
}
34
レポート課題 1/12 (月) 〆切
• 必須問題
1. Exercise 2.75
メッセージパッシング
• 随意問題
2. Exercise 2.73
記号微分
3. Exercise 2.74
データ主導プログラミングによるデータベース統合
35

Download Report