コンピュータソフトウェア

コンピュータソフトウェア
5. コンテナと探索
田浦
http://www.logos.ic.i.u-tokyo.ac.jp
/~tau/lecture/software/
コンテナとは?



容器: 多数のデータを収納(contain)するデータ
 「たくさんのデータ」を「まとめて扱う」ために有用
最も原始的な例
 配列
標語的には「高度・柔軟な配列(もどき)」を作ることが主題
 どのようなコンテナがあるか?
 どのように問題解決の役に立つか?
 その実現方法は?
応用例：スペルチェッカー


入力
 辞書ファイル: 多数の「正しい」単語を列挙している
 文書ファイル: 文章(単語の並び)
出力
 文書ファイル中の単語で，辞書ファイルに出現しないもの
辞書 abandon
babble
cup
doctor
eat
family
...
文書
Today, I learned about
searching and
containers. ...
スペルチェッカー概要
辞書の構築：
D = 空集合
/* これが「コンテナ」 */
辞書ファイル中の各単語に対し
その単語をDに加えていく
スペルチェック：
文書ファイル中の各単語に対し
その単語がDに「含まれるか否か」検査する
(1) 集合を作る，
(2) 集合に要素を加える，
(3) 集合にある要素が含まれるかどうかを検査する
という操作があればできるようだ
応用例：検索エンジン(索引)


入力
 検索対象となるすべての文書(多数のファイル)
 検索したい単語(通常，多数)
出力
 検索したい単語が現れるファイル(+ ファイル中での位置)
Today, I Today, I
Today, learned
I Today, I
learned
learned
about
Today,
I
learned
about
about
searching
learned
about
searching
Today, I
andsearching
andsearching
It isabout
fun tolearned
containers.
...
searching
and
containers.
...and
learn
about
...
and containers.
containers.
...
algorithms
searching
containers.
...
and
containers. ...
+
“fun”
Today, I Today, I
Today, learned
I Today, I
learned
learned
about
Today,
I
learned
about
about
searching
learned
about
searching
I
searching
andToday,
andsearching
It isabout
fun tolearned
containers.
...
searching
and
containers.
...and
learn
containers.
...
and about
containers.
...
algorithms
searching
containers.
...
and
containers. ...
検索エンジン概要
文書に対する索引の構築：
D = 空の「連想記憶」 /* これがコンテナ．詳細後述 */
すべての文書に対し
その文書中のすべての単語に対し
Dに「単語  出現文書と位置」という関係を追加
検索：
D中で「検索したい単語  ???」という関係を探す
(1) 連想記憶を作る，
(2) 連想記憶に関係 X  Y を加える，
(3) 連想記憶に関係 X  ??? が含まれるかどうかを検査(含ま
れていれば???を見つける)する
という操作があればできるようだ
以降の主題



どのような機能を持つコンテナが必要か?
 配列では何が不足か?
色々なプログラミング言語に備わっているコンテナ
 C, Java, C++, Python
コンテナの実現方法
 配列，構造体，動的メモリ割り当て
Part I: 様々なコンテナ
配列も一種のコンテナである



C:
 int a[10];
/* intを10個 */
 typedef struct complex { double x; double y } complex;
complex c[20];
/* complexを20個格納 */
 int * a = (int *)malloc(sizeof(int) * 30); /* intを30個 */
C++ :
 int * a = new int[30];
Java :
 int[] a = new a[10];
配列も一種のコンテナである



aが配列(またはポインタ)のとき，a[i]はaのi番目の要素を取
り出す
それも非常に効率的に
仕組み: 要素とメモリアドレスの間の単純な関係を作る
 a[0], a[1], ..., をメモリ上で連続したアドレス上に配置
  a[i]のアドレス = a[0]のアドレス + 1要素のサイズ * i
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
配列の何が不足か



index (a[i]のi)が整数に限られる
 「i 番目の要素の値」
はすぐにわかるが，
「値Xを持つ要素は何番目」
はすぐにわからない
 cf. 辞書の例
サイズが生成時に決めたもので固定される
 30要素で生成したら許されるindexは < 30 (なぜ?)
必要なメモリサイズが実際に格納する要素数ではなく，取りう
る最大のindex値で決まる
 a[1], a[1000]の2要素だけを格納するのに，1001個分の領域
が必要
要素の単純な配置から生ずる制限
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
参考: 配列だけで書いたスペル
チェッカ
単語wの検索：
check_word(char * w, char ** D, int n) {
for (i = 0; i < n; i++) {
if (strcmp(w, D[i]) == 0) return;
}
printf(“word %s not found in dictionary\n”, i);
}
 「線形探索(linear search)」という
 計算量:一単語につき O(n) (n : 辞書の大きさ)
コンテナの一般的機能






コンテナ作成
追加
探索
削除
全要素の列挙，生成
動的な伸縮
 要素数に制限がなく，作成時に指定しなくて良い
 必要に応じて使うメモリを増やしていく(動的メモリ確保)
これらをデータ数が大きくなっても「効率よく」行うのが目標
Part II: 実際のプログラミング言語
で提供されるコンテナの実例




