Microsoft PowerPoint - IntroAlgDs ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - IntroAlgDs ppt"

あかりだいほうじ
5 years ago
Views:

アルゴリズムとデータ構造入門 -4 006 年月 7 日アルゴリズムとデータ構造入門 Sorting( 整列 ) Hashing( ハッシュ法 ) 奥乃博年前の今朝阪神淡路大震災犠牲者死者だけで 6434

hashing( ハッシュ法 ) 4. アンケート ( 最後の 5 分 ) 配布する用紙に名前を記入して下さい回収は学生同士で教員は一切タッチしません ( 退場!

1 アルゴリズムとデータ構造入門年月 7 日アルゴリズムとデータ構造入門 Sorting( 整列 ) Hashing( ハッシュ法 ) 奥乃博年前の今朝阪神淡路大震災犠牲者死者だけで 6434 人天災は忘れた頃にやってくる ( 寺田寅彦 ) 天才は忘れた頃にやってくる ( 奥乃博 ) 月 7 日本日のメニュー. vector ( ベクタ ). Sorting ( 整列 ) 3. hashing( ハッシュ法 ) 4. アンケート ( 最後の 5 分 ) 配布する用紙に名前を記入して下さい回収は学生同士で教員は一切タッチしません ( 退場!) Sorting ( 整列 ) 内部整列 (internal sorting) データはすべて主記憶上に置いて整列. 作業領域を極力減らす. 比較回数を極力減らす外部整列 (external sorting) 外部の記憶装置を用いて整列 3. 主記憶と補助記憶との間でのデータ転送回数を極力減らす 3

2 Internal Sorting( 内部整列 ) 逐次入力型挿入ソート (insertion sort) ヒープソート (heap sort) バッチ型クイックソート (quick sort) バブルソート (bubble sort) その他 ( 外部整列と共通 ) マージソート (merge sort 併合ソート) 4 クイックソートの補足 pivotのとり方は工夫が必要すでに並んでいる場合には最小あるいは最大要素を pivot に取ると最悪適切な pivot を取れば Θ( nlog n) リスト使用の場合は pivot 選択がリスト辿りが必要コストが重いベクタ使用の場合にはコストが軽い 5 新しいデータ型 : ベクタ (vector) データの並びを表現するデータ型 #( 要素 0 要素 n- ) インデックス (index) は0から始まる (0-origin) 要素は任意のデータいわゆる次元配列 (array) Constructor( 構築子 ) (make-vector サイズ [ データ ]) (vector データ 0 データ n- ) (list->vector リスト ) 6

3 新しいデータ型 : ベクタ (vector)( 続 ) Selectors( 選択子 ) (vector-ref ベクタインデックス ) その他 (vector-length ベクタ ) サイズを返す (vector-set! ベクタインデックスデータ ) (vector->list ベクタ ) 入出力は #( 3 4 5) 7 ベクタ (vector) の例 (define y (make-vector 5)) #(() () () () ()) (define x #( 3 4 5)) #( 3 4 5) (vector-length x) 5 (vector-ref x ) 3 (vector-set! x 3 8) #( 3 8 5) x #( 3 8 5) (vector-set! x 0 'foo) #(foo 3 8 5) 8 ピープ (heap) というデータ構造ヒープとは分木の特殊形ヒープの高さを h とすると. 高さ h- までは完全分木. 高さ h の葉は左詰 3. 親ノードの値 v p と子ノードの値 v c とすると h h- v p pred v c が成立 pred は比較ベクタで実現する 0 3

4 ピープ (heap) のベクタ表現ヒープの高さを h とすると高さ h- までは完全分木高さ h の葉は左詰ベクタで実現する親のインデックスを i サイズ0 子のインデックスは i, i+ i i i+ i i i+ h h- ピープの諸演算手続き (define (make-heap maxsize) (let ((heap (make-vector (+ maxsize )))) (vector-set! heap 0 0) heap ))) (define (heap-size heap) (vector-ref heap 0)) (define (heap-left-child n) (* n )) (define (heap-right-child n) (+ (* n ) )) (define (heap-parent n) (quotient n )) (define (heap-top heap) (vector-ref heap )) (define (heap-size-set! heap n) (vector-set! heap 0 n) ) 0サn n n+ イズ3 insert-heap ( ピープに要素挿入 ) (define (insert-heap heap element pred) (let ((n (+ (heap-size heap) ))) (vector-set! heap n element) (heap-size-set! heap n) (sift-up heap n element pred) element )) sift-up では高さがつずつ減少 4 4

