Data Structures and Algorithms in Java（Javaによるデータ構造とアルゴリズム）

引用

Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.

章の要約

本書は全15章、736ページで、巻末に参考文献と索引が付く。Wiley の説明によれば、演習は目的別に分けられている。確認問題は理解度を試し、創造問題は新しいクラスの作成を求め、プロジェクトはプログラム全体の作成を求める。データ構造の教科書の多くと違い、最初の2章を Java 言語とオブジェクト指向設計に充てており、最初のデータ構造である配列が登場するのは103ページである。

第1～2章：Java入門、オブジェクト指向設計

第1章は言語の復習で、クラスとオブジェクト、文字列、ラッパー、配列、列挙型、式、制御フロー、簡単な入出力、パッケージを扱う。最終節ではソフトウェア開発を工程として取り上げ、設計、擬似コード、コーディング、文書化とスタイル、テストとデバッグを説明する。第2章ではオブジェクト指向設計の目標、原則、パターンを述べたうえで、継承、インタフェースと抽象クラス、例外、キャストとジェネリクス、入れ子クラスを扱う。

第3章：基本的なデータ構造

最初に配列を扱い、ゲームの記録の保存、配列の整列、文字配列による簡単な暗号、二次元配列などを例に挙げる。続いて単方向、循環、双方向の連結リストをそれぞれ実装とともに示し、最後に同値性の判定とデータ構造の複製を取り上げる。

第4章：アルゴリズム解析

実験による評価とその限界から始め、「本書で用いる7つの関数」を導入し、ビッグオー記法による漸近解析へ進む。章末では、帰納法やループ不変条件など、簡単な正当化の手法を扱う。

第5章：再帰

階乗、英語の定規の描画、二分探索、ファイルシステムといった例から入り、再帰アルゴリズムの解析、線形再帰・二分再帰・多重再帰、再帰アルゴリズムの設計、Java で再帰が際限なく深くなる危険、末尾再帰の除去へと進む。Wiley によれば、この章は第6版で新設されたもので、以前は複数の章に分かれていた内容を集約している。

第6～7章：スタック、キュー、デック；リストとイテレータのADT

第6章は3つの構造をそれぞれ抽象データ型として示し、配列と、必要に応じて連結リストで実装する。応用として、配列の反転や、括弧と HTML タグの対応の検査がある。第7章はリストADT、動的配列の償却解析を伴う配列リスト、位置リスト、イテレータ、Java Collections Framework を扱い、ムーブ・トゥ・フロント・ヒューリスティックによるアクセス頻度の管理というケーススタディで終わる。

第8～9章：木；優先度付きキュー

第8章は一般の木と二分木を定義し、連結構造と配列による表現を示したうえで、走査（先行順、後行順、幅優先、中間順、オイラー・ツアー）に長い節を割く。第9章は優先度付きキューADTを定義し、未整列リスト、整列済みリスト、そしてヒープで実装する。さらに、優先度付きキューによる整列として選択ソート、挿入ソート、ヒープソートを示し、最後に適応型優先度付きキューを扱う。

第10～11章：マップ、ハッシュ表、スキップリスト；探索木

第10章はマップADT、ハッシュ表（ハッシュ関数、衝突処理、負荷率と再ハッシュ）、整列マップ、スキップリスト、集合・多重集合・多重マップを扱う。第11章は二分探索木と平衡化のための Java フレームワークから始め、AVL 木、スプレー木、(2,4)木、赤黒木を説明する。

第12～13章：整列と選択；テキスト処理

第12章はマージソートとクイックソート、比較整列の下界、バケットソートと基数ソート、整列アルゴリズムの比較、枝刈り探索による選択を扱う。第13章は文字列に移り、パターン照合（力任せ法、ボイヤー・ムーア法、クヌース・モリス・プラット法）、トライ、貪欲法によるテキスト圧縮、動的計画法を述べる。

第14～15章：グラフアルゴリズム；メモリ管理とB木

第14章はグラフADT、4通りのグラフ表現、深さ優先探索と幅優先探索、推移的閉包、トポロジカル順序、最短経路、最小全域木を扱う。第15章は言語の下の層に降り、Java 仮想マシンのスタックとヒープ、ガベージコレクション、メモリ階層とキャッシュ、B木、外部メモリでの整列を取り上げる。

主要概念

第1～5章：言語、設計、解析、再帰

• オブジェクト指向設計の原則とパターン：第2章で導入される用語で、以降の各構造がなぜそのように作られるのかを説明するために使われる。
• ジェネリクスとインタフェース：各抽象データ型を Java で表現するための仕組み。
• ビッグオーと漸近解析：以降のすべての構造で実行時間を測る尺度。
• 再帰：固有の解析方法と失敗の仕方を持つ技法で、独立した1章で扱われる。

第6～11章：線形構造、木、マップ

