データ構造が性能を変える。
C++ Module 09の課題を元に、データ構造の選択がアルゴリズムの性能にどう影響するかをインタラクティブに探求します。テキストを読むだけでなく、実際に操作して計算量の違いを体感してください。
最適な「検索」方法とは？
この課題では、膨大な価格データから特定の日付を効率的に見つけ出す必要がありました。`std::map`（平衡二分探索木）がいかに優れているかを、線形探索を行う`std::list`と比較して見てみましょう。
スライダーを動かしてデータ件数を変更し、検索に必要な「計算ステップ数」がどのように変化するか観察してください。
逆ポーランド記法を入力して計算を開始してください。
スタックの「後入れ先出し」
逆ポーランド記法の計算は、「後入れ先出し (LIFO)」の`std::stack`に最適です。数字をスタックに積み、演算子が現れると2つ取り出して計算する様子をアニメーションで見てみましょう。
計算ボタンを押すと、スタックの動きがステップごとに表示されます。
アクセス vs 挿入のトレードオフ
`std::vector`はランダムアクセスが高速ですが、要素の挿入コストが高いです。一方、`std::deque`は挿入が得意です。マージ挿入ソートにおいて、この違いが全体の処理時間にどう影響するかを比較します。
要素数が増えると、挿入コストの高さが`vector`の弱点となり、`deque`が有利になる傾向が見られます。