5 sift-up(heap 修復 ) (define (sift-up heap from element pred) (if (<= from ) element (let ((parent (heap-parent from))) (let ((value (vector-ref heap parent))) (cond ((pred value element) element) (else (vector-set! heap from value) (vector-set! heap parent element) (sift-up heap parent element pred ))))))) 回繰り返すと高さが減少要素数を n とすると計算量は Θ(log n) 5 最大要素の抽出と heap 修復 (define (heap-extract-top heap pred) (let* ((value (heap-top heap)) (n (heap-size heap)) (element (vector-ref heap n)) ) (heap-size-set! heap (- n )) (vector-set! heap element) (sift-down heap (- n ) element pred) value )) sift-down では高さがつずつ増加 6 sift-down(heap 修復 ) (define (sift-down heap from to element pred) (let ((left-child (heap-left-child from)) (right-child (heap-right-child from)) ) (if (or (>= from to) (> left-child to)) element (let ((max-child (if (> right-child to) left-child (if (pred (vector-ref heap left-child) (vector-ref heap right-child) ) left-child right-child )))) (let ((max-child-value (vector-ref heap max-child))) (cond ((pred element max-child-value) element) (else (vector-set! heap from max-child-value) (vector-set! heap max-child element) (sift-down heap max-child to element pred )))))))) 7 5

6 ヒープソート (heap-sort) (define (heap-sort records. args) (let ((pred (if (null? args) >= (car args))) (heap (make-heap 00)) (result ()) ) (for-each (lambda (i) (insert-heap heap i pred)) records) (do ((i (length records) (- i )) (result nil) ) ((<= i 0) (reverse result)) (set! result (cons (heap-extract-top heap pred) result ))))) ヒープソートの計算量 Θ( nlog n) 9 ヒープソート (heap-sort) の正しさベクタ x のヒープ成立条件 heap(m,n) i m +, n x i x i [ ] [ ] [] sift-down では実行前 : heap(,n) の成立は? 実行後 : heap(,3) が成立 i 回目の sift-down では実行前 :heap(,k) は成立, heap(k,n)? 実行後 :heap(k,k+) が成立つまり, heap(,k+) が成立 0 ヒープソート (heap-sort) の正しさ () ベクタ x のヒープ成立条件 heap(m,n) i m +, n x i x i [ ] [ ] [] sift-up では実行前 :heap(,n) 成立, heap((n+)/,n+) だけが? 実行後 :heap((n+)/4,(n+)/) は? i 回目の sift-up では実行前 :heap(k/,k)? 他は成立実行後 :heap(k/,n) 成立, heap(k/4,k/)? 6

7 バブルソート (bubble sort) (define (bubble-sort records. args) (let ((pred (if (null? args) >= (car args))) (size (vector-length records)) ) (do ((i 0 (+ i ))) ((>= i size) records) (do ((j (- size ) (- j )) (data nil) ) ((<= j i)) (set! data (vector-ref records j)) (cond ((pred data (vector-ref records (- j )) ) (vector-set! records j (vector-ref records (- j )) ) (vector-set! records (- j ) data) )))))) バブルソート (bubble sort) 実行トレースバブルソート (bubble sort) の計算量回ごとに敷居 ( ) がつずつ減る n i= ( i ) = n( n ) Θ( n ) 4 7

8 シェルソート (Shell sort) バブルソート : 隣接データを比較 h= 飛び飛び (h) に比較 h k = 3h k- +,, の時 e.g., 40, 3, 4, Θ( n.5 ) 5 マージソート ( 併合ソート merge sort) ソート済みのデータを前からマージ ( 併合 ) リスト版ベクタ版計算量は両方のデータのスキャンのみ m 個のデータと n 個のデータとすると Θ( m + n) 空間計算量も余分に Θ( m + n) 7 内部マージソート (In-place merge sort) 分割統治型ラン (run) と言う Θ( nlog n) 8 8

9 Sorting( 整列 ) のまとめ選択ソート (selection sort) 挿入ソート (insertion sort) シェルソート (Shell sort) h k = 3h k- +,, の時 Θ( n ) Θ( n ) Θ( n 定数小.5 クイックソート (quick sort), 分割統治法 (devide and conquer) 平均 Θ( n log n) 最悪 Θ( n ) ヒープソート (heap sort) 常時 Θ( nlog n) マージソート (merge sort) 常時 Θ( nlog n) ) 30 Sorting( 整列 ) のデモ Java のデモプログラム ~okuno/lecture/05/introalgds/ 3 Sort( 整列 ) 済ベクタの探索分探索 (binary search) > = < 比較 > = < > = < 分探索の計算量 Θ(log n) 33 9

