データ構造入門 — Project Hematite

プログラムの動き方では、すべてのプログラムが同じループに従うことを学んだ：情報を受け取り、処理し、結果を出す。情報が複数になった瞬間、プログラム自身には答えられない問いが生まれる。その情報はどのように保存すべきか？

この答えは、見た目以上に重要だ。

「ひとまとめ」の問題

連絡先アプリを作っているとしよう。名前と電話番号のリストがあり、ユーザーは名前で番号を調べる。シンプルな要件だ。

では、そのアプリに 1000 万件の連絡先があるとしたら。ユーザーが名前を入力して、1 秒以内に結果を期待する。プログラムが先頭からひとつずつ全件を調べる必要があるなら、平均 500 万件を確認してようやく目的のものにたどり着く。高速な現代のマシンでも数秒かかるかもしれない。電話アプリとしては使い物にならない。

データは同じだ。結果を左右するのは、そのデータを整理する方法だ。

電話帳は「ひとまとめ」ではない — アルファベット順に並んでいるから、だいたいのページを開いて短い範囲をざっと見ればいい。その構造によって、500 万ステップの検索が数十ステップに変わる。情報は変わっていない。変わったのは整理のしかただ。

データ構造（data structure）は、こうした整理の選択を形式化したものだ。データ構造とは、データをメモリ上に配置する方法と、それを操作するための定義済みの手続きの集合のことだ。配置の仕方によって、どの操作が速くてどの操作が遅いかが決まる。

操作と効率

どのデータ構造も、何らかの操作（operation）の集合をサポートする。すべての構造に共通する最も基本的な4つは次のとおりだ：

アクセス（access） — 特定の位置にある要素を取得する。
検索（search） — ある値が存在するかどうか（またどこにあるか）を調べる。
挿入（insert） — 新しい要素を追加する。
削除（delete） — 既存の要素を取り除く。

4つすべてを同等に得意とする構造は存在しない。アクセスを瞬時に行える配置は挿入を遅くするかもしれない。挿入が安価な構造は検索が高コストになりうる。データ構造を選ぶとは、どの操作を速くしたいかを選び、その代償として生じるトレードオフを受け入れることだ。

効率を測る：最初の視点

構造のパフォーマンスを比較するとき、機械ごとに異なる絶対的な実行時間よりも、データが増えたときに時間がどうスケールするかのほうが重要だ。鍵となる問いはこうだ：要素数が 2 倍になったとき、処理にかかる時間はどうなるか？

2つのカテゴリが常に登場する：

定数時間（constant time） — 要素数に関係なく、操作にかかる仕事量が一定だ。データが 2 倍になっても何も変わらない。これが最善の性質だ。
線形時間（linear time） — 操作の仕事量が要素数に比例して増える。データが 10 倍になれば、仕事も 10 倍になる。

後のチェックポイントでこの考え方を厳密に発展させ、正式な記法を導入する。今は「定数」と「線形」という言葉を知っておけば、構造間のトレードオフを語るのに十分だ。

これから学ぶ構造

以降のチェックポイントでは、5つの基本的な構造を紹介する。それぞれの概観を示そう：

配列

配列（array）は要素を連続したメモリブロックに、ひとつずつ隣り合わせに格納する。このレイアウトによって、位置を指定して任意の要素に到達するのが定数時間になる — 先頭からスキャンする必要がない。配列は最もシンプルで広く使われる構造であり、多くの他の構造のベースにもなっている。

トレードオフ：中間に要素を挿入・削除するには前後の要素をずらす必要があり、配列のサイズに比例した時間がかかる。

連結リスト

連結リスト（linked list）は各要素を独立したノードに格納する。各ノードはその値と、次のノードへの参照を持つ。ノードはメモリのどこに散在していてもよく、連続したブロックは不要だ。

中間への挿入・削除は安価だ：参照を数本更新するだけで、リストのサイズに関係ない。トレードオフ：位置 $i$ の要素に到達するには先頭から順にたどる必要があり、近道はない。

スタック

スタック（stack）は特定の規律を強制する構造だ：要素は一方の端（トップと呼ぶ）でしか追加・削除できない。最後に追加した要素が必ず最初に取り出される — 後入れ先出し（LIFO: Last In, First Out）だ。

この制約は制限に見えるが、驚くほど多くの実際の問題に自然に対応する：シーケンスの逆順処理、ナビゲーション中の経路追跡、そしてプログラムが内部で関数呼び出しを管理する仕組みなどだ。

キュー

キュー（queue）はスタックの鏡写しだ。要素は一方の端（後ろ）から追加され、もう一方の端（前）から取り出される — 先入れ先出し（FIFO: First In, First Out）だ。コーヒーショップの行列のようなもので、最初に来た人が最初に接客される。

キューは、到着順に処理しなければならないものすべてに自然なモデルだ：ウェブサーバーへのリクエスト、動画ストリームのフレーム、実行待ちのタスクなど。

ハッシュマップ

ハッシュマップ（hash map、辞書または連想配列とも呼ぶ）はキーと値のペアを格納し、ペアの数に関係なくキーで値を定数時間で参照できる。キーを数学的な関数に通してメモリ上の格納・検索場所を直接求めることで、スキャンが一切不要になる。

トレードオフ：要素に意味のある順序がなく、ソートされたアクセスを必要とする操作はコストが高い。

中心テーマ：最善の構造は唯一ではない

5つのデータ構造を学んだあと、自然と「どれを使えばいいか？」という問いが生まれる。答えは常に同じだ：何をしたいかによる。

必要な操作	選ぶべき構造
位置による高速アクセス	配列
中間での頻繁な挿入・削除	連結リスト
履歴の追跡、シーケンスの逆順処理	スタック
到着順に項目を処理	キュー
名前やキーによる高速検索	ハッシュマップ

実際のプログラムでは複数の構造を同時に使うことが多い。ウェブサーバーなら、受信リクエストをキューで保持し、各リクエストのセッションデータをハッシュマップで検索し、返却する項目を配列に格納する、といった具合だ。

データ構造を学ぶのはカタログを暗記するためではない。問題を見て、どの操作が最も重要かを見極め、適切な道具を選ぶ判断力を鍛えるためだ。

まとめ

データ構造とは、データをメモリ上に整理する方法と、それを操作する手続きの集合のことだ。整理の仕方がどの操作を速くするかを決める。
4つの基本操作はアクセス、検索、挿入、削除だ。すべての構造はこれらの間でトレードオフを行う。
定数時間の操作はデータセットの大きさに関わらず仕事量が一定だ。線形時間の操作はデータに比例して増える。
このシリーズで扱う5つの構造は：配列（高速な位置アクセス）、連結リスト（シーケンス中間の安価な変更）、スタック（LIFO 規律）、キュー（FIFO 規律）、ハッシュマップ（高速なキー検索）だ。
最善の構造は唯一ではない。構造の強みを、プログラムが実際に最も多く行う操作に合わせることが、良い選択への道だ。