01 / 読書ガイド
読書ガイド
引用
Wengrow, J. (2020). A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills (2nd ed.). The Pragmatic Bookshelf.
章の要約
第2版は506ページ、20章からなり、各章は「Wrapping Up（まとめ）」と演習問題で終わる。その後に全章の演習問題の解答を収めた付録が続く。序文では、本書の対象読者、この版の新しい点、読み方、コード例、オンライン資料について述べている。出版社はソースコードをダウンロード用に提供している。コード例はJavaScript、Python、Rubyで書かれている。出版社によれば、第2版ではすべての章に演習問題が加わり、再帰、動的計画法、日常のコードでのビッグO記法の使い方、ヒープとトライに関する新しい章が追加された。
第1〜3章：なぜデータ構造が重要なのか、なぜアルゴリズムが重要なのか、O Yes! ビッグO記法
本書の方法は、無料の抜粋として公開されている第1章で示される。操作の速さは時間ではなく、その操作にかかるステップ数で測る。この章では配列に対する読み取り、検索、挿入、削除のステップ数を数え、次に配列を集合（セット）と比較する。集合では「重複を許さない」という一つの規則が挿入のコストを変える。第2章は整列済み配列を導入して二分探索と線形探索を比較し、第3章はステップ数の数え方を、対数とO(log N)を含むビッグO記法へとまとめ上げる。
第4〜6章：ビッグOでコードを速くする、ビッグOを使う最適化と使わない最適化、楽観的なシナリオのための最適化
3つの章で単純なソートを用いて分析を深める。バブルソート（無料の抜粋）は二次の計算量をもつアルゴリズムと、二次の解法を線形の解法に置き換える方法を示す。選択ソートは、ビッグOが定数を無視する理由と、同じ分類に属する二つのアルゴリズムでも違いが出ることを示す。挿入ソートは最良・最悪・平均の場合を導入する。
第7章：日常のコードにおけるビッグO
第2版で新設され、これも抜粋として公開されている章で、短く実用的な関数に分析を適用する。偶数の平均、単語の組み立て、配列からの標本抽出、衣料品のラベル付け、回文判定、商品の一覧、パスワード解読などである。冒頭では、現在のビッグOを判定することがコード最適化の第一歩だと説明している。
第8〜9章：ハッシュテーブルによる超高速な検索、スタックとキューで洗練されたコードを書く
ハッシュテーブルは、ハッシュ関数、衝突、効率的なハッシュテーブルの条件を通して扱われ、データの整理とコードの高速化の両方の用途が示される。スタックとキューは、制約のあるデータ構造、そして抽象データ型として提示される。
第10〜13章：再帰で再帰的に再帰する、再帰的に書くことを学ぶ、動的計画法、速さのための再帰的アルゴリズム
再帰のまとまりは、再帰的なコードの読み方と基底条件から始まり、再帰的な問題の類型とトップダウンの考え方（階段問題、アナグラム生成）を経て、メモ化とボトムアップによる動的計画法へと進む。第13章は再帰を分割（パーティション）、クイックソートとその最悪の場合、クイックセレクトに応用し、ソートが他のアルゴリズムの鍵になりうることにも触れる。
第14〜17章：ノードベースのデータ構造、二分探索木ですべてを速くする、ヒープで優先順位を守る、トライ（Trie）してみよう
連結リストと双方向連結リスト（それを用いたキューを含む）、挿入・削除・走査を伴う二分探索木、優先度付きキューとしてのヒープ（配列へのヒープの格納や「最後のノード」問題を含む）、そしてオートコンプリートの構築に用いるトライを扱う。
第18章：グラフですべてをつなぐ
有向グラフ、オブジェクト指向による実装、深さ優先探索と幅優先探索とその効率、重み付きグラフとダイクストラ法を扱う。
第19〜20章：空間の制約への対処、コード最適化のテクニック
第19章はビッグOをメモリに拡張し、時間と空間のトレードオフと、再帰に隠れた空間コストを論じる。第20章は実践的な最適化戦略をまとめる。現在のビッグOから出発し、想像しうる最良のビッグOを考え、「魔法のような検索（magical lookups）」を探し、パターンを見つけ、貪欲法を使い、データ構造を変えることである。
主要概念
第1〜7章：効率の測定
- 秒ではなくステップ：操作の速さはその操作にかかるステップ数であり、ハードウェアに依存しない。
- ビッグO記法：N個のデータ要素に対してステップ数がどう増えるかを、定数を無視して表す。
- 最良・最悪・平均の場合：同じアルゴリズムでも入力によって振る舞いが変わる理由。
- 二分探索：整列済み配列を各ステップで半分にする方法で、O(log N)の源である。
第8〜13章：検索、制約、再帰
- ハッシュテーブル：ハッシュ関数によるキーに基づく検索で、衝突を処理して検索を速く保つ。
- 抽象データ型：許される操作によって定義されるスタックとキュー。
- 再帰と基底条件：問題を自分自身のより小さな場合によって解くこと。
- メモ化とボトムアップの動的計画法：重なり合う部分問題に対する再帰呼び出しの繰り返しをなくすこと。
第14〜18章：ノードベースの構造
- 連結リスト：リンクでつながれたノードで、配列とは読み取りと挿入のコストが異なる。
- 二分探索木とヒープ：高速な検索のため、あるいは最も優先度の高い要素に素早くアクセスするために順序づけられた木。
- グラフ探索とダイクストラ法：深さ優先・幅優先の走査と、重み付きグラフにおける最短経路。
第19〜20章：空間と最適化
- 空間計算量：メモリに適用したビッグOで、再帰が使う呼び出しスタックも含む。
- 最適化のテクニック：より速いアルゴリズムを見つけるための意識的な戦略。
批判的分析
長所
- 効率についての単一で具体的な考え方。 無料の第1章がその方法を示している。速さに関する主張はすべて、記法が登場する前に小さな例でステップを数えることに還元されるので、読者は定義からではなく経験からビッグOを組み立てる。
- 普通のコードの分析。 第7章は実際のコードベースにあるような短い関数を分析し、第20章は分析を最適化の習慣へと変える。そのため理論が、現役のプログラマーが書くコードと結びついている。
- 完全な解答つきの演習問題。 すべての章が演習問題で終わり、付録には全20章の解答があるので、独習に使いやすい。
- 複数言語の例。 JavaScript、Python、Rubyの例は、現役のWeb開発者にとってコードを身近なものにしている。出版社はプログラミング以外の前提条件を挙げていない。
短所
- 非形式的な分析。 ビッグOはステップ数の数え方を通して導入される。目次には形式的な定義、正しさの証明、漸化式の解法が見当たらないため、理論の講義に進む学生にはより厳密な教科書が必要になる。
- 範囲の取捨選択。 マージソート、平衡探索木、最小全域木などの標準的なアルゴリズムは節見出しに現れない。本書は中核的な構造を扱うが、大学の講義の全範囲を網羅するわけではない。
- 動的型付け言語の例のみ。 コードはJavaScript、Python、Rubyで書かれており、講義でJavaやC++を使う学生は実装を自分で書き換える必要がある。
コースにおける位置づけ
このコースの中で本書は、Bhargavaの Grokking Algorithms と並ぶやさしい最初の一冊である。どちらもプログラミングはできるがコンピュータサイエンスの素養のない読者に向いている。Wengrowはステップの数え方と日常的なコードの分析により多くの紙幅を割き、解答つきの演習問題を備えている。一方Bhargavaは図解により多く頼り、貪欲法や近似アルゴリズムといった話題も扱う。どちらを先に読んでもよく、同じ中核的な考え方について二通りの説明がほしい読者には両方読むのも妥当である。
本書の後、コースは本格的な教科書へと進む。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 は、ずっと後で読む専門書である。
本書の使い方
本書は、日々の仕事のためにデータ構造とアルゴリズムを理解したいプログラマーを対象としている。独学やブートキャンプで学んだ開発者、最初のデータ構造の講義を受ける学生も含まれる。前提はどの言語でもよい基本的なプログラミングと学校で習う算数だけであり、対数は第3章で説明される。
実際的な読み方：
- 中核（順番に）： 第1〜9章。本書の分析は積み重ねで築かれており、第7章の実際のコードの分析は丁寧に取り組む価値がある。
- 再帰のまとまり： 第10〜13章をひとまとまりとして読む。動的計画法の第12章はその前の2章に依存する。
- データ構造： 第14〜18章。時間が足りなければ、最初はヒープとトライ（第16〜17章）を飛ばしてもよいが、グラフ（第18章）は飛ばさないこと。
- 総まとめ： 第19〜20章は本書を締めくくる章で、技術面接や講義の試験の前の復習に向いている。
各章の演習問題は解答を読む前に解くこと。ダウンロードできるコードを、最もよく使う言語で打ち込んで実行し、同じ処理の遅い版と速い版の時間を測って、ステップ数の違いを実際に確かめるとよい。大学の講義を受けている場合は、本書の各まとまりの後に形式的な教科書の対応する章を読み、形式的な扱いがわかりにくくなったときに本書の説明を使うとよい。