ハッシュ法 (hashing) 探したいデータの範囲膨大例 : 最大 0 文字の単語 50 文字とすると組合わせの数は 0 log(50

(hasing) を使用 0 50 = 7 6 0 0 37 辞書とハッシュ表 apocalypse 黙示 apocope 語尾消失 (

apocalypse apocope apocrypha apodosis apogee ッシュ値エントリハ apogee 6 4 5 0

10 ハッシュ法 (hashing) 探したいデータの範囲膨大例 : 最大 0 文字の単語 50 文字とすると組合わせの数は 0 log(50 ) 0( log ) 7 ところが実際の単語数は高々ベクタ ( 配列 ) で単語を管理すると疎すかすかの配列ハッシュ法 (hasing) を使用 0 50 = 辞書とハッシュ表 apocalypse 黙示 apocope 語尾消失 ( 空 ) ハッシュ apocrypha apodosis directaccess table 聖書外典帰結節遠地点 apocalypse apocope apocrypha apodosis apogee ッシュ値エントリハ apogee apogee apocalypse apocrypha apodosis apocope 遠地点 38 ハヤシライスを知っていますか hashed beaf 語源は同じ 39 0

11 ハッシュ法 (hashing) キーの値の探索なしにアクセスハッシュ関数 (hash function) キーハッシュ値 ( 整数 ) ハッシュ表 (hash table) サイズ M 占有率 (load factor)α データ量 N α = N M 異なるキーに対してハッシュ値が同じハッシュ値の衝突 (collision) 40 ハッシュ関数 (hash function) 設計の指針 : ランダム性を有するものキー : x = a a L key ( x) = m 例 : キーから例 : 文字列から整数への写像 n i= h ( x) a n code( a ) mod M i 例 3: m の中央部分の logm 桁分を使用 h ( x) h3 ( x) m mod M K where constant K such that MK m mod M N 4 ハッシュ法の基本手続き挿入 (insert) hash 表に key を持つデータを挿入検索 (member) hash 表から key でデータを検索削除 (delete) hash 表から key を持つデータを削除 4

12 ハッシュ値衝突 (collision) 対処法チェイン法 (chaining, separate chaining, 連鎖法内部ハッシュ法 ) 開番地法 (open addressing, オープン法外部ハッシュ法 ). 線形走査法 (linear probing). 万能ハッシュ法 (universal hashing) 3. 重ハッシュ法 (double hashing) h, gとすると h(x), h(x)+g(x), h(x)+g(x), h(x)+3g(x), 43 dog curb bird チェイン法 bird ハッシュ値の衝突 Backet( バケツ ) を作りつないで行くチェイン法の平均最悪計算量. 挿入 Θ(N). 検索 Θ(N) 3. 削除 Θ(N) 44 内部ハッシュ法 (internal hashing) ハッシュ関数 h i α = N < 占有率 α M エントリに状態を導入 /deleted/key( データ ). 挿入 : /deleted というフラグのあるエントリに入れる. 検索 : /deletedまで探す 3. 削除 : deletedというフラグを立てる deleted キーキーデータデータ 45

13 線形走査法 (linear probing) ハッシュ関数 h 衝突発生時 h i h+i mod M 挿入 /deleted というフラグのあるエントリに入れる検索 /deleted まで探す削除 deleted というフラグを立てる 46 万能ハッシュ法 (universal hashing) ハッシュ関数 h, ハッシュ関数をランダムに選択挿入 /deleted というフラグのあるエントリに入れる検索 /deleted まで探す削除 deleted というフラグを立てる 47 重ハッシュ法 (double hashing) ハッシュ関数 h, g 衝突発生時 h i h+ig mod M 挿入 /deleted というフラグのあるエントリに入れる検索 /deleted まで探す削除 deleted というフラグを立てる 48 3

14 線形走査法 (linear probing) の例. h(dog)=. h(kyoto)=4 3. h(univ)=0 4. h(informatics)= 5. h(sicp)=3 6. h(test)= 線形走査法の挿入の計算量. n 個のデータが格納 n+ 個目のデータを挿入するときにh i (x) がi 回目で空いている確率 n n n n i + L M M M M i +. 空きセルを見つけるまでの比較回数 M i n( n ) L( n i + ) n M + + = i= M ( M ) L( M i + ) i= M M n 3. ハッシュ表にN 個のデータを挿入する手間は N M M N M dx = M log M x e 0 n= 0 n M N + M 50 線形走査法の挿入の計算量 ( 続 ) 4. 回あたりの平均の挿入の手間は M M loge loge( α) N M N + α Computational Complexity /(-α) -/α log (-α) Load Factor load factor α α loge( α) α 5 4

15 線形走査法の検索の計算量. deleted はないものと仮定. 表にキーがない時は n=n の挿入と同じ M = M N α 3. 表にキーがある時 M M loge loge( α) N M N + α 4. 削除も検索と同じ 5. 上記の解析は一様ハッシュ (uniform hashing) を仮定 : キーの探索列ランダム 5 Computational Complexity /(-α) -/α log (-α) Load Factor load factor α α loge( α) α 53 宿題はありません期末テスト健闘を期待します必修課題 3もお忘れなく随意課題の提出でランクアップをテスト : 月 7 日 3 限 56 5

Microsoft PowerPoint - IntroAlgDs ppt [互換モード]

Microsoft PowerPoint - IntroAlgDs ppt [互換モード] アルゴリズムとデータ構造入門 -4 008 年月 5 日アルゴリズムとデータ構造入門 Sorting( 整列 ) Hashing( ハッシュ法 ) 奥乃博祝成人の日年前の7 日阪神淡路大震災犠牲者死者だけで6434 人天災は忘れた頃にやってくる ( 寺田寅彦 ) 天才は忘れた頃にやってくる ( 奥乃博 ) (Asahi.com より転載 ) 月 5 日本日のメニュー. vector ( ベクタ