Open Data Structures: An Introduction（オープンデータ構造入門）

引用

Morin, P. (2013). Open Data Structures: An Introduction. AU Press. Free official edition: https://opendatastructures.org/

章の要約

第1章：はじめに

冒頭の章では、整列されていない百万個の要素に対して百万回の検索を行うと時間がかかりすぎるという大まかな計算によって効率の重要性を説明し、続いて本書全体で使うインタフェースを定義する。Queue、Stack と Deque、List、USet（順序なし集合）、SSet（順序付き集合）である。必要な数学（対数、階乗、漸近記法、期待値と指示変数を伴うランダム化）を復習し、w ビットのワード RAM という計算モデルを定め、住宅ローンの分割払いと一括購入、火災保険の購入というたとえで、最悪計算時間、償却計算時間、期待計算時間を区別する。また Java のコードは簡略化されている（public や private がない）ことを説明し、本書のすべてのデータ構造の一覧表を示す。

第2章：配列に基づくリスト

この章では、背後の配列の上に List と Queue を実装する。まず ArrayStack とその拡張・縮小の償却解析から始め、配列の一括コピーを使う最適化版、循環配列による ArrayQueue、両端の操作が速い ArrayDeque、そして一方が少なくなると再均衡する二つのスタックから作る DualArrayDeque を示す。最後に、要素を大きさが増えていくブロックに格納して無駄な領域を約 √n に抑える RootishArrayStack を、平方根の計算法の議論とともに扱う。

第3章：連結リスト

連結リストは、添字による定数時間のアクセスを手放す代わりに、既知のノードの隣での定数時間の挿入と削除を得る。この章では片方向連結リスト（スタックとキューの操作用）、ダミーノードを持つ双方向連結リスト、そして各ノードに小さなブロックを格納する省メモリのリスト SEList を実装し、ブロックの分散と集約に関する償却解析を行う。

第4章：スキップリスト

スキップリストはランダムなコイン投げによって連結リストの階層を作る。この章では各操作の期待時間が O(log n) の SSet と、添字によるアクセスを支える SkiplistList を実装し、探索経路の期待長と領域を解析する。

第5章：ハッシュテーブル

前半では、乗算ハッシュを用いるチェイン法と線形探査法を実装し、線形探査の解析を行ってタビュレーションハッシュを紹介する。後半では、基本型、複合オブジェクト、配列、文字列のハッシュコードの作り方を説明する。著者は、コード中の「ランダムな」定数が大気のノイズから生成されたものだと述べている。

第6章：二分木

二分木の用語を定義した後、再帰的および非再帰的な走査と、探索・追加・削除を備えた非平衡な BinarySearchTree を書く。章末の議論では、以後の章で O(log n) の性能を得る三つの方法、すなわちランダム化、償却、最悪時の平衡化を予告する。

第7章：ランダム二分探索木

この章はまず、ランダムな順列から作った二分探索木の探索経路の期待長が対数であることを証明し、その結果を用いて Treap を設計する。Treap はランダムな優先度を割り当てることで、挿入や削除の後も木をランダムな形に保つ。

第8章：スケープゴート木

スケープゴート木は、ときどき部分木全体を完全に平衡な部分木に作り直すことで平衡を保つ。この章では再構築を実装し、更新の償却コストが O(log n) であり、高さが抑えられているため探索は最悪でも O(log n) であることを示す。

第9章：赤黒木

本書で最も技術的な章である。まず 2-4 木を示し、次に左傾型の変種を用いて赤黒木を 2-4 木のシミュレーションとして実装し、追加と削除を場合ごとに詳しく扱う。赤黒木が Java Collections Framework などのライブラリで使われる理由、すなわち対数の高さ、最悪 O(log n) の更新、償却で定数回の回転を説明する。

第10章：ヒープ

二つの優先度付きキューを作る。Eytzinger の配置を用いて完全二分木を配列に格納する BinaryHeap と、二つのヒープの併合も可能にするマージ操作を持つランダム化ヒープ MeldableHeap である。

第11章：ソートアルゴリズム