Javaクラスライブラリ
C++ Standard Template Library (STL)
Python組み込みコンテナ
ほとんどの言語で似たライブラリが提供されている
 ML
 Ruby
 PHP
 ...
Javaクラスライブラリ



XXXList
 ArrayList, LinkedList
XXXSet, XXXMap
 EnumSet, HashSet, LinkedHashSet, TreeSet
 SortedMap, EnumMap, HashMap, IdentityHashMap,
LinkedHashMap, TreeMap, WeakHashMap
PriorityQueue
使用例
(Java 1.5)
import java.util.*;
class use_sequence {
public static void main(String[] args) {
ArrayList<String> a = new ArrayList<String>();
a.add("I");
a.add("learned");
a.add("containers");
a.add(0, "This");
a.add(1, "week");
System.out.println(a.get(3));
System.out.println(a.get(4));
}
}
import java.util.*;
使用例
class use_hash {
public static void main(String[] args) {
HashMap<String,Integer> a = new HashMap<String,Integer>();
a.put("This", 0);
a.put("week", 1);
a.put("I", 2);
a.put("learned", 3);
a.put("containers", 4);
System.out.println(a.get("I"));
System.out.println(a.get("learned"));
if (a.containsKey("Intel")) {
System.out.println("Intel inside");
} else {
System.out.println("no Intel inside");
}
}
}
C++ Standard Template Library
(STL)


vector, list, deque, basic_string, bitset
set, multiset, map, multimap
使用例
#include <deque>
using namespace std;
int main(int argc, char ** argv)
{
deque<char *> a;
a.push_back("I");
a.push_back("learned");
a.push_back("containers");
a.insert(a.begin(), "This");
a.insert(a.begin() + 1, "week");
printf("%s\n", a[3]);
printf("%s\n", a[4]);
}
#include <map>
using namespace std;
使用例
int main(int argc, char ** argv)
{
map<char*, int> a;
a["This"]
= 0;
a["week"]
= 1;
a["I"]
= 2;
a["learned"] = 3;
a["containers"] = 4;
printf("%d\n", a["I"]);
printf("%d\n", a["learned"]);
if (a.find("Intel") != a.end()) {
printf("Intel inside\n");
} else {
printf("no Intel inside\n");
}
}
Python組み込みコンテナ


リスト
 a = [“To”, “learn”, “algorithm”, “is” ]
辞書
 a = { “To” : “a.html”, “learn” : “b.html” }
使用例
a = []
a.append("I")
a.append("learned")
a.append("containers")
# ここまでを
# a = [ “I”, “learned”, “containers” ] とも書ける
a.insert(0, "This")
a.insert(1, "week")
print a[3]
print a[4]
使用例
a = {}
a["This"]
= 0;
a["week"]
= 1;
a["I"]
= 2;
a["learned"] = 3;
a["containers"] = 4;
# 注: ここまでを a = { “This” : 0, “week” : 1, ... }
# とも書ける
print a["I"]
print a["learned"]
if "Intel" in a:
print "Intel inside"
else:
print "no Intel inside"
コンテナの分類整理
1. sequence (列)
2. map (写像)
associative array (連想配列)
associative memory (連想記憶)
などということもある
3. priority queue (優先度キュー)
列



直感的には: 値の列 v0, v1, v2, ..., vn – 1を保持
可能な操作
 先頭や末尾，より一般にはi番目となる，要素の追加
 先頭や末尾，より一般にはi番目の，要素の参照
 先頭や末尾，より一般にはi番目の，要素の置き換え，削除
実例
 Java : ArrayList, LinkedList
 C++ : vector, list, deque
 Python : リスト
写像，連想配列，連想記憶



直感的には，値 値の組(対応)を多数保持
 左を鍵(key), 右側を値(value)と呼ぶ
 keyは整数とは限らない
可能な操作
 新しい対応 key  valueを追加
 keyに対応する組(値)を参照(探索)
 keyに対応する組の置き換え・削除
実例
 Java : HashMap, TreeMap, ... (その他多数)
 C++ : map, multimap
 Python : 辞書
集合は写像の特別な場合



keyに対応するvalueがあれば，keyが集合に含まれるという
解釈
可能な操作
 新しい要素Xを追加
 Xが含まれるかどうかの判定
 Xを削除
実例
 Java : HashSet, TreeSet, ... (その他多数)
 C++ : set, multiset
優先度キュー


直感的には: 値の列 v0, v1, v2, ..., vn – 1をある決められた大小
関係(優先度)にしたがって保持
可能な操作
 優先度を指定しつつ，要素の挿入
 最小優先度の要素の取り出し
おまけ「出るコン」
(よく出るコンテナ)
列
写像
優先度キュー
Java
ArrayList, LinkedList HashMap
PriorityQueue
C++
deque
(vector, list)
map
priority_queue
Python
リスト
辞書
heapq
練習問題

最初に述べたスペルチェッカープログラムを，HashMap
(Java), map (C++), 辞書(Python)のいずれかを用いて書け
 辞書は可能な単語を1行に一個
 文章は単語が空白または改行で区切られているとせよ
