配列、リスト、木、グラフ、それぞれの理論的な特性を知り、実装まで理解するためのガイドブック
- Pat Morin 著、堀江 慧・陣内 佑・田中 康隆 共訳
- 288ページ
- A5判
- 電子書籍の形式：PDF
- ISBN：978-4-908686-06-1
- 2018年7月20日 第1版第1刷 発行
- 正誤情報
データの格納方法を工夫するだけで、魔法みたいにアルゴリズムが導出できる。うまくデータを整頓するだけで、画期的に計算が速くなる。仕事で直面している問題がなかなか解決しないのは、問題に対する適切なデータ構造を知らないから、というだけかもしれません。
計算機科学の授業で当たり前のように学ぶさまざまなデータ構造。学部生向けの教科書としてはもちろん、理論を学ぶチャンスがないまま業務でプログラムを開発しているエンジニアや、そもそも学ぶ機会がまだ訪れていない高校生プログラマが、その考え方の基本を学ぼうとするときに手に取るべき一冊です。
本書は、Pat Morin教授が執筆しクリエイティブコモンズ継承ライセンス（CC BY）で公開している教材 “Open Data Structures” を、本書で学んだ訳者らが Pat 氏の許諾のもとで翻訳、クラウドファンディングをはじめとする普及活動を続けているコンテンツを書籍として発行するものです。書籍そのものはCC BYライセンスではありませんが、原稿テキストおよび書籍と同一内容のPDF（レイアウトは販売されている書籍とは異なります）は堀江氏が管理する下記のサイトからCC BYライセンスのコンテンツとしてご利用いただけます。
著者紹介
Pat Morin
Carleton大学コンピュータサイエンス学部教授。Carleton大学で博士（コンピュータサイエンス）を取得。近年の研究領域は計算幾何学やデータ構造、分散計算など。2012 年にOpen Data Structures プロジェクトを開始した。好きなデータ構造はスキップリスト。
堀江慧（ほりえさとる）
東京大学教養学部の授業にて本書と出会う。東京大学総合文化研究科修士課程修了。好きなデータ構造はBloom Filter。好きな分野は並列分散処理や組み合わせ最適化。好きな言語は、最近だとGolang やErlang、CUDA。コンピュータにハードな計算を投げつけて、その間代わりに自分はダラダラしてあげるのが好き。あとは人の書いたプログラムの不要な部分を削るのが好き。
陣内佑（じんないゆう）
ブラウン大学博士課程学生。東京大学大学院総合文化研究科修士課程を修了し、理化学研究所革新知能統合研究センター勤務を経て、ブラウン大学博士課程へ。学部より現在まで人工知能と機械学習の研究開発に従事。好きなデータ構造は二分木。好きな言語はC++。
田中康隆（たなかやすたか）
東京大学教養学部の授業にて本書と出会う。コロンビア大学計算機科学科修士課程修了。好きなデータ構造はBounded Priority Queue。好きな言語はRとPython。現在は米国カリフォルニア州フェイスブック本社勤務のエンジニアとして、ビッグデータと日々格闘している。
目次
訳者まえがき
本書の読み方
訳者謝辞
なぜこの本を書いたのか
謝辞
C++版のまえがき
第1章 イントロダクション
1.1 効率の必要性
1.2 インターフェース
1.3 数学的背景
1.4 計算モデル
1.5 正しさ、時間計算量、空間計算量
1.6 コードサンプル
1.7 データ構造の一覧
1.8 ディスカッションと練習問題
第2章 配列を使ったリスト
2.1 ArrayStack：配列を使った高速なスタック操作
2.2 FastArrayStack：最適化されたArrayStack
2.3 ArrayQueue：配列を使ったキュー
2.4 ArrayDeque：配列を使った高速な双方向キュー
2.5 DualArrayDeque：2つのスタックから作った双方向キュー
2.6 RootishArrayStack：メモリ効率に優れた配列スタック
2.7 ディスカッションと練習問題
第3章 連結リスト
3.1 SLList：単方向連結リスト
3.2 DLList: 双方向連結リスト
3.3 SEList：空間効率の良い連結リスト
3.4 ディスカッションと練習問題
第4章 スキップリスト
4.1 基本的な構造
4.2 SkiplistSSet：効率的なSSet
4.3 SkiplistList：効率的なランダムアクセスList
4.4 スキップリストの解析
4.5 ディスカッションと練習問題
第5章 ハッシュテーブル
5.1 ChainedHashTable: チェイン法を使ったハッシュテーブル
5.2 LinearHashTable：線形探索法
5.3 ハッシュ値
5.4 ディスカッションと練習問題
第6章 二分木
6.1 BinaryTree：基本的な二分木
6.2 BinarySearchTree：バランスされていない二分探索木
6.3 ディスカッションと練習問題
第7章 ランダム二分探索木
7.1 ランダム二分探索木
7.2 Treap: 動的ランダム二分探索木の一種
7.3 ディスカッションと練習問題
第8章 スケープゴート木
8.1 ScapegoatTree：部分的に再構築する二分探索木
8.2 ディスカッションと練習問題
第9章 赤黒木
9.1 2-4 木
9.2 RedBlackTree：2-4 木をシミュレートする二分木
9.3 要約
9.4 ディスカッションと練習問題
第10章 ヒープ
10.1 BinaryHeap：二分木を間接的に表現する
10.2 MeldableHeap：つなぎ合わせられるランダムなヒープ
10.3 ディスカッションと練習問題
第11章 整列アルゴリズム
11.1 比較に基づく整列
11.2 計数ソートと基数ソート
11.3 ディスカッションと練習問題
第12章 グラフ
12.1 AdjacencyMatrix：行列によるグラフの表現
12.2 AdjacencyLists：リストの集まりとしてのグラフ
12.3 グラフの走査
12.4 ディスカッションと練習問題
第13章 整数を扱うデータ構造
13.1 BinaryTrie：二分トライ木
13.2 XFastTrie：O(log log_n)) 時間での検索
13.3 YFastTrie：O(log log_n)) 時間のSSet
13.4 ディスカッションと練習問題
第14章 外部メモリの探索
14.1 BlockStore
14.2 B木
14.3 ディスカッションと練習問題
参考文献
索引