マージソート、クイックソート、ヒープソートを扱い、比較に基づくソートの下界を証明した後、整数のための計数ソートと基数ソートを示す。クイックソートはランダム探索木に、ヒープソートは BinaryHeap に結びつけられる。

第12章：グラフ

グラフを隣接行列と隣接リストで表し、そのコストを比較した後、幅優先探索と深さ優先探索（非再帰版の深さ優先探索を含む）を示す。

第13章：整数のためのデータ構造

w ビット整数をキーとする SSet の問題に戻り、BinaryTrie（O(w) の操作）、ハッシュを用いて O(log w) 時間で探索する XFastTrie、そして XFastTrie に格納した標本と通常の SSet を組み合わせてすべての操作を期待 O(log w) 時間にする YFastTrie を順に作る。

第14章：外部メモリでの探索

最終章では、すべてのデータがメモリに収まるという前提を外す。RAM、SSD、ハードディスクの実測アクセス時間で外部メモリモデルの動機を示し、ブロックストアを導入して、B 木の探索、追加、削除と、分割・併合の償却解析を実装する。

主要概念

第1章：はじめに

• インタフェースと実装：インタフェース（List、USet、SSet）はどんな操作があるかを定め、データ構造はそれを実装する一つの方法である。
• 償却時間と期待時間：償却の上界は一連の操作にわたるコストの平均であり、期待値の上界はデータ構造自身のランダムな選択についての平均である。
• ワード RAM モデル：w ビットのワードに対する基本操作が定数時間で行え、w は少なくとも log n であるとする計算モデル。

第2–3章：配列に基づくリスト・連結リスト

• サイズ変更する背後の配列：配列を倍にしたり半分にしたりすることで、末尾での追加と削除の償却コストを定数に保つ。
• 循環配列：添字を配列長で割った余りとして扱い、キューや両端キューがどちらの端にも伸びられるようにする。
• 省メモリの構造：RootishArrayStack と SEList は無駄な領域を約 √n、あるいは n のわずかな割合に抑える。

第4章：スキップリスト

• ランダムな階層：各要素を確率 2 分の 1 で一つ上のリストに昇格させ、探索経路の期待長を対数にする。

第5章：ハッシュテーブル

• チェイン法：配列の各スロットが、そこにハッシュされる要素のリストを持つ。
• 線形探査法：要素を配列に直接格納し、衝突したら次の空きスロットまで前方に走査する。
• ハッシュコード：任意のオブジェクトを整数に変換する関数で、等しいオブジェクトが等しいコードを持つように組み合わされる。

第6–9章：二分探索木

• 二分探索木の性質：各ノードの値は左部分木の値より大きく、右部分木の値より小さい。
• Treap：ランダムな優先度に関するヒープでもある探索木で、形をランダムに保つ。
• 部分的な再構築：平衡の崩れた部分木を一から作り直すこと。スケープゴート木の基本的な考え方である。
• 2-4 木としての赤黒木：ノードを彩色して二分木で 2-4 木を表し、高さを 2 log n 以下に保証する。

第10–11章：ヒープ・ソート

• 暗黙的な二分木：完全二分木を配列に格納し、親と子の位置を算術的に計算できるようにする。
• 比較の下界：比較に基づくどんなソートも、最悪および平均の場合におよそ n log n 回の比較を必要とする。

第12–14章：グラフ・整数・外部メモリ

• 隣接リスト：各頂点について、その出近傍のリストを保持するグラフの表現。
• 二進キーのトライ：根から葉への経路が整数キーのビット列を表す木。
• B 木：ノードの大きさをディスクブロックに合わせ、ブロックの読み込み回数を最小にする平衡探索木。

批判的分析

長所