(簡単のためカンマやピリオドは，ないものとしてよい)
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++:
Java:
それを矢印で表す
n:
p:
q:
r:
class 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
(Java)
class ArrayListX {
int capacity;
int n;
X[] a;
}
(C++)
class ArrayListX {
int capacity;
int n;
X * a;
}
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

追加は必ず新しい要素を入れる「箱」を新しく割り当てて行う
(Java)
class LinkedListX {
Cell head;
Cell tail;
}
class Cell {
Cell next;
Cell prev;
X value;
}
(C++)
class LinkedListX {
Cell * head;
Cell * tail;
}
class Cell {
Cell * next;
Cell * prev;
X value;
}
挿入操作の実際

(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
速い・遅い操作は?




i 番目となる要素の追加
O( )
 特に，末尾への追加
O( )
 特に，先頭への追加
O( )
i 番目の要素の削除
O( )
 特に，末尾からの削除
O( )
 特に，先頭からの削除
O( )
i 番目の要素の参照・置き換え O( )
注: 0, 1, ..., n – 1番目の要素を順に参照する O( )
 cf. Java, C++のiterator
練習課題
JavaのArrayList, C++のvectorに相当するデータ構造
 JavaのLinkedList, C++のlistに相当するデータ構造
を自分で作ってみよ(C, C++, またはJavaで)
 先頭・末尾への挿入・削除
 任意の値の参照
 挿入するデータの型は決めてよい(文字列など)
 以下の性能測定をしてgnuplotなどでグラフ表示せよ
 N個のデータを末尾に挿入する
 N個のデータを末尾に挿入後，それらを先頭から取り出す
 多数のデータ挿入後に，ランダムな要素の参照をN回

クイズ



i 番目の要素の参照 O(1)
先頭・末尾への追加 amortized O(1)
先頭・末尾からの削除 O(1)
を達成する方法は?
 C++ dequeがそれをやっている模様
 hint : ArrayListの方法を変更してみよ
写像，連想記憶


以下をすべて効率的に行いたい
 対応 key  value の追加
 key に対する対応 key  X の削除
 key に対応する value の探索
keyは以下を満たす任意の値
 key同士の等号比較ができる(当然の条件)
 時に，key間に全順序関係が存在すること，それに基づく
不等号比較ができることを仮定する
 挿入されたあとkey自身が変化することはない
 たとえばkey自身が配列で，挿入された後に変更される
ことはない
連想記憶の実現法

使われているデータ構造による分類
 配列
 木構造
 ハッシュ表
配列を用いた連想記憶


連想記憶 = keyの列とvalueの列
 Java: class map { ArrayList<K> a; ArrayList<V> b;};
二通りのやり方:
 その1:
 組k  vの挿入は末尾に行う (amortized O(1))
 a.add(k); b.add(v);
 探索は線形探索 O(n)
 その2: つねに整列 (a0  a1  a2  ... )しておく
 挿入は ai  k < ai+1なる i を見つけてi + 1へ挿入 O(n)
 探索は2分探索 O(log n)
2分探索


入力:
 整列された配列 a[0], ..., a[n – 1]
 i 0  i < n  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 4 5 6 10 13 13
q
90 98
2分探索
コード
int find_idx(String k) {
int 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]
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;
}

探索・挿入・削除


search(k) {
i = find_idx(k);
if (a[i] == k) return a[i];
else not_found;
}
insert(k, v) {
i = find_idx(k);
a.insert(i+1, k);
b.insert(i+1, v);
}
delete(k) {
i = find_idx(k);
if (a[i] == k) {
a.delete(i);
b.delete(i);
}
}
練習問題


ホーア論理を用いてループ部分の正しさを証明せよ
 自分で，事前条件，事後条件，ループ不変条件などを設定
せよ
{ ????? }
計算量 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))
 両者とも，「データのおき場所(アドレス)は自由，それをポ
インタでつなぐ」方式に起因
木構造
 両者の「中間」
木構造，リスト，配列の関係


配列: 深さ0の木(と見れなくもない)
リスト: 各ノードの子供が一人以下の木

木構造のパラメータ
 子供の数(1ならばリスト，非常に大ならば配列に近い)

木構造の子供の数が適度(2以上，ある一定値以下)ならば，
 データにたどり着くまでのポインタの追跡 O(log n)
 挿入・削除時のデータの書き換え O(log n)
 とできるのではないか?
2分木を用いた連想記憶


2分木 : 子供の数が0, 1, 2のいずれか
各ノードとリーフにkeyとvalueを格納
 リーフのみに格納する場合もある
“learned”
3
“I”
2
Java:
class Node {
Key k;
Value v;
Node left;
Node right;
};
C++:
class Node {
Key k;
Value v;
Node * left;
Node * right;
};
“about”
4
...
...
“today”
1
“searching”
5
...
...
効率的な探索のための2分木の構成
k
<k
>k
正しい2分木の状態

10, 20, 30, 40, 50, 60を格納している正しい2分木の状態例
30
10
10
20
50
30
20
40
60
40
50
60
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();
}
2分木はO(log n)か?
クイズ

整列に2分木が使える
ハッシュ表を用いた連想記憶
優先度キュー

Download Report