Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People（図解でわかるアルゴリズム入門）

引用

Bhargava, A. Y. (2024). Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People (2nd ed.). Manning Publications.

章の要約

第2版は320ページ、13章からなり、Daniel Zingaroによる序文（foreword）、著者の序文、そして本書の使い方、対象読者、構成を説明する「本書について」の節がある。出版社によれば、400点を超える図、すべての章の演習問題とコードサンプル、Python 3に更新されたコード、木（二分探索木、平衡木、B木）とNP完全問題に関する新しい内容、現代のCPU上でのデータ構造の性能についての解説が含まれる。各章は読者が学ぶ内容の短い一覧で始まり、章末にはまとめ（Recap）が置かれている。

第1章：アルゴリズム入門

土台となる章である。最初のアルゴリズムとしての二分探索、実行時間とビッグO記法、実行時間の増え方の違い、最悪の場合の尺度としてのビッグO、そして非常に遅い実行時間の例としての巡回セールスパーソン問題を扱う。

第2章：選択ソート

メモリの仕組みから始め、読み取り、途中への挿入、削除について配列と連結リストを比較したうえで、選択ソートを導入する。この章は第1章のビッグO記法と対数を前提にすると明記している。

第3章：再帰

基底ケースと再帰ケース、スタックと呼び出しスタック、そして再帰のときに呼び出しスタックがどう振る舞うかを扱う。著者は読者に、コードを実際に動かし、少なくとも一つの再帰関数を紙とペンでたどるよう勧めている。この章では疑似コードも導入される。

第4章：クイックソート

一般的な問題解決の戦略としての分割統治法を扱い、その最初の主要な例としてクイックソートを示す。さらにビッグO記法を再び取り上げ、マージソートとクイックソートを比較し、平均の場合と最悪の場合を対比する。

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

ハッシュ関数とハッシュテーブルの一般的な用途（検索、重複の防止、キャッシュ）を扱い、続いて性能を決める内部の仕組み、すなわち衝突、性能、負荷率を説明する。

第6章：幅優先探索

ネットワークをモデル化する方法としてのグラフの導入、ステップ数の意味での最短経路を求める幅優先探索、キュー、有向グラフと無向グラフ、トポロジカルソートを扱う。

第7〜8章：木、平衡木

この版で新しく加わった章である。第7章はファイルのディレクトリを使って根付き木と二分木を定義し、深さ優先探索を導入して幅優先探索と対比し、木に基づく圧縮アルゴリズムとしてハフマン符号化を扱う。第8章は二分探索木と平衡が重要な理由、AVL木と回転、スプレー木、B木とその利点を導入する。

第9章：ダイクストラ法

辺に所要時間があるときの重み付きグラフと最短経路を、「ピアノとの物々交換」の例を通して扱い、ダイクストラ法がうまくいかない負の重みの辺と、実装も取り上げる。

第10章：貪欲法

貪欲戦略（教室のスケジューリング）、ナップサック問題と集合被覆問題、近似アルゴリズム、そして速い厳密解が知られていないNP困難な問題の見分け方を扱う。

第11章：動的計画法

ナップサック問題を再び取り上げ、動的計画法が表（グリッド）の上で部分問題から解を組み立てる様子を示す。グリッドがどう変わるかについての一連の問いを示し、例を通して新しい問題に対する動的計画法の解法を考える方法を示す。

第12章：k近傍法

機械学習への入口である。k近傍法による分類、推薦システム、特徴抽出、回帰、そしてこの手法の用途と限界を扱う。

第13章：次に進むべきところ

本書で扱わなかった10のアルゴリズム（線形回帰、転置インデックス、フーリエ変換、並列アルゴリズム、MapReduceなど）を簡単に紹介し、さらに読むべきものを案内する。

主要概念

第1〜4章：実行時間、ソート、再帰

• ビッグO記法：入力の大きさに応じてアルゴリズムの実行時間がどう増えるかを、最悪の場合について示す。
• 二分探索：整列済みのリストを繰り返し半分にする方法で、O(n)ではなくO(log n)となる。
• 配列と連結リスト：メモリの仕組みに結びついた、速い読み取りと、速い挿入・削除の対比。
• 再帰と呼び出しスタック：基底ケース、再帰ケース、そして保留中の呼び出しのスタック。
• 分割統治法：クイックソートのように、問題をより小さな場合に帰着させること。

第5〜9章：ハッシュテーブル、グラフ、木

