みんなのデータ構造
1章
データ構造の「インタフェース」と「実装」は別
「インタフェース」
抽象データ型とも呼ばれる
備えている操作とその意味（セマンティクス）
「実装」
データ構造の内部表現
アルゴリズムの定義
配列でもポインタでもListを実装可能
Queue
queueといえば一般的にはFIFO queueを指す
add(x) = enqueue(x)
remove() = dequeue()
Priority Queue
最小の要素を削除する
add(x) = enqueue(x)
remove() = deleteMin()
Stack
LIFO queueに付けられる特別な名前
add(x) = push(x)
remove() = pop()
Deque
FIFO, LIFOを一般化したインタフェース
以下の組み合わせで両方を実現できる
addFirst(x)
addLast(x)
removeFirst()
removeLast()
List
上述のインタフェースはListインタフェースとしてまとめることができる
以下の組み合わせでそれらを実現できる
size()
get(i)
set(i, x)
add(i, x)
USet
unordered set
数学における集合
n個の互いに相異なる要素が含まれる
size()
remove()
find(x)
add(x)
SSet
sorted set
USetと同じセマンティクスのインタフェースを備えるがfindが異なる
SSetのfind(x)は後継探索 successor search と呼ばれる
y >= x を満たす最小の要素yを見つける
SSetのほうが実装が複雑で実行時間が長い
必要な機能がなければUSetを使う
数学を思い出すシリーズ
$ \log_{b}{k}
これは$ \mathrm{b}^{x}=k を満たすxとして一意に決まる
底が省略されていれば2とする。二進対数
イメージは「kを何回bで割れば1以下になるかを表す数」
オイラーの定数 e を底とする対数もよく使う
$ \log_{e}{k}を$ \ln kと書き、自然対数と呼ぶ
冪指数にある対数の除去
底の変換操作
これらを組み合わせると自然対数と二進対数を比較できる
$ n!
スターリングの近似で見積もりが可能
乱択化 randomization
格納されているデータや実行する操作に加えてサイコロの出目も踏まえて実際の処理を決める
同じことをしても実行時間が毎回同じにはならない
このようなデータ構造の分析においては期待実行時間を考えるとよい
期待値の線形性
インジケータ確率変数
データ構造の性能を考えるときの重要な項目
正しさ
インタフェースを正しく実装していること
時間計算量 time complixity
最悪実行時間 worst-case running time
ある操作の最悪実行時間が f(n) というとき、実行時間は絶対にそれより長くならない
償却実行時間 amortized running time
典型的な操作にかかるコストが f(n) を超えないことを意味する
いくつかの操作は超えるかもしれないが全体として考えれば f(n) といえるという意味
期待実行時間 expected running time
実行時間が確率変数であり、確率変数の期待値が f(n) であることを意味する
空間計算量 space complixity
2章 配列を使ったリスト
ArraryStack
get(i), set(i,x)は O(1) 定数時間で実行できる
add(i,x), remove(i) は O(1 + N - i)
m個のaddおよびremoveを実行したときにresizeにかかる時間はO(m)
FastArraryStack
C++のstd::copyのような、resize時に各要素を新しい配列にfor loopでcopyするのではなく、高速にコピー可能な機械語の命令に変換される機能を使うことで高速化される
ArrayQueue
add(x)で追加された順にremove()で削除される
ArrayStackをそのまま使うことはできない
i=0でadd(i,x), remove(i) を呼び出すことになり、nに比例する実行時間がかかる
無限長の配列があれば配列を使ったキューを実装可能
次に削除する要素を追跡するindex j、キューの要素数n
initialize
[nil, nil, ...] j=0 n=0 で初期化
add(x) nをインクリメント
[x, nil, ...] j=0 n=1
add(y) nをインクリメント
[x, y, ...] j=0 n=2
remove() jでアクセス出来る要素を除いたあとに jをインクリメント、nをデクリメント
[nil, y, ...] j=1 n=1
次はyが削除されることが保証される
無限長の配列は存在しないので剰余算術で工夫する
a[j] を j mod a.length とする
jが配列の添字として有効なa.length-1を超えたとしても、配列の先頭に戻る
要素数がaの大きさを超える問題は、resize()でカバーする
add(x)の際にaが一杯であればresize()
remove()の際にも必要ならresize()
resize()
j mod a.length から開始して (j + n - 1) mod a.length までを順に新たな配列にcopyする
jを0に戻す
add(x), remove() は O(1)
m個のaddおよびremoveを実行したときにresizeにかかる時間はO(m)
ArrayDeque
ArrayQueueは一方の端からは追加、もう一方からは削除しかできない
ArrayDequeでは両端に対して追加・削除ができる
ArrayQueue同様に
内部の配列は循環配列
内部の追跡用index j、キューの要素数nを持つ
add(i,x) remove(i) の際に要素をずらす処理が発生する
ずらす量が少なくて済むように実装するので操作にはmin{i, n-1}のコストがかかる
add(x), remove() は O(1)
m個のaddおよびremoveを実行したときにresizeにかかる時間はO(1 + min{i, n-1})
つまり、両端においてはO(1)なのでDequeのインタフェースを備えていることになる
DualArrayDeque
2つのArrayStackを組み合わせて使うデータ構造
RootishArrayStack
メモリ効率を重視したデータ構造
3章 連結リスト
Listインタフェースの実装で連結リストを使う
連結リストとはリストの要素を収めたノードの集まり
ポインタを使ってノードを繋げて列を作る
長所
動的な操作がしやすい
短所
読み書きする際に対象のノードを見つけるまで辿るため、get(i) set(i,x) が定数時間ではなくなる
SLList (singly-linked list)
各ノードuはデータu.xとu.nextを保持している
末尾ノードではnextはnullになる
効率のために要素数と、先頭ノード・末尾ノードへの参照を持つ
code:typescript
interface Node {
x: T;
next: Node | null;
}
type SLList {
n: number;
head: Node;
tail: Node
}
最後のノードを削除するときや空のリストにノードを追加するときはhead, tailの更新に工夫が必要
Stackを実装するには
push(x)で先頭にノードを追加すると定数時間
pop()で先頭を削除すると定数時間
FIFO Queueを実装するには
add(x)で末尾にノードを追加すると定数時間
remove()で先頭を削除すると定数時間
SLListはStack, FIFO Queueインタフェースを実装する
要素の追加・削除はいずれも定数時間O(n)で実行可能
DLList (doubly-linked list)
SLListのノードとの違い
直前の要素prevへの参照も持っている
最後のノードを削除するときや空のリストにノードを追加するときの複雑な実装を避けるため、dummyノードを持つ
dummyノードはデータを持たない
dummyノードは先頭の直前、末尾の直後に位置しており、DLListは内部的にはノードが循環している
code:typescript
interface Node {
x: T
next: Node;
prev: Node;
}
class DLList {
private n: number;
private dummy: Node;
constructor() {
this.dummy = {} as Node;
this.dummy.next = this.dummy;
this.dummy.prev = this.dummy;
this.n = 0;
}
}
getNode(i) 添字を指定してノードを見つける際には先頭（dummy.next）か末尾（dummy.prev）の近い方から探すのでi番目のノードを見つけるにはO(1 + min{i, n-1})
get(i) set(i,x) の処理は簡単で、getNode(i) したあとに値を返すか書き換えればよい。その操作は定数時間だがgetNode(i)のO(1 + min{i, n-1})がかかる
追加
ノードwの直前に追加したく、参照がわかっている場合は addBefore(Node *w, T x)で挿入する
前後のノードをwから辿って参照を書き換える
dummyノードがあるので先頭か末尾かを気にする必要がない
削除
削除したいノードwの参照がわかっている場合は remove(Node *w)で削除する
これも前後の参照を書き換えるだけ
dummyノードがあるので先頭か末尾かを気にする必要がない
添字で対象を選ぶremove(i)もgetNode(i)でノードを見つけてからremove(Node *w)するだけですむ
DLListはListインタフェースを実装する
get(i) set(i,x) add(i,x) remove(i) すべての実行時間がO(1 + min{i, n-1})
時間がかかるのはノードへの参照を得る処理のみなので、参照を定数時間で取得できるようなデータ構造 (たとえばUSet) と組み合わせて使うと良い
実例
RedisのList
SEList (space-efficient list)
メモリ使用量が多いという連結リストの欠点を克服するデータ構造
Nodeにはデータの他にポインタを2つも持っている
BDeque (bounded deque) というArrayDequeに似たブロックを複数持ち、BDequeが連結されている
BDequeはArrayDequeと違って縮小しない
探索時にブロックを丸ごとスキップできるので O(1 + min{i, n-1}) / b)
SEListによって、ArrayListかDLListかのトレードオフを調整出来る
unrolled likned listと呼ばれることもある
XOR-list
DLListのメモリ使用量を克服するデータ構造
ノードuはポインタの代わりにu.nextprevを持つ
uとu.prevがあれば u.next = u.prev ^ u.nextprev (排他的論理和) で求めることができる
この方法の欠点
実装が複雑になる
ガベージコレクションがある言語 (Java, Python etc.) では利用できない
4章 スキップリスト
単方向連結リストを縦に並べるイメージ
ohbarye.icon 図がないと説明が難しい
最下層は通常のソートされた連結リスト
層i に存在するリストの要素は層i+1 においては固定の確率p（良く使われる p の値は 1/2 と 1/4）で存在する
SkiplistSSet
find(x) add(x) remove(x) すべて平均的には O(logN)、最悪O(N)
ohbarye.icon add, remove の実装がそこそこ複雑なので読み飛ばした
SkiplistList
DLListはListインタフェースを実装する
get(i) set(i,x) add(i,x) remove(i) すべての実行時間がO(logN)
定理
n 要素を含むスキップリストの大きさの期待値は O(n) である。あ る要素の探索経路の長さの期待値は 2 log n + O(1)
ohbarye.icon 証明についていけなかった
実例
RedisのSortedSetはHash tableとSkip listの組み合わせで実現している
5章 ハッシュテーブル
ChainedHashTable
chaining (チェイン法)
内部に長さnの配列tを持つ
データをリストに格納する
ハッシュ値iのデータはt[i]のリストに入る
同じハッシュ値を持つデータが複数あっても良い
データxのハッシュ値をhash(x)と表現する
n <= t.lengthであればリストの平均要素数は1以下になる
add(x)
code:c++
bool add(T x) {
if (find(x) != null) return false;
if (n+1 > t.length) resize();
n++;
return true;
}
ArrayStack同様に必要に応じてresizeする
拡張にかかる償却実行時間は定数
remove()
t[hash(x)]のリストを探索する
ハッシュテーブルの性能はハッシュ関数に大きく依存する
"良い"ハッシュ関数は0~t.length-1の間で均等に分散する関数
"悪い"ハッシュ関数はその逆で、すべてを同じリストに突っ込んでしまう
ChainedHashTableはUSetインタフェースを実装する
add(x) remove(x) find(x) すべて O(1)
LinearHashTable (線形探索法)
open address (オープンアドレス法) を用いる
配列tに直接値を格納する
i = hash(x) となる要素 x をテーブ ルに格納するときに理想的な場所は t[i] であろうという考える
そこに他の要素が格納されている場合は、t[(i + 1) mod t.length] を試す。それも無理なら、t[(i + 2) mod t.length] を試すx を格納できる場所が見つかるまで、これを繰り返す。
t の値としては次の 3 種類を使う。
データの値:USet に実際に入っている値
null:データが入っていないことを示す値
del:データが入っていたがそれが削除されたことを示す値
削除時にt[i]をnullにしてしまうと、探索時にt[(i + 1) mod t.length]を探しに行かずに探索が終了してしまうため
追加時にnullかdelであれば置き換える
resize() が呼び出されるのは
add(x) に際して null でないエントリの数t.length/2 を上回るとき
remove(x) に際してデータの入っているエントリ数が t.length/8 を下回るとき
ChainedHashTableはUSetインタフェースを実装する
add(x) remove(x) find(x) すべて O(1)
Tabulation hashing
上記の実行時間解析はhash値が一様に分布するという仮定を置いている
この仮定の実現には大きさ2^wの巨大配列に、すべてが独立するwビットのランダムな整数を用意する必要があるがメモリ観点では厳しい
配列を分割し、排他的論理和を計算することでhash値を求められる
ハッシュ値
ハッシュテーブルに格納するデータは整数ばかりではない
プリミティブ型
char, byte, int, floatなどには常に2進数による表現がある
ビット列を整数として解釈すれば整数と同様に扱える
複合オブジェクト
構成要素それぞれのハッシュ値と乱数を用いて計算する
配列と文字列
固定数の構成要素の場合は上記のやり方はうまくいかない
素体上の多項式を利用する
ohbarye.icon このあたりかなり難しくて理解できていない…
Further discussion
上記のChaining hash tableと Linear hash tableは任意のデータセットに対応する実用的なもの
ハッシュテーブルとハッシュ値の研究は長く、活発で多岐にわたるので、その他にも様々な研究と実装がある
perfect hashing (完全ハッシュ法)
find(x)が最悪でもO(1)になる
データセットが静的であればperfect hash function (完全ハッシュ関数) を見つけることができる
派生もある
動的データセットにも対応するtwo-level hash table
cuckoo hashing
universal hashing
6章 二分木
二分木には複数の定義がある
数学的な二分木(binary tree)の定義
連結(connected) な有限無向グラフ
閉路 (cycle) を持たない
すべての頂点の次数 (degree) が3 以下
コンピュータサイエンスにおける応用
二分木はふつう根を持つ (rooted)
木の根(root)と呼ばれる特殊なノード r があり、このノードの次数は 2 以下
ノード u (≠ r) から r に向かう経路における 2 番めのノー ドを u の親(parent)という。u に隣接する親以外のノードを u の子(child) という
特に順序付けられている(ordered)二分木に興味があることが多い ので、子を左の子、右の子と呼び分ける
走査
再帰的なアルゴリズムを使うと二分木に関する計算が楽になる
code:typescript
interface Node<T> = {
left: Node;
right: Node;
parent: Node;
val: T;
}
const size = (Node u) => {
if (u === null) return 0;
return 1 + size(u.left) + size(u.right);
}
const height = (Node u) => {
if (u === null) return -1;
return 1 + max(height(u.left), heihgt(u.right));
}
再帰なしで二分木を走査することができる
StackまたはQueue (List) を使う事が多い
Binary Search Tree
バランスされていない二分探索木
全順序な集合の要素をデータ u.x として持つ特別な二分木 ノード u について以下が成り立つ
u.left を根とする 部分木に含まれるデータはすべて u.x より小さい
u.right を根とする部分木 に含まれるデータはすべて u.x より大きい
BinarySearchTree は SSet インターフェースの実装であって、 add(x)、remove(x)、find(x) の実行時間は O(n) である。
SkipListSSetよりも性能が良くない
Binary Search Treeはバランスされていない＝偏りがある可能性がある
{0,1,2,...14} の順で追加した場合、ただのListのようなchainになる
回避するいくつかの方法を後続の章で紹介する
第7章では期待実行時間がlogN
第8章では償却実行時間がlogN
第9章では催花雨実行時間がlogN
二分木の設計
parentへの参照を持つか？
ないほうがメモリ効率が良いしバグも少なくなる
あると走査時に便利な事が多い
parent, left, rightへの参照をどのように持つか？
u.p = [parent, left, array] のように持っても良い
代数的な表現ができることで簡潔に書けることがある
木のrotateLeft, rotateRightが好例
走査順
行きがけ順(pre-order)とは、二分木の訪問順であって、ノード u をそのいずれの子よりも先に訪問するものである
通りがけ順(in-order)とは、二分 木の訪問順であって、ノード u を左の部分木に含まれる子よりも後かつ右の部 分木に含まれる子よりも先に訪問するものである
帰りがけ順(post-order) とは、二分木の訪問順であって、ノード u を u を根とする部分木に含まれる いずれの子よりも後に訪問するものである。
行きがけ番号、通りがけ番号、帰 りがけ番号とは、それぞれの対応する順序に従って頂点を訪問したときにノー ドに付される訪問順の番号である。
7章 ランダム二分探索木
ランダム二分探索木
乱択化によって性能向上した二分探索木
15個の要素 {0,1,2,...14} の順で追加した場合、ただのListのようなchainになるが、このような形になるのは1通りだけ
1/1307674368000 なので現実的には無視できる
一方、バランス木の形をとれるのは21964800通りある
ランダムに追加されるとき、それなりに平衡木に近い形になる
{0,...n-1}の置換を選んでその順に追加していく
計算量
ランダム二分探索木の構築にかかる時間は O(n log n)
find(x)についてO(log n)が任意のxに成り立つ
Treap
ランダム二分探索木は add remove を想定していないのでSSetインタフェースを満たしていない
特色
nodeは値xだけでなくpriority p を持つ
pはxに対して一意、かつランダムに割り当てられる
ヒープ性を持つ: 根でない任意のノード u について u.parent.p < u.p が成り立つ
add removeの実装ができる
要素の追加・削除の際にヒープ性を保つように rotateLeft or rotateRight する
計算量
add(x) remove(x) find(x) いずれの実行時間の期待値も O(logn)
SkipListとの比較
いずれも SSet の 実装で、各操作の実行時間の期待値は O(logn)
どちらのデータ構造 でも、add(x)、remove(x) は、検索に続けて定数回のポインタの更新からなる
どちらのデータ構造でも、探索経路の長さの期待値が 性能を決める重要な値である
SkipList: $ 2\log{n} + O(1)
Treap: 2lnn + O(1) ≈ 1.386logn + O(1)
Treapのほうが高速といえる
8章 スケープゴート木
再構築によって完全二分木を保つ
9章 赤黒木
Java collection frameworkやC++ STLなどで広く使われている
理由
木の高さが要素数の対数 $ 2 log Nで抑えられる
add(x) remove(x) を最悪 $ O(logN) で実行できる
add(x) remove(x) に伴う回転の回数は償却すると定数になる
SkipList, Treapは乱択を利用するので木の高さは保証せず、$ O(logN) は期待値にすぎない
Scapegoatは木の高さを保証するが$ O(logN) は償却時間にすぎない
代償として実装が複雑
2-4木
いきなり赤黒木の設計を見る前に2-4木を理解する必要がある
各nodeが持つ子の数が2~4の木のこと
bestでは木の高さが$ \log{4} N
赤黒木
2-4木を効率的にシミュレートしている
定義は1つではなく、実装も複数ある
代表的なものが左傾赤黒木 (left-leaning)
左傾性を持つことでnodeの次数ごとに赤を持つかどうかが判断できる
赤黒木 は SSet インターフェースの実装であって、 add(x)、remove(x)、find(x) の実行時間は $ O(\log N) である。
AVL木
赤黒木より古くから存在するデータ構造
highly-balanced性を持つ
任意のnode uについて、u.leftを根とする部分木の高さとu.rightを根とする部分木の高さの差が高々1である性質
赤黒木よりも木の高さが低く実装は単純だが、回転の償却時間は1ではない
10章 ヒープ
優先度付きキューの実装
2種類あるがいずれも特殊な二分木でヒープと呼ばれる
「雑多に積まれたもの」を意味する
二分探索木は高度に構造化されているので対照的
BinaryHeap
二分木を間接的に表現する
配列にnodeを幅優先順に入れていく
Eytzinger法と呼ばれ、コンピュータサイエンスが生まれるよりはるか昔400年以上前に発見された
隣接するnodeは以下のように表現できる
code:c++
int left(int i) {
return 2*i + 1;
}
int right(int i) {
return 2*i + 2;
}
int parent(int i) {
return (i-1)/2;
}
昇順の場合、最小値がrootに来る
ヒープは完全二分木である
BinaryHeap は優先度付きキューのインターフェースを実装する。add(x)、remove() の実行時間は $ O(\log N) である。
MeldableHeap
2つのnode (と連なる部分木) のmergeを軸とする実装
add(x) では追加するnodeとrootをmergeする
remove() ではrootが除かれるのでleft childとright childをmergeする
merge処理においてはheap性を失わないようにnodeの持つkeyで比較をしてparentとなるnodeを決めるが、leftとrightどちらとmergeさせるかはランダムに決める
BinaryHeapと違って二分木の形状に制約はない
n個のnodeからなる二分木におけるランダムウォークの長さの期待値は$ \log (N+1)
MeldableHeap は優先度付きキューのインターフェースを実装する。add(x)、remove() の実行時間は $ O(\log N) である。
11章 整列アルゴリズム
比較に基づくものではないソートアルゴリズムは小数のデータの整列に向いている
これはIEEE754において、数の大きさに符号のついた二進整数表現とみなすよう設計されているため 12章 グラフ
グラフに対する典型的な操作群
addEdge(i,j)
removeEdge(i,j)
hasEdge(i,j)
outEdge(i)
inEdge(i)
これらはUSet、ハッシュテーブルなどで実装可能だが、要求を満たす中でも単純な実装を用いることで応用が効く
隣接行列 AdjacencyMatrix
頂点間の関係を行列で管理する
空間使用量$ O(n^2)
計算量
addEdge(i,j) 定数時間
removeEdge(i,j) 定数時間
hasEdge(i,j) 定数時間
outEdge(i) $ O(n)
inEdge(i) $ O(n)
隣接リスト AdjacencyLists
2次元配列で管理するが、2次元目の要素は「ある頂点が隣接している頂点で構成されるリスト」
空間使用量$ O(n+m)
計算量
addEdge(i,j) 定数時間
removeEdge(i,j) $ O(deg(i))
hasEdge(i,j) $ O(deg(i))
outEdge(i) $ O(deg(i))
inEdge(i) $ O(n+m)
deg(i)は頂点iから出ている辺の個数（＝各リストの要素数）
探索
いずれもO(n+m)で走査できる
13章 整数を扱うデータ構造
再びSSetの話
SSetにて整数をキーとして扱いたいシーンは非常によくある
そうしたシーンに有効なトライ木と呼ばれるデータ構造がある
Re"trie"valから来ている造語らしい
BinaryTrie
wビットの整数の集合を二分木で符号したもの
…と聞いてもパッとわからないが図を見るとわかる
4 bitsの数字があるとして、上位ビットが0か1かで木が分岐する
値を持つ葉同士は双方向連結リストで結ばれている
先端と末端にはdummy nodeが紐付いている
探索、追加、削除はいずれも同じ辿り方をし、いずれも木の深さ＝wビットに対して$ O(w)
たかだか$ 2^w の整数しか格納できないうえに性能も$ \log{n} \le wなのであまりパッとしない
XFastTrie
BinaryTrieの改良
木の深さwに対して $ i \in \{1,...,m\}とし、iごとにハッシュテーブルを用意する
findを$ O(\log{w})
YFastTrie
XFastTrieの改良
木のノードの数をn/wに減らし、葉がTreapを拡張したデータ構造を持つ
TreapはSSetを備えている
探索、追加、削除いずれも$ O(\log{w})
ohbarye.icon 難しくてあまり理解できていない
14章 外部メモリの探索
これまでデータ構造内のすべてのデータをRAMに格納出来る前提で扱ってきた
大きすぎて収まりきれないデータもある
RAMへのアクセスはSSDと比べて2500倍、HDDと比べて160000倍以上高速
HDDやSSDのデータを読むときにはブロック単位で読み出しが行われる
演算対象はたった1バイトだとしてもそのバイトを含むブロックをまとめてRAMに読み込む
I/Oモデル、ディスクアクセスモデルと呼ばれることもある
B木
ファイルシステムにおける基本的なデータ構造として用いられている
Appple HFS+
Microsoft NTFS
Linux Ext4
B木がよく利用される理由
ブロックサイズをBとしたとき$ O(\log_{B} n)が実行時間の上界
実際Bはかなり大きい数字（数百〜数千）なのでデータの99%ぐらいは葉に保存されている
データベースにおいて、残り1%の内部ノードをRAMにすべて積める可能性が高い
その場合、すべての内部ノードの走査は高速に行え、外部メモリへのアクセスは1回で済む