• 抽象データ型：操作だけで定めた仕様で、本書では Java のインタフェースと対にして示される。
• 償却解析：動的配列に用い、スプレー木には星印の付いた節で用いる。
• 位置リストとイテレータ：内部表現を見せずに、列の中の位置を扱えるようにする方法。
• ヒープ、ハッシュ表、平衡探索木：それぞれ優先度付きキュー、マップ、順序付きマップの中心となる構造。

第12～15章：アルゴリズムとシステム

• 分割統治による整列と整列の下界：マージソートとクイックソートの対比、および比較整列の限界。
• トライと動的計画法：テキスト処理の章の道具。
• グラフ走査、最短経路、全域木：グラフの章の中心。
• メモリ階層とB木：データ構造と計算機の実際の動作を結ぶ内容。

批判的分析

長所

• まずインタフェース、次に実装。 Wiley によれば、各ADTには対応する Java のインタフェースがあり、具体的な構造はそれを実装するクラスとして net.datastructures パッケージにまとめられ、Java Collections Framework を補う形で設計されている。第7章では本書の位置リストを Collections Framework と直接比較しており、学習用のコードからライブラリのコードへ移る助けになる。
• 意図された順序。 アルゴリズム解析（第4章）と再帰（第5章）は、それらに依存するスタック、木、整列より前に置かれている。最も難しい構造である平衡木（第11章）は、マップや優先度付きキューで型ができたあとに登場する。
• 目的別の演習。 確認問題、創造問題、プロジェクトに分かれているため、宿題には短い確認問題、課題にはプログラム全体、というように使い分けられる。
• 1冊としては広い範囲。 古典的な構造と並んで、テキスト処理、グラフアルゴリズム、外部メモリも扱っており、専門のアルゴリズムの講義への橋渡しとして使える。

短所

• Java の知識が前提になる面がある。 最初の約100ページは言語とオブジェクト指向設計に充てられている。必要な読者には助けになるが、すでに Java を書ける読者は読み飛ばすことになり、言語に依存しない扱いを望む読者は、コードがジェネリクス、イテレータ、入れ子クラスといった Java 特有の書き方に結びついていると感じるだろう。
• 新しい Java の機能は視野に入っていない。 Wiley の変更点の説明にあるのは Java 7 で導入された型推論で、目次にはそれ以降の言語機能をうかがわせるものがない。そのため、新しい Java の書き方で書いたコードは、印刷された例と見た目が異なる。
• アルゴリズムの扱いは簡潔。 テキスト処理は約40ページの1章、グラフは約75ページの1章にとどまり、これらの話題は掘り下げるというより導入するものである。
• 解析の重い節がある。 目次では、いくつかの節に星印が付いている（たとえばボトムアップのヒープ構築、スキップリストの確率的解析、スプレー木の償却解析）。初めて学ぶ読者は、これらを2周目に回すことになるだろう。

コースにおける位置づけ

本書は2つ目のコース向けの教科書である。最初のプログラミングの授業を終えていることを前提とし、1つの言語でデータ構造を組み立てていく。このコースの他の本のうち、Wengrow の A Common-Sense Guide to Data Structures and Algorithms と Bhargava の Grokking Algorithms は、より平易な、あるいは図解による入門書で、最初の通読や併読に使える。どちらも Java のクラスライブラリを軸に構成されてはいない。Pat Morin の Open Data Structures は、各構造に厳密なインタフェース、実装、実行時間の証明を付けて同じ範囲を扱い、Java、C++、擬似コードの版がオンラインで無料公開されている。Goodrich らの本があまり深く扱わない証明を補う第二の資料として自然である。

Brass の Advanced Data Structures はデータ構造をアルゴリズム設計として扱う大学院レベルの本で、コードは C で書かれている。Okasaki の Purely Functional Data Structures は関数型言語における不変なデータ構造を扱う。どちらも、本書の代わりではなく、本書の次に進む先として適している。

本書の使い方

最初のプログラミングの授業を終え、古典的なデータ構造を Java で実装したい学部2年次の学生に向いている。目次には独立した数学の章はなく、第4章で増加率を表す関数、ビッグオー記法、帰納法による証明が導入される。すでに Java を知っている読者は、第2章か第3章から始めてよい。

1学期の進め方の例：

• 中核： 第3章から第9章まで順に読む。第4章の解析を使う構造より前に、第4章を読んでおく。第5章は木の章より前に終えておく。
• 後半： 第10章と第11章（マップと探索木）、第12章（整列）。平衡木は講義の方針に応じて選ぶ（たとえば AVL 木と赤黒木）。
• 任意： 第13章から第15章は、アルゴリズムの講義への橋渡し、または自習用とする。初回は星印の付いた節を飛ばす。

コードは読むだけでなく書くこと。インタフェースからスタック、キュー、位置リストを実装し、それぞれを Java Collections Framework の対応するものと比べる。確認問題は各節の後に解き、創造問題とプロジェクトは各章の終わりにとっておく。