コンピュータアルゴリズム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)
配列(四角を横に並べる)
オブジェクト(長方形を縦に並べる)
n:
p:
q:
r:
n:
p:
q:
r:
単なる慣習：どちらも実際にはメ
モリ上の連続したアドレスを占め
ている
配列やオブジェクトの要素が他のオブジェクトや配列を参照
している(C/C++のポインタ型, Javaの参照型，配列型)場合，
C/C++:
Java:
それを矢印で表す
n:
p:
q:
r:
struct A {
int n;
int * p;
A * q;
int r;
};
class A {
int n;
int[] p;
A q;
int 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]に要素が入っている．残りは「空き部屋」
n
capacity
a
(C/C++)
typedef struct ArrayListX {
int capacity;
int n;
X * a;
} ArrayListX;
capacity個
n個
可変長配列の操作の実際
i 番目の要素参照，置き換え: 自明
i 番目となる要素の挿入
配列が満杯だったらより大きな配列を取り直し，中身を新
配列へコピー
もともと i 番目およびそれ以降の要素をひとつずつ後ろへ
ずらす
i 番目の要素の削除
もともと i + 1 番目およびそれ以降の要素をひとつずつ前
へずらす
速い・遅い操作は?
i 番目となる要素の追加
特に，末尾への追加
特に，先頭への追加
i 番目の要素の削除
特に，末尾からの削除
特に，先頭からの削除
i 番目の要素の参照・置き換え
O(
O(
O(
O(
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)
n
つまり平均すればO(1) 償却計算量(amortized
complexity) O(1)ともいう
速い・遅い操作再掲
i 番目となる要素の追加
特に，末尾への追加
特に，先頭への追加
i 番目の要素の削除
特に，末尾からの削除
特に，先頭からの削除
i 番目の要素の参照・置き換え
O(
O(
O(
O(
O(
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)
head
tail = c;
tail
else
head.prev = c;
head = c;
}
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)
head
l->tail = c;
tail
else
l->head->prev = c;
l->head = c;
}
x
速い・遅い操作は?
i 番目となる要素の追加
O( )
特に，末尾への追加
O( )
特に，先頭への追加
O( )
i 番目の要素の削除
O( )
特に，末尾からの削除
O( )
特に，先頭からの削除
O( )
i 番目の要素の参照・置き換え 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間に全順序関係が存在すること，それに基づく
不等号比較ができることを仮定する
挿入されたあと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
2 4 5 7 8 10 12 13
q
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) {
remove(k) {
i = find_idx(k);
i = find_idx(k);
if (i 0 && a[i] == k) return b[i];
if (i 0 && a[i] == k) {
else not_found;
a.remove(i);
}
b.remove(i);
put(k, v) {
} else {
i = find_idx(k);
error /* no such key */
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);
}
}
練習問題
ホーア論理を用いてfind_idxの正しさを証明せよ
特に，ループ不変条件を見出せ
計算量 O(log n)を示せ
{ ????? }
while (q – p 2) {
{ ????? }
int c = (p + q) / 2;
if (a[c] k) p = c;
else
q = c;
}
{ ????? }
配列を用いた探索の計算量
検索
挿入
削除
線形探索
O( )
2分探索
O( )
amortized
O( )
O( )
O( )
O( )
どちらにしてもこの方法での連想記憶はそれほど有用ではない
木構造を用いた連想記憶
リスト (linked list)
...
...
...
...
...
木構造(tree)
...
配列 (array)
各データ構造の特徴
配列
すべてのデータに「一撃で」(O(1)で)アクセスできる
挿入・削除が面倒
要素 アドレスの「単純な」対応が原因
リスト
途中データのアクセスに「ポインタの追跡」時間がかかる
(O(n))
(先頭末尾への)挿入・削除が容易・効率的
「データのおき場所(アドレス)は自由，それをポインタでつ
なぐ」方式に起因
木構造
両者の「中間」
木構造の基本アイデア
木構造の子供の数が適度(2以上，ある一定値以下)ならば，
データにたどり着くまでのポインタの追跡 O(log n)
挿入・削除時のデータの書き換え O(log n)
とできるのではないか???
2分木を用いた連想記憶
2分木(binary tree) : 子供の数が0, 1, 2のいずれかの木
各ノードにkey valueを格納
Java:
class Node {
Key k;
Value v;
Node left;
Node right;
};
“learned”
3
C++:
class Node {
Key k;
Value v;
Node * left;
Node * right;
};
“I”
2
“about”
4
...
...
“today”
1
“searching”
5
...
...
効率的な探索のための2分木の構成
k
2分探索木(binary search tree)
<k
>k
2分探索(binary search)とは
似て非なる言葉
k
木構造の亜種
k >k
リーフ(葉)以外の子供に(key, value)を格納するか否か
否の場合，途中ノードは，k (閾値)だけを格納する
m分木
子供の数が0, 1, …, m – 1
ノードひとつに複数(> 1)個の(key, value)を格納
k1 , k 2
3分木
以下の話はこれらの選択によらず共通
< k1
k1 x < k2
k2
正しい2分探索木の状態
10, 20, 30, 40, 50, 60を格納している正しい2分探索木の状態
例
30
10
10
20
50
30
20
40
60
40
50
60
keyの集合が同じでも複数の表現方法(内部状態)があることに注意
2分木中でのデータの並び方
7
3
11
1
0
5
2
左の子すべて;
自分;
右の子すべて;
が「小さい順」
4
9
6
8
13
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
右の子で同様
練習:
1. コードにしてみよ
2. 再帰呼び出しを使わずにループで書いてみよ
k
>k
2分木に対する操作: 挿入
あるノード(k)を基点とする key : value の組の挿入
key = k そのノードに挿入(上書き)
key < k
左の子がいない 左の子を新ノードとして作る
左の子がいる 左の子で再帰呼び出し
k
key > k
右の子で同様
k
k
key
<k
>k
クイズ: 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
>k
削除(2)
両方の子がいる場合(再びnは根でないことを仮定)
pの子を誰にするのが手っ取り早いか?
...
p
n
<k
>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
1
2
key
val
.
.
.
H–1
あるキーがどのリストに入るかの決め方: 「ハッシュ関数」と
いう適当な, 0, …, H – 1 (Hは配列の要素数)の値をとる関数
で決める
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)に「ちらばる
」ようにする
つまりなるべく「どんなキーが来ても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)
参照がO(1)であることをのぞけば，平衡木に勝るものではな
いが，平衡木よりも簡単
優先度キューのデータ構造：
部分順序つき木(Partially Ordered Tree)
部分順序つき木
構造としては2 (m)分木と同じだが，不変条件が違う
不変条件(最小値に興味がある場合) :
k
親のkey 子のkey
k
2分木よりも自由度が高い
木の形を「規則正しく」維持するのが容易
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
c
f
x h
0 1 2 3 4 5
b
e
g
d
i
k
j
6 7 8 9 10 11
a c b f e d j x h g i k
ヒープに対する操作:
最小値の参照
根(a[0])を見ればよい! (O(1))
値の挿入
入れた後の木の形はきまっている
まずは追加されるノードに入れてしまう
あとは大小関係を満たすべく要素の入れ替えを行う
6
9
8
8 交換
新ノード
6
9
最小値(根)の削除
再び，削除後の木の形は決まっている
右下隅を消す(根に移動する)しかない
あとは挿入時と同様のつじつまあわせ
10
6
6
6
9
10
7
9
7
7
9
10
ヒープ操作計算量
挿入・削除
木の深さ分の値の入れ替えしかおこらない
故に O(log n)
ヒープソート
クイズ: ヒープがあれば計算量O(n log n)で整列ができる
2分木の場合と異なり，最悪でO(n log n)
© Copyright 2024 ExpyDoc
