コンピュータアルゴリズム2 6. コンテナの実現 田浦 http://www.logos.ic.i.u-tokyo.ac.jp /~tau/lecture/software/

Part III : コンテナの実現

実現方法を語る上での目標と仮定 目標: 各操作の計算量をコンテナ中の要素数や操作の回数の関数として見積もる それをできるだけ小さくする 「万能」コンテナ すべての操作を一定時間で行える は存在しない(存在すればコンテナは一種類でよかった!) 仮定(使える道具) 配列 固定の要素を持ったレコード(以降オブジェクト) C : struct, C++ : struct, class, Java : class 配列，オブジェクトの動的な生成(メモリ確保)が定数時間で行える C : malloc, C++, Java : new 配列，オブジェクトの要素の参照は定数時間で行える

頭の使い方：データ構造 同じ状態(同じ数列や集合)を表すのにも，計算機内(メモリ内)での「表現方法，配置方法」は色々ある 要するに言われたこと(挿入，削除，参照)が正しくできれば文句はない この表現方法や配置方法のことを「データ構造」という データ構造の作り方で各操作の得手・不得手が決まる たとえば普通の配列も一種のデータ構造 配列は指定された要素の参照が得意だが，新しい要素の追加は苦手

データ構造を図示する際の約束(1) 配列(四角を横に並べる) オブジェクト(長方形を縦に並べる) 配列やオブジェクトの要素が他のオブジェクトや配列を参照している(C/C++のポインタ型, Javaの参照型，配列型)場合，それを矢印で表す 単なる慣習：どちらも実際にはメモリ上の連続したアドレスを占めている n: p: q: r: C/C++: struct A { int n; int * p; A * q; int r; }; Java: class A { int n; int[] p; A q; int r; }; n: p: n: q: p: r: q: r:

データ構造を図示する際の約束(2) 特に null ポインタ(C/C++ の0, またはNULL, Javaのnull)は，矢印を書かないか，以下のように明示する n: p: q: r: 実際には p に null (0)が代入されている状態

列 理想的には以下をすべて効率的に行いたい i 番目となる要素の追加挿入 i 番目の要素の削除 i 番目の要素の参照，置き換え

配列を基にした列(可変長配列) JavaのArrayList, C++のvector 常に下図のような状態を保つ aはcapacity個の要素を格納できる配列 a[0] ... a[n-1]に要素が入っている．残りは「空き部屋」 capacity個 n capacity a (C/C++) typedef struct ArrayListX { int capacity; int n; X * a; } ArrayListX; n個

可変長配列の操作の実際 i 番目の要素参照，置き換え: 自明 i 番目となる要素の挿入 配列が満杯だったらより大きな配列を取り直し，中身を新配列へコピー もともと i 番目およびそれ以降の要素をひとつずつ後ろへずらす i 番目の要素の削除 もともと i + 1 番目およびそれ以降の要素をひとつずつ前へずらす

速い・遅い操作は? i 番目となる要素の追加 O( ) 特に，末尾への追加 O( ) 特に，先頭への追加 O( )

配列があふれたらどのくらい大きくすべきか? capacity = capacity + 1 ? capacity = capacity + 10 ? capacity = capacity * 2 ? もちろん(未来に何が行われるかわからない限り)どちらがいいと断定はできないが，「+ 一定値」ではなく「* 一定値」とすることには重要な意味がある

配列伸張方式による差 連続して n 回の「末尾への追加」が行われた場合の「合計」の計算量を考える ここでは必要な要素のコピー回数で計算量を見積もる 配列の最初の大きさは1とする + 1 の場合 (+10, +100, ...でも結果は同じ) 1 + 2 + 3 + 4 + ... + (n – 1)  O(n2) * 2 の場合 (*1.5, *1.2, ... でも結果は同じ) 1 + 2 + 4 + 8 + ... + 2m  2m+1 – 1  O(n) つまり平均すればO(1) 償却計算量(amortized complexity) O(1)ともいう  n