• ハッシュテーブル：平均して定数時間の検索で、衝突と負荷率が性能を左右する。
• 幅優先探索：キューを使って重みなしグラフの最短経路を求める。
• 深さ優先探索とハフマン符号化：木の走査と、木に基づく圧縮アルゴリズム。
• 平衡木：データが変化しても検索を速く保つAVL木、スプレー木、B木。
• ダイクストラ法：辺の重みが負でないグラフにおける最短経路。

第10〜13章：難しい問題とその先

• 貪欲法と近似：局所的に最適な選択によって、NP困難な問題に対して良い答えを速く得る。
• 動的計画法：部分問題を先に解き、全体の問題へと積み上げる。
• k近傍法：特徴の類似度による分類と回帰。

批判的分析

長所

• 図と例を中心に組み立てられている。 出版社は400点を超える図を挙げており、公開されている各章の冒頭からその書き方がわかる。どの考え方も、アルゴリズムを述べる前に具体的な場面（再帰なら屋根裏部屋の鍵のかかったスーツケース、ハッシュテーブルなら食料品店、幅優先探索ならサンフランシスコを横切るバスの経路）から始まる。
• 短い本としては広い範囲。 320ページで二分探索からNP困難な問題、近似アルゴリズム、動的計画法、k近傍法まで扱い、最終章はさらなる話題を案内する。
• 更新された第2版。 木と平衡木に関する新しい章が第1版の空白を埋め、コードはPython 3で書かれ、ソースコードはGitHubで公開されている。
• 能動的な読み方を促す。 たとえば再帰の章は、コードを実行し再帰関数を手でたどるよう読者に求めており、出版社はすべての章に演習問題があるとしている。

短所

• 証明ではなく直観。 「高度な数学は不要」という出版社の方針のため、正しさや実行時間は導出されるのではなく例によって説明される。大学の講義を受ける学生には、証明のある教科書がやはり必要である。
• 各話題の扱いが短い。 図の多い320ページに13章を収めているため、一つのアルゴリズムに割ける紙幅は限られる。第13章は明示的に10の話題を概観するだけである。
• Pythonのみ。 すべてのコードはPythonで書かれているため、他の言語で作業する読者は自分で書き換える必要がある。

コースにおける位置づけ

本書はこのコースで最も視覚的な入口であり、Wengrowの A Common-Sense Guide to Data Structures and Algorithms と対になる。Wengrowはステップの数え方と日常的なコードの分析により多くの紙幅を割き、すべての演習問題に解答をつけている。Bhargavaは分析を軽くする代わりに、平衡木、ダイクストラ法、NP困難な問題、k近傍法など、より広いアルゴリズムの範囲を扱う。一方の説明が難しいと感じた読者は、もう一方に切り替えるとよい。

この2冊の後は、Goodrich、Tamassia、Goldwasserの Data Structures and Algorithms in Java と、Pat Morinの無料の Open Data Structures が、実装と証明を伴う大学レベルの本格的な扱いを提供する。Peter Brassの Advanced Data Structures とChris Okasakiの Purely Functional Data Structures は、ずっと後で読む専門書である。貪欲法と動的計画法の章は、アルゴリズムの講義へのやさしい予習にもなる。

本書の使い方

本書は、どの言語でも少しプログラミングができ、アルゴリズムを直観的に学びたい読者に向いている。独学のプログラマー、最初のデータ構造の講義の前や受講中の学生、技術面接の準備をする人などである。Pythonの経験があると役立つが、例はどれも短い。

実際的な読み方：

• 中核： 第1〜6章を順番に。ビッグO、配列とリスト、再帰、分割統治法、ハッシュテーブル、そしてグラフと、各章が前の章の上に築かれている。
• 木とグラフ： 第7〜9章。第8章の平衡木は最初は軽く読んでもよいが、第9章は第6章で始まった最短経路の話を完結させる。
• 問題解決の戦略： 第10〜11章。第11章は第10章のナップサック問題を再び取り上げるので、一緒に読むのがよい。
• 任意： 機械学習に関心のある読者には第12章、読書案内として第13章。

GitHubのリポジトリにあるPythonのコードを実行して入力を変えてみること、そして本書が勧めるように再帰関数やグラフ探索を手でたどることが大切である。次に進む前に各章の演習問題を解くこと。講義のためには、各まとまりの後に形式的な教科書の対応する章を読み、本書が省いている証明と分析を確認するとよい。