• インタフェース、実装、証明が一体になっている。 各データ構造は少数のインタフェースのいずれかに照らして導入され、完全に実装され、明示された定理で解析される。ほとんどの節は実行時間の短いまとめで終わる。1.7 節の表で、すべての構造を一目で比較できる。
• 通常の入門科目を超える範囲。 リスト、ハッシュテーブル、探索木、ヒープに加え、スキップリスト、Treap、スケープゴート木、併合可能ヒープ、X-fast・Y-fast トライ、B 木を扱い、同じ上界に至るいくつかの方法（ランダム化、償却、最悪時の平衡化）を示している。
• 三種類の保証の丁寧な扱い。 最悪時間、償却時間、期待時間の区別は第1章で具体的なたとえとともに導入され、全体を通じて使われる。そのため、たとえば赤黒木が複雑であるにもかかわらずライブラリで好まれる理由が理解しやすい。
• オープンで改変可能。 序文によれば、本書はオープンソースのプロジェクトとして運営されている。LaTeX と Java のソースはクリエイティブ・コモンズ表示ライセンスで GitHub に公開され、Java、C++、擬似コードの版がある。各章の議論の節は歴史的背景と参考文献を示す。

短所

• 入門科目としては数学的な要求が高い。 証明は早い段階（第4章以降）から確率、指示変数、償却の議論を用い、第9章の赤黒木の削除は長い。離散数学を学んでいない学生には難しいかもしれない。
• コードは慣用的というより簡略化されている。 Java の例はアクセス修飾子やクラス階層を意図的に省いており、完全な実装は付属のソースコードを見る必要がある。また、ライブラリのコレクションの使い方は扱わない。
• グラフとアルゴリズムは簡潔。 第12章は表現と幅優先・深さ優先探索のみで、最短経路や最小全域木などのグラフアルゴリズムは扱わない。AVL 木のような平衡木も議論の節で触れられるだけである。
• 版の細部がやや古い。 読んだ版（0.1G）は 2010 年代前半のもので、32 ビット JVM のワード長やディスクの時間など、一部の例はその時代を反映している。演習の解答は付いていない。

コースにおける位置づけ

このコースのデータ構造の本の中で、Morin は、図解中心のやさしい本（Bhargava の Grokking Algorithms と Wengrow の A Common-Sense Guide to Data Structures and Algorithms）と専門的な本（Okasaki の Purely Functional Data Structures と Brass の Advanced Data Structures）の間にある。形式的な解析に慣れていない学生は、一般に数学をほとんど使わずに直感を養う本とされる入門書から始め、その後 Morin に進んで証明と完全な実装を学ぶとよい。

Goodrich、Tamassia、Goldwasser の Data Structures and Algorithms in Java は近い範囲を扱う。一般に Java プログラミングとアルゴリズムをより多く含む幅広い標準的教科書とされるので、それを主教材として Morin を無料でより解析的な副読本にすることも、その逆も可能である。Morin の後は、より高度な探索構造に関心のある学生には Brass が、同じ考え方が純粋関数型の環境でどう見えるかを知りたい学生には Okasaki が自然な次の一歩となる。

本書の使い方

本書は、プログラミングの科目を一つ修了し、離散数学を少し学んだ情報系の 2 年生に向いている。後で使う確率と漸近記法は第1章で復習される。Java に慣れていると役立つが必須ではない。コードは簡略化された書き方で、C 系の言語を知っていれば読める。

一学期の授業では、第1章、第2章（少なくとも ArrayStack、ArrayDeque、DualArrayDeque）、第3章（片方向・双方向連結リスト）、第5章、第6章、平衡化の方法として第7章または第8章、第10章、第11章を中心にするとよい。スキップリストの第4章はランダム化解析への良い入門になる。第9章は 2-4 木との対応の部分までを読み、削除の全場合は任意としてよい。第12–14章は長めの授業や独学向きである。

各章末の演習（全体で 150 問を超える）のいくつかに取り組むこと。多くは構造の実装や改変を求めるもので、ダウンロードできるソースコードを使えば自分の版を本書の実装と比べて試せる。各章の議論の節では、それぞれの考え方の歴史とさらなる文献への手がかりが得られる。

版と出典

本ガイドは Open Data Structures (in Java) 第 0.1G 版に基づき、著者の公式サイト https://opendatastructures.org/ で公開されている無料 PDF（ods-java.pdf）を読んで作成した。印刷版は 2013 年に AU Press から刊行されている。謝辞、序文「Why This Book?」、完全な目次、第1章の全文（1.1–1.8 節）、そして第2–14章の各章の導入、すべての節見出し、まとめと実行時間の表、および「Discussion and Exercises」の節を参照している。