速い・遅い操作再掲 i 番目となる要素の追加 O( ) 特に，末尾への追加 O( ) (amortized O(1))

リンクリストを基にした列 実例: Java LinkedList, C++ list, Python リスト 追加は必ず新しい要素を入れる「箱」を新しく割り当てて行う head tail (C/C++) typedef struct Cell { struct Cell * next; struct Cell * prev; X value; } Cell; typedef struct LinkedListX { Cell * head; Cell * tail; } LinkedListX;

挿入操作の実際 (Java) void add_to_front(X x) { Cell c = new Cell(); c.x = x; c.prev = null; c.next = head; if (head == null) tail = c; else head.prev = c; head = c; } head tail x

挿入操作の実際 (C) void add_to_front(LinkedListX * l, X x) { Cell * c = (Cell *) malloc(sizeof(Cell)); c->x = x; c->prev = null; c->next = head; if (l->head == null) l->tail = c; else l->head->prev = c; l->head = c; } head tail x

速い・遅い操作は? i 番目となる要素の追加 O( ) 特に，末尾への追加 O( ) 特に，先頭への追加 O( ) 注: 0, 1, ..., n – 1番目の要素を順に参照する O( ) cf. Java, C++のiterator

練習課題(1) 配列を用いた可変長配列(JavaのArrayList, C++のvectorに相当するデータ構造) リンクリストを用いた可変長配列(JavaのLinkedList, C++のlistに相当するデータ構造) を自分で作ってみよ(C, C++, またはJavaで) 先頭・末尾への挿入・削除 任意の値の参照 挿入するデータの型は決めてよい(文字列など) 以下の性能測定をしてgnuplotなどでグラフ表示せよ N個のデータを末尾に挿入する N個のデータを末尾に挿入後，それらを先頭から取り出す 多数のデータ挿入後に，ランダムな要素の参照をN回

クイズ(1) ファイルを全行読んで，反対向きに表示するプログラムを書くとする．やってはいけないのは? 案1: LinkedListを用いて，行を先頭に追加 していく．全部追加後，前からprint 案2: ArrayListを用いて同様 案3: LinkedListを用いて，行を末尾に追加 ．全部追加後，後ろからprint 案4: ArrayListを用いて同様

擬似コード 案1, 2 {Linked,Array}List<String> L = new {Linked,Array}List<String>(); for (ファイル中の各 line) L.add(0, line); for (line : L) print line; 案3, 4 {Linked,Array}List<String> L = new {Linked,Array}List<String>(); for (ファイル中の各 line) L.add(line); for (i = 0; i < 行数; i++) print L.get(行数 – i – 1);

クイズ(2) i 番目の要素の参照 O(1) 先頭・末尾への追加 amortized O(1) 先頭・末尾からの削除 O(1) を達成する方法は? C++ dequeがそれをやっている模様

練習課題(2) 配列用のクイックソートをそのままLinkedListに置き換えると計算量はどうなるか(a[i]を単純にget(a, i)に置き換える)? LinkedList用のO(n log n)クイックソートを書け アルゴリズム自体の考え方は同じ コーディングを気をつけなくてはいけないだけ

写像，連想記憶 Java : XXXMap, STL: map, Python : 辞書 以下をすべて効率的に行いたい 対応 key  value の追加 Java : m.put(key, value) Python/STL : m[key] = value key に対する対応 key  X の削除 Java : m.remove(key) Python/STL : del m[key] key に対応する value の探索 Java : value = m.get(key) Python/STL : value = m[key]

keyに関する前提 keyは以下を満たす任意の値 key同士の等号比較ができる(当然の条件)

連想記憶の実現法 使われているデータ構造による分類 配列や列(リストなど) 木構造 ハッシュ表

