1. データ構造の戦略的選択：「その仕事に最適な道具を選ぶ」

データ構造の選択を間違えると、プログラムは不必要に遅くなります。各課題で、なぜそのコンテナが「最適」だったのかを見ていきましょう。

`std::map`（賢い辞書） - Ex00

内部的に**平衡二分探索木**でデータを保持し、常にキーでソートされた状態を維持します。これにより、**検索**が非常に高速になります。

データが100万件あっても、目的のデータにたどり着くのに必要なステップ数はわずか**20回**程度です。

`std::stack`（お皿の山） - Ex01

**「後入れ先出し（LIFO）」**というシンプルなルールで動作し、RPN計算のように「直近のデータを処理する」アルゴリズムと完璧に一致します。

ブラウザの「戻る」ボタンやエディタの「元に戻す」機能もこの仕組みです。

2. 理論を超えたハードウェアの現実：「CPUの気持ちを考える」

アルゴリズムの性能は理論だけで決まりません。データがメモリ上でどう配置されるかが、CPUの**キャッシュ効率**を通じて実際の速度に絶大な影響を与えます。

`vector`：キャッシュヒット 🚀

データが**連続したメモリ**にあるため、CPUは次に使うデータを高速なキャッシュに先読みでき、瞬時にアクセスできます。

`deque`：キャッシュミス 🐢

データが**断片化**しているため、CPUは毎回低速なメインメモリまでデータを取りに行く必要があり、遅延が発生します。

3. アルゴリズムの叡智：「賢さの尺度は時間だけではない」

Ford-Johnsonアルゴリズムは、処理時間ではなく**「比較回数」を最小化する**ことに特化しています。この「賢さ」を、より一般的な二分挿入法と比較してみましょう。

21個のランダムな整数をソートした際の比較回数を計測します。

Ford-Johnson

0

ヤコブスタール数で挿入順序を最適化し、無駄な比較を徹底的に排除します。

二分挿入法

0

効率的ですが、常に最善の比較順序を選べるわけではありません。