体系ガイド · 入門

データ構造を、必要な操作から選ぶ

配列・連結リスト・ハッシュ表・ヒープを、検索、追加、削除、順序の要件に対応させて選びます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 先に、よく行う操作を書き出す
  2. 配列と連結リストの違いを条件付きで読む
  3. 検索と優先度付き取り出しを比べる
  4. 処理順の要件を、小さな例で確かめる
  5. この記事をロゲイアに質問する理解を確かめる

先に、よく行う操作を書き出す

データ構造は、データの置き方と、それを扱う操作を組み合わせた設計です。「一番速い構造は何か」と考える前に、添字で読むのか、キーで探すのか、最小値を取り出すのか、先頭から順に処理するのかを決めます。件数と操作の頻度も、選択に大きく関わります。

例えば、注文番号から1件を探す要件と、締切が早い仕事を繰り返し取り出す要件では、求める操作が異なります。前者にはハッシュ表など、後者にはヒープなどが候補になります。同じデータを持つ場合でも、必要な操作を言葉にすると、比較する構造が明確になります。

配列と連結リストの違いを条件付きで読む

配列は添字から位置を求めやすく、要素を順に読む際の局所性にも利点があります。一方、途中へ要素を挿入すると、後ろの要素を移動させる必要がある構成もあります。動的配列の末尾追加は、容量を増やす回には多くのコピーが生じても、一連の追加を通した償却コストで説明できます。

連結リストの挿入をO(1)と説明するときは、挿入位置のノードなど必要な参照がすでに分かっているという条件が重要です。「1000番目へ挿入する」ために先頭からたどる仕事まで含めれば、その探索時間は別に必要です。参照を維持するメモリや、実機でのアクセスの局所性も考慮しましょう。

検索と優先度付き取り出しを比べる

ハッシュ表はキーのハッシュ値を使って候補を絞ります。適切なハッシュ関数と負荷率のもとで期待できる高速な検索を、あらゆる入力で必ず一定時間だと読み替えてはいけません。衝突、再配置、キーの計算コスト、実装の対策が影響します。範囲検索や値順の走査が主な目的なら、順序を持つ別の構造も候補です。

二分ヒープでは、根から最小値などの優先要素を得られます。根の参照と、その要素を削除して構造を整える操作は区別します。例えば、締切が最も早い仕事を繰り返し選ぶなら、毎回全件をソートし直す以外の方法を検討できます。ただし、任意の注文番号を直接探す用途に、ヒープがそのまま最適とは限りません。

処理順の要件を、小さな例で確かめる

受付順に3件の仕事A、B、Cを処理するなら、キューはA、B、Cの順に取り出します。最後に積んだものを先に扱うスタックなら、取り出し順はC、B、Aです。この違いは、探索の順序、履歴の取り消し、待ち行列などの実装に直結します。名前よりも、操作後の状態を手で追うことが理解の助けになります。

計算量は規模を増やしたときの仕事の増え方を比較する道具です。定数倍、メモリ消費、キャッシュ、同期、既存ライブラリの品質は、それだけでは決まりません。まず意味と必要な操作を合わせ、次に計算量と実装条件を比べ、性能が重要な箇所は代表的な負荷で測る、という順に進めましょう。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