配列を用いた連想記憶 連想記憶 = keyの列とvalueの列 Java: class map { ArrayList<K> a; ArrayList<V> b;}; 二通りのやり方: その1: 組k  vの挿入は末尾に行う (amortized O(1)) put(k, v) { a.add(k); b.add(v); } 探索は線形探索 O(n) その2: つねに整列 (a0 < a1 < a2 < ... )しておく 探索は2分探索 O(log n) 挿入は ai  k < ai+1なる i を見つけて挿入 O(n) キーの列 値の列

2分探索 入力: 整列された配列 a[0], ..., a[n – 1] i 0  i < n–1  a[i] < a[i+1] 見つけたい key k 出力 (以下のi): 下にある例外ケースを除き， a[i]  k < a[i+1] を満たすi (0  i < n – 1) いくつかの例外ケース n = 0 ならば i = –1 n > 0 かつ k < a[0] ならば i = –1 n > 0 かつ a[n – 1]  k ならば i = n – 1

2分探索の基本アイデア 求める i が存在する可能性のある範囲 を狭めていく(挟みうち) a[p]  k < a[q]を保ちながらループ(不変条件) p q 2 4 5 7 8 10 12 13 90 98

2分探索 コード int find_idx(k) { n = a.size(); if (n == 0) return –1; if (k < a[0]) return –1; if (a[n–1]  k) return n–1; // a[0]  k < a[n–1], n > 0 int p = 0; int q = n–1; while (q – p  2) { // a[p]  k < a[q], q – p  1 int c = (p + q) / 2; if (a[c]  k) p = c; else q = c; } // a[p]  k < a[q], 1  q – p < 2 // a[p]  k < a[p+1] return p;

探索・挿入・削除 get(k) { i = find_idx(k); if (i  0 && a[i] == k) return b[i]; else not_found; } put(k, v) { i = find_idx(k); if (i  0 && a[i] == k) { a.replace(i, k); b.replace(i, v); } else { a.add(i+1, k); b.add(i+1, v); } } remove(k) { i = find_idx(k); if (i  0 && a[i] == k) { a.remove(i); b.remove(i); } else { error /* no such key */ } }

練習問題 ホーア論理を用いてfind_idxの正しさを証明せよ 特に，ループ不変条件を見出せ 計算量 O(log n)を示せ { ????? } while (q – p  2) { { ????? } int c = (p + q) / 2; if (a[c]  k) p = c; else q = c; } { ????? }

配列を用いた探索の計算量 線形探索 2分探索 検索 O( ) O( ) 挿入 amortized O( ) 削除 どちらにしてもこの方法での連想記憶はそれほど有用ではない

木構造を用いた連想記憶 リスト (linked list) ... ... ... 配列 (array) ... ... ... 木構造(tree)

各データ構造の特徴 配列 すべてのデータに「一撃で」(O(1)で)アクセスできる 挿入・削除が面倒 要素  アドレスの「単純な」対応が原因 リスト 途中データのアクセスに「ポインタの追跡」時間がかかる(O(n)) (先頭末尾への)挿入・削除が容易・効率的 「データのおき場所(アドレス)は自由，それをポインタでつなぐ」方式に起因 木構造 両者の「中間」

木構造の基本アイデア 木構造の子供の数が適度(2以上，ある一定値以下)ならば， データにたどり着くまでのポインタの追跡 O(log n) とできるのではないか???

2分木を用いた連想記憶 2分木(binary tree) : 子供の数が0, 1, 2のいずれかの木 各ノードにkey  valueを格納 “learned”  3 Java: class Node { Key k; Value v; Node left; Node right; }; “I”  2 “today”  1 C++: class Node { Key k; Value v; Node * left; Node * right; }; ... ... “about”  4 “searching”  5 ... ...

効率的な探索のための2分木の構成 k 2分探索木(binary search tree) < k > k

木構造の亜種 k  k > k リーフ(葉)以外の子供に(key, value)を格納するか否か m分木 子供の数が0, 1, …, m – 1 ノードひとつに複数(> 1)個の(key, value)を格納 以下の話はこれらの選択によらず共通 k1, k2 3分木 < k1 k1  x < k2  k2

正しい2分探索木の状態 10, 20, 30, 40, 50, 60を格納している正しい2分探索木の状態例 30 10 20 10 50 keyの集合が同じでも複数の表現方法(内部状態)があることに注意

2分木中でのデータの並び方 7 3 11 1 5 9 13 2 4 6 8 10 12 14 list_elems() { if (left != null) left.list_elems(); print key; if (right != null) right.list_elems(); } 左の子すべて; 自分; 右の子すべて; が「小さい順」 これですべてのkeyが小さい順にprintされる

2分木に対する操作: 探索 あるノード(k)を基点とするkeyの探索 key = k  見つかった key < k  左の子がいない(null)  not found 左の子がいる  左の子で再帰呼び出し key > k  右の子で同様 k < k > k 練習: 1. コードにしてみよ 2. 再帰呼び出しを使わずにループで書いてみよ

2分木に対する操作: 挿入 あるノード(k)を基点とする key : value の組の挿入 key = k  そのノードに挿入(上書き) 左の子がいない  左の子を新ノードとして作る 左の子がいる  左の子で再帰呼び出し key > k  右の子で同様 k < k > k k k key

クイズ: 2分木は本当にO(log n)か? つまり，探索，挿入ともデータ数nに対して O(log n)時間か? amortized O(log n) (i.e., n個挿入するのにO(n log n)か? n個のデータを入れるのに最悪のケースは?

実はO(n)  遅いだけでなく，再帰呼び出しは危険(スタックオーバーフロー) ループに書き換える必要がある(練習) ただし，「不運な場合」は少ない クイックソートの不運な場合と類似

クイズ(数学) n要素のクイックソート, 空の2分木へのn要素の挿入の「平均」計算量はO(n log n)か? 平均計算量 現れ得るデータがみな等確率で現れるとした時の平均 簡単のため全データが異なるとする クイックソートや2文木の計算量は要素間の大小関係だけで決まるから, n要素の順序関係n!通りが等確率で現れると仮定してよい n要素の配列を作ったとき不運なデータができる確率は無視できるほど小さい(n  のとき 0)か?

2分木に対する操作: 削除 key の削除 削除すべきノード(n)を特定するところまでは探索と同じ 主な問題はnを削除した後の木構造の維持 「データ構造の不変条件」の回復 n < k > k

削除(1) 左(右)の子がいない場合 注: nはルートではない(親がいる)と仮定している ... ... p p n n > k

削除(2) 両方の子がいる場合(再びnは根でないことを仮定) pの子を誰にするのが手っ取り早いか? ... p n < k

注: nが根だったら? 問題: 削除の結果，木の根が入れ替わったら，どこのポインタを書き換えればいいのか? そのようなポインタは木の外から生えていて，どこを書き換えたらいいのか一般にはわからない 解決策: 木のノードを直接さすことはしない Java: class tree { node root; } C++: class tree { node * root; }

クイズ 整列に2分木が使える

平衡木 挿入・削除・探索がO(log n)でできることを保証するには? 子供の大きさが極端に偏らなけれ(ある「平衡条件」を満たせ)ば良い 挿入・削除の結果「平衡条件」がくずれたら直す いくつかの種類 AVL木 (左右の子の高さの差が0または1以内) Red-Black木 B木 根・葉以外の頂点の子供の数が m/2以上 m 以下 例: 2以上3以下(2-3木)，3以上5以下 葉の子供の数はもちろん0 葉までの深さはどこも同じ 教科書(石畑やCormen et al.)で自習してください

ハッシュ表を用いた連想記憶 実はシンプルかつ，実践的にも速い，最もpopularな方法 4学期の授業でやった(んですよね?) 教科書(石畑本)で復習して下さい

ハッシュ表のデータ構造 基本は各要素がkey, valueのリストになった配列 ハッシュ表 あるキーがどのリストに入るかの決め方: 「ハッシュ関数」という適当な, 0, …, H – 1 (Hは配列の要素数)の値をとる関数で決める 1 2 . H – 1 ハッシュ表 key val

typedef struct list_node { struct list_node. next; K key; V val; } typedef struct list_node { struct list_node * next; K key; V val; } * list_node_t; typedef struct hash_table { int capacity; list_node_t * a; } * hash_table_t; hash_table list_node

探索・挿入・削除 V search(table, key) { h = hash(key); return search_list(table->a[h], key); } insert(table, key, val) { h = hash(key); table->a[h] = cons_list(table->a[h], key, val); } remove(table, key) { h = hash(key); table->a[h] = remove_list(table->a[h], key); }

ポイント 多数のキーが十分多くのエントリ(0, 1, …, H – 1)に「ちらばる」ようにする 「最悪」の場合は全部のキーが一つのエントリに固まる場合で, 通常の列からの探索と変わらない N個のデータに対して, O(N)のエントリを用意し, ハッシュ関数がそれらを「均等に」ばらまいてくれるとすると 探索 O(1), 挿入 amortized O(1), 削除 O(1)が達成できる

優先度キュー 以下の操作が可能なコンテナ keyの挿入 (key間に定義されるある全順序に従った)最小(大)のkeyの参照 同，取り出し(削除) 探索はできなくてもいいことに注意

動機確認 整列されていない配列を用いた場合の計算量 挿入: O( ) 最小値参照: O( ) 最小値取り出し: O( ) 整列された配列の場合は? 2分木・平衡木を用いた場合は? ハッシュ表は役に立たない

これから述べる優先度キューの計算量 挿入: O(log n) 最小値参照: O(1) 最小値取り出し: O(log n)

優先度キューのデータ構造： 部分順序つき木(Partially Ordered Tree) 構造としては2 (m)分木と同じだが，不変条件が違う 不変条件(最小値に興味がある場合) : 親のkey  子のkey 2分木よりも自由度が高い 木の形を「規則正しく」維持するのが容易 k k k

完全2分木，ヒープ 完全2分木 葉以外のすべてのノードの子供の数が2 n段の完全2分木のノード数 2n – 1 ヒープ「以下を満たす部分順序つき木」 完全2分木から0個以上の葉を右端から取り除いた形 任意要素数のヒープがあり，要素数が決まれば形が一意に決まる 欠けているノード 完全2分木(4段) 要素数12のヒープ

ヒープの実際の表現 (形があまりに規則的なので)ポインタを使う必要がない 内容(key)のみを配列に格納 a[i] の左の子 a[2 * i + 1], 右の子 a[2 * i + 2] 注: 配列の添え字は0からとしている さらなる特典: 子から親もわかる a[i]の親 a[(i – 1) / 2] (i > 0) a 0 1 2 3 4 5 6 7 8 9 10 11 c b a x h f i g e c j k d b f e d j x h g i k

ヒープに対する操作: 最小値の参照 根(a[0])を見ればよい! (O(1))

値の挿入 入れた後の木の形はきまっている まずは追加されるノードに入れてしまう あとは大小関係を満たすべく要素の入れ替えを行う 6 6 9 8 交換 8 9 新ノード

最小値(根)の削除 再び，削除後の木の形は決まっている 右下隅を消す(根に移動する)しかない あとは挿入時と同様のつじつまあわせ 10 6 7 9 7 9 7 9 10

ヒープ操作計算量 挿入・削除 木の深さ分の値の入れ替えしかおこらない 故に O(log n)

ヒープソート クイズ: ヒープがあれば計算量O(n log n)で整列ができる 2分木の場合と異なり，最悪でO(n log n)