アルゴリズムとデータ構造入門 -14 2014 年 1 月 21 日 大学院情報学研究科知能情報学専攻 http://winni.kuis.kyoto-u.ac.jp/~okuno/lctur/13/introalgds/ okuno@i.kyoto-u.ac.jp,okuno@nu.org if mod( 学籍番号の下 3 桁,3) 0 if mod( 学籍番号の下 3 桁,3) 1 if mod( 学籍番号の下 3 桁,3) 2 試験は 1 月 28 日 ( 火 )3 限 8 号館 3F 大講義室 1 1. vctor ( ベクタ ) によるSorting 1. ヒープソート (hap sort) 2. Sarching ( 探索 ) 1. 二分探索 (binary sarch) 2. ハッシュ法 (hashing) 3. 授業アンケート 3 (dfin (palindrom? chars) (qual? chars (rvrs chars) ) (dfin (mak-palindrom chars) (dfin (mak-vn-palindrom chars) (appnd chars (rvrs chars)) ) (dfin (mak-odd-palindrom chars) (appnd chars (cdr (rvrs chars))) ) (palindrom? '(shi n bu n shi)) (palindrom? '(ta k ya bu ya k ta)) (palindrom? (M A D A M I M A D A M)) (dfin (last-but-on itms) (rvrs (cdr (rvrs itms))) ) (last-but-on '(shi n bu n shi)) (shi n bu n) 4 1
データの並びを表現するデータ型 #( 要素 0 要素 n-1 ) インデックス (indx) は 0 から始まる (0-origin) 要素 は任意のデータ いわゆる 1 次元配列 (array) Constructor( 構築子 ) (mak-vctor サイズ [ データ ]) (vctor データ 0 データ n-1 ) (list->vctor リスト ) 5 Slctors( 選択子 ) (vctor-rf ベクタ インデックス ) その他 (vctor-lngth ベクタ ) サイズを返す (vctor-st! ベクタ インデックス データ ) (vctor->list ベクタ ) 入出力は #(1 2 3 4 5) 6 (dfin y (mak-vctor 5)) #(() () () () ()) (dfin x #(1 2 3 4 5)) #(1 2 3 4 5) (vctor-lngth x) 5 (vctor-rf x 2) 3 (vctor-st! x 3 128) #(1 2 3 128 5) x #(1 2 3 128 5) (vctor-st! x 0 'foo) #(foo 2 3 128 5) 7 2
ヒープとは 2 分木の特殊形 ヒープの高さを h とすると 1. 高さ h-1 までは完全 2 分木 2. 高さ h の葉は左詰 3. 親ノードの値 v p と子ノードの値 v c とすると v p prd v c が成立 prd は比較 (<, >, >=, <=) ベクタで実現する h h-1 8 ヒープの高さを h とすると 高さ h-1 までは完全 2 分木 高さ h の葉は左詰 ベクタ利用の利点 2i 2i+1 サイズ0 親のインデックスを i 子のインデックスは 2i, 2i+1 i h h-1 i 2i 2i+1 9 (dfin (mak-hap maxsiz) (lt ((hap (mak-vctor (+ maxsiz 1)))) (vctor-st! hap 0 0) hap ))) (dfin (hap-siz hap) (vctor-rf hap 0)) (dfin (hap-lft-child n) (* n 2)) (dfin (hap-right-child n) (+ (* n 2) 1)) (dfin (hap-parnt n) (quotint n 2)) (dfin (hap-top hap) (vctor-rf hap 1)) (dfin (hap-siz-st! hap n) (vctor-st! hap 0 n) ) 0 i 2i 2i+1 サイズ10 3
(dfin (insrt-hap hap lmnt prd) (lt ((n (+ (hap-siz hap) 1))) (vctor-st! hap n lmnt) (hap-siz-st! hap n) (sift-up hap n lmnt prd) lmnt )) sift-up では 高さが 1 つずつ減少 11 (dfin (sift-up hap from lmnt prd) (if (<= from 1) lmnt (lt ((parnt (hap-parnt from))) (lt ((valu (vctor-rf hap parnt))) (cond ((prd valu lmnt) lmnt) (ls (vctor-st! hap from valu) (vctor-st! hap parnt lmnt) (sift-up hap parnt lmnt prd ))))))) 1 回繰り返すと高さが1 減少 要素数を n とすると計算量は (log n) 12 (dfin (hap-xtract-top hap prd) (lt* ((valu (hap-top hap)) (n (hap-siz hap)) (lmnt (vctor-rf hap n)) ) (hap-siz-st! hap (- n 1)) (vctor-st! hap 1 lmnt) (sift-down hap 1 (- n 1) lmnt prd) valu )) sift-down では 高さが 1 つずつ増加 13 4
(dfin (sift-down hap from to lmnt prd) (lt ((lft-child (hap-lft-child from)) (right-child (hap-right-child from)) ) (if (or (>= from to) (> lft-child to)) lmnt (lt ((max-child (if (> right-child to) lft-child (if (prd (vctor-rf hap lft-child) (vctor-rf hap right-child) ) lft-child right-child )))) (lt ((max-child-valu (vctor-rf hap max-child))) (cond ((prd lmnt max-child-valu) lmnt) (ls (vctor-st! hap from max-child-valu) (vctor-st! hap max-child lmnt) (sift-down hap max-child to lmnt prd )))))))) 14 1 回繰り返すと高さが 1 増加 要素数を n とすると計算量は (log n) sift-downward では 高さが 1 ずつ増加 15 (dfin (hap-sort rcords. args) (lt ((prd (if (null? args) >= (car args))) (hap (mak-hap 100)) (rsult ()) ) (for-ach (lambda (i) (insrt-hap hap i prd)) rcords) (do ((i (lngth rcords) (- i 1)) (rsult nil) ) ((<= i 0) (rvrs rsult)) (st! rsult (cons (hap-xtract-top hap prd) rsult ))))) ヒープソートの計算量 ( n log n) 16 5
ベクタ x のヒープ成立条件 hap(m,n) im1, n xi 2 xi sift-down では 実行前 : hap(1,n) の成立は? 実行後 : hap(1,3) が成立 k 回目の sift-down では 実行前 :hap(1,k) は成立, hap(k,n)? 実行後 :hap(k,2k+1) が成立 つまり, hap(1,2k+1) が成立 17 ベクタ x のヒープ成立条件 hap(m,n) im1, n xi 2 xi sift-up では 実行前 :hap(1,n) 成立, hap((n+1)/2,n+1) だけが? 実行後 :hap((n+1)/4,(n+1)/2) は? k 回目の sift-up では 実行前 :hap(k/2,k)? 他は成立 実行後 :hap(k/2,n) 成立, hap(k/4,k/2)? 18 1. vctor ( ベクタ ) によるSorting 1. ヒープソート (hap sort) 2. Sarching ( 探索 ) 1. 二分探索 (binary sarch) 2. ハッシュ法 (hashing) 3. 授業アンケート 19 6
二分探索 (binary sarch) > = < 比較 > = < > = < 二分探索の計算量 (log n) 20 探したいデータの範囲膨大 例 : 最大 10 文字の単語 50 文字とすると組合わせの数は log( 50 10 ) 10(2 log 2) 17 ところが実際の単語数は高々 6 10 ベクタ ( 配列 ) で単語を管理すると疎 すかすかの配列 ハッシュ法 (hashing) を使用 10 50 17 10 22 1. vctor ( ベクタ ) によるSorting 1. ヒープソート (hap sort) 2. Sarching ( 探索 ) 1. 二分探索 (binary sarch) 2. ハッシュ法 (hashing) 3. 授業アンケート 23 7
ッapocalyps 黙示シュ値ントリハapocop 語尾消失 ( 空 ) ハッシュエ apocrypha 聖書外典 apodosis 帰結節 dirctaccss tabl apog 遠地点 apocalyps 2 apog 遠地点 apocop 6 apocrypha 4 apocalyps apodosis 5 apog 0 apocrypha apodosis apocop 24 キーの値の探索なしにアクセス ハッシュ関数 (hash function) キー ハッシュ値 ( 整数 ) ハッシュ表 (hash tabl) サイズ M 占有率 (load factor)α データ量 N N M 異なるキーに対してハッシュ値が同じ ハッシュ値の衝突 (collision) 26 設計の指針 : ランダム性を有するもの キー : x a 1 a 2 a n ky ( x) m 例 1: キーから 例 2: 文字列から整数への写像 n 2 i1 h ( x) cod ( a ) mod M i 例 3: m 2 の中央部分の logm 桁分を使用 h ( x) 1 2 h3 ( x) m mod M K whr constant K such that MK m mod M 2 N 2 27 8
挿入 (insrt) hash 表に ky を持つデータを挿入 検索 (mmbr) hash 表から ky でデータを検索 削除 (dlt) hash 表から ky を持つデータを削除 28 チェイン法 (chaining, sparat chaining, 連鎖法 内部ハッシュ法 ) 開番地法 (opn addrssing, オープン法 外部ハッシュ法 ) 1. 線形走査法 (linar probing) 2. 万能ハッシュ法 (univrsal hashing) 3. 2 重ハッシュ法 (doubl hashing) h, gとすると h(x), h(x)+g(x), h(x)+2g(x), h(x)+3g(x), 29 dog ハッシュ値の衝突 Backt( バケツ ) を作り, つないで行く curb bird bird チェイン法の平均最悪計算量 1. 挿入 (N ) 2. 検索 (N ) 3. 削除 (N ) 30 9
ハッシュ関数 h i 占有率 α N M エントリに状態を導入 /dltd/ky( データ ) 1 1. 挿入 : /dltd というフラグのあるエントリに入れる 2. 検索 : まで探す 3. 削除 : dltd というフラグを立てる dltd キー 1 データ1 キー 2 データ2 31 ハッシュ関数 h 衝突発生時 h i h+i mod M 挿入 /dltd というフラグのあるエントリに入れる 検索 まで探す 削除 dltd というフラグを立てる 32 ハッシュ関数 h, ハッシュ関数をランダムに選択 挿入 /dltd というフラグのあるエントリに入れる 検索 まで探す 削除 dltd というフラグを立てる 33 10
ハッシュ関数 h, g 衝突発生時 h i h+ig mod M 挿入 /dltd というフラグのあるエントリに入れる 検索 /dltd まで探す 削除 dltd というフラグを立てる 34 h(dog)=2 h(kyoto)=4 h(univ)=0 h(informatics)=2 h(sicp)=3 h(tst)=8 0 1 2 3 4 5 6 7 8 9 35 1. n 個のデータが格納済 n+1 個目のデータ挿入時に h i (x) がi-1 回目まですべて詰まっている確率 n n 1 n 2 n i 1 M M 1 M 2 M i 1 2. 空きセルを見つけるまでの比較回数 1 M 1 n( n 1) ( n i 1) 1 M ( M 1) ( M i 1) i1 i1 3. ハッシュ表にN 個のデータを挿入する手間は N M N M M log dx M M n 0 M x M N 1 n M n0 i M M n 36 11
4. 1 回あたりの平均の挿入の手間は M M 1 log log N M N 1 (1 ) Computational Complxity 10.0 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 0.0 1.0 0.1 0.2 1/(1-α) -1/α log (1-α) 0.3 0.4 0.5 0.6 Load Factor 0.7 0.8 0.9 1.0 load factor α 1 1 1 log (1 ) 37 1. dltd はないものと仮定 2. 表にキーがない時は n=n の挿入と同じ M 1 M N 1 3. 表にキーがある時 M M 1 log log (1 ) N M N 1 4. 削除も検索と同じ 5. 上記の解析は 一様ハッシュ (uniform hashing) を仮定 : キーの探索列ランダム 38 1. dltd はないものと仮定 2. 表にキーがない時は n=n の挿入と同じ M 1 M N 1 3. 表にキーがある時 M N log M 1 log (1 ) M N 1 40 12
Hap Sortの正しさを証明せよ 1. Sift-up アルゴリズムを書け 2. Sift-down アルゴリズムを書け 3. Hap-sort アルゴリズムを書け 4. Hap 成立条件を使って,Sift-upアルゴリズムが正しいことを証明 5. Hap 成立条件を使って,Sift-downアルゴリズムが正しいことを証明 6. Hap-sort の計算量を求めよ 41 期末テスト 健闘を期待します 必修課題 2の締切は2 月 9 日 16 時 随意課題の提出でランクアップを 期末テスト :1 月 28 日 ( 火 )3 限 8 号館 3F 大講義室 42 13