※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 学問の宇宙・応用の軌道ステーション群「作る力と生きる力シリーズ」計算機文明部 第4巻。ガイド役: Fable 5 監修 / Sonnet 5 執筆(脚本班)
> トーン規約: GAKUMON_UNIVERSE.md準拠。専門用語は初出で必ず説明する。
> **安全枠(§16.18・絶対厳守)**: 本冊は教育目的の概念解説であり、実装例は教育用の小さな擬似コードにとどめる。特定のプログラミング言語による実装や、実機での性能測定は範囲外とする。
> 接続先: →BOOK-0341『自分の言語を作る』第1巻(字句解析・構文解析の基礎)、→BOOK-0066『情報派生: アルゴリズムとデータ構造』第1巻(探索・整列・計算量の基礎はそちらが土台になっている)、→BOOK-0345『要件定義とデザイナー思考』(どの構造を選ぶかという判断も、結局は要件定義の一種である)。
> 水準: 一〜十二(なぜ一列に並べるだけでは足りないのかという入口から、木構造・グラフが実際の問題をどう解決するかまでを、年代順の比較史を交えて積み上げる)。
# BOOK-0343 作る力と生きる力シリーズ: 計算機文明部 第4巻 情報構造の設計 — 一列の棚から、枝分かれする地図へ
> 学問の宇宙・応用の軌道ステーション群「作る力と生きる力シリーズ」計算機文明部 第4巻。ガイド役: Fable 5 監修 / Sonnet 5 執筆(脚本班)
> トーン規約: GAKUMON_UNIVERSE.md準拠。専門用語は初出で必ず説明する。
> **安全枠(§16.18・絶対厳守)**: 本冊は教育目的の概念解説であり、実装例は教育用の小さな擬似コードにとどめる。特定のプログラミング言語による実装や、実機での性能測定は範囲外とする。
> 接続先: →BOOK-0341『自分の言語を作る』第1巻(字句解析・構文解析の基礎)、→BOOK-0066『情報派生: アルゴリズムとデータ構造』第1巻(探索・整列・計算量の基礎はそちらが土台になっている)、→BOOK-0345『要件定義とデザイナー思考』(どの構造を選ぶかという判断も、結局は要件定義の一種である)。
> 水準: 一〜十二(なぜ一列に並べるだけでは足りないのかという入口から、木構造・グラフが実際の問題をどう解決するかまでを、年代順の比較史を交えて積み上げる)。
---
## 入口の物語 — 一万個目の荷物を探せなかった日
配送センターに配属された新人整理係は、初日に紙の台帳を渡された。荷物が届くたびに、伝票番号と行き先を台帳の一番下の行に書き足していく。仕事はそれだけだった。ところが数か月後、台帳の行数が千行を超えたころ、ある客が「先週送った荷物がまだ届かない、伝票番号は0731番のはずだ」と問い合わせてきた。新人整理係は台帳を一行目から指でなぞり始めた。百行、二百行……探しても探しても0731番が出てこない。結局、最後から数行手前でようやく見つかったときには、20分近くが経っていた。
客を待たせている間、新人整理係の指は同じページを何度も行き来し、額には汗がにじんでいた。ようやく見つけたときには、客はすでに苛立ちを隠せない様子だった。「一列に並べて書き足すだけの台帳は、荷物が少ないうちは何の問題もない」と、様子を見ていた主任が言った。「でも数が増えると、後ろのほうにある1件を探すのに、前から全部読む羽目になる。これは台帳の作り方そのものの限界であって、君の探し方が下手なわけじゃない」。
新人整理係は納得しかけたが、すぐに別の疑問がわいた。「じゃあ、伝票番号の順に並べ替えておけばいいんですか」。主任はうなずいた。「そのとおり。でも並べ替えておくと、今度は新しい荷物が来るたびに、正しい位置に割り込ませる作業が面倒になる。探すのが速くなると、しまうのが遅くなる。しまうのを速くすると、今度は探すのが遅くなる――このトレードオフ(何かを得ると別の何かを失う関係)をどう解決するかという問題に、計算機の世界は何十年もかけて取り組んできたんだ」。
この一言が、本冊の出発点になる。一列に並べる「配列」という最も素朴な発想から出発し、なぜ連結リストが生まれ、なぜ木構造が生まれ、なぜグラフが生まれたのか――その一つひとつが「前の構造のどこが不便だったから、次の構造が発明されたのか」という年代的な比較史として積み重なっている。荷物1000個前後を扱う配送センターを例に、数値を実際に検算しながら、この階段を一段ずつ登っていく。
---
## 第一章: 一列に並べる発想の基礎とその限界(水準一〜二)
### 配列という最も素朴な入れ物
同じ種類のデータを、途切れなく連続した番地に並べて収める入れ物を**配列(はいれつ、水準一: 同じ種類のデータを、連続した番地〈インデックス〉に並べて収める、最も基本的なデータ構造)**と呼ぶ。配送センターの台帳のように、荷物が届いた順に行を足していくだけの記録方法は、まさに配列そのものである。配列の強みは、番地(インデックス)さえ分かれば、その中身に一瞬でアクセスできる点にある。たとえば「到着順で500番目に受け付けた荷物」を知りたいだけなら、台帳の500行目を開くだけで済み、これはO(1)(データ件数によらず一定の手間)で完了する。しかし「伝票番号0731番はどの行にあるか」という問いに対しては、番地が事前に分からない以上、この強みは使えない。
### 検算1 — 線形探索の回数
台帳の先頭から一行ずつ確認していく探し方を**線形探索(せんけいたんさく、水準一: データの先頭から順番に一つずつ確認し、目的のものを見つける探索方法)**と呼ぶ。以後、本冊では配送センターが荷物1,024件前後を扱う場面を例に取る(1,024=2の10乗という、後の章の検算にもつながるきりのよい数である)。
```
最悪の場合(目的の荷物が最後の行にある、または存在しない):1,024回の確認が必要
平均の場合:(1 + 1,024) ÷ 2 = 512.5回 → およそ512〜513回の確認が必要
```
この「データの件数Nに対して、確認回数がおおよそNに比例して増えていく」という増え方を**O(n)(オーダーエヌ、水準二: アルゴリズムの手順の回数が、データ件数nにほぼ比例して増えていくことを表す計算量の書き方)**と表す。台帳が1,024行から2,048行に倍増すれば、探索にかかる手間もおよそ倍になる――これが線形探索の限界である。
---
> **定着量の目安(第一章)**: 配列と線形探索の定義、およびO(n)という書き方を身につけるには、件数を変えた「最悪何回・平均何回」の見積もりドリルを15問程度こなすと、水準一〜二の内容がほぼ定着すると見込まれる。
---
## 第二章: 並べ替えて武器にする、そして新たな壁(水準三〜四)
### ソート済み配列と二分探索
台帳を伝票番号の順に**整列(せいれつ、ソート、水準三: データを大小関係などの決まった順序に並べ替える処理)**しておくと、真ん中の行だけを確認し、探している番号がそれより大きいか小さいかで、確認すべき範囲を半分に絞り込める。この方法を**二分探索(にぶんたんさく、水準三: 整列済みのデータに対し、真ん中の要素と比較しながら探索範囲を半分ずつに絞り込んでいく探索方法)**と呼ぶ。
### 検算2 — 二分探索は何回で1件に絞り込めるか
1,024件の台帳で二分探索を行うと、範囲は次のように半分ずつ狭まっていく。
```
1,024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
(半分にする操作を10回繰り返すと1件に絞り込める。2の10乗=1,024だから)
```
最悪でも10回の確認で1件が見つかる。線形探索の平均512.5回と比べると、
```
512.5 ÷ 10 = 51.25倍
```
およそ51倍速いという計算になる。件数が増えるほどこの差は開いていく――これが「O(log n)(オーダーログエヌ、水準三: 確認回数が、データ件数nの対数〈2倍になっても確認回数は1回しか増えない〉に比例して増えていく計算量)」という増え方の強さである。
### 検算3 — 整列済み配列に割り込ませるコスト
問題は、ここに新しい荷物を割り込ませるときに起きる。伝票番号順に並んだ1,024件の配列の、ちょうど真ん中あたりに新しい1件を挿入したいとする。配列は連続した番地に隙間なく詰まっているため、挿入したい位置より後ろにある要素を、すべて1つずつ後ろへずらして空き番地を作らなければならない。
```
挿入位置が先頭に近いほど、ずらす要素の数は増える
先頭に挿入する場合:最大1,023個の要素をずらす必要がある(O(n))
```
探索は速くなったのに、挿入は逆に重い作業になってしまった。「探すのが速くなると、しまうのが遅くなる」という主任の言葉が、ここで具体的な数値として姿を現す。
---
> **定着量の目安(第二章)**: `2の10乗=1,024`という関係と二分探索の絞り込み手順、および整列済み配列への挿入コストの見積もりを身につけるには、二分探索の回数ドリルと挿入コストの見積もりドリルを合わせて20問程度こなすと、水準三〜四の内容がほぼ定着すると見込まれる。
---
## 第三章: 鎖でつなぐ発想と、欲張りな木構造(水準五〜六)
### 連結リストの発明 — 挿入を軽くする代わりに失うもの
1950年代、初期の記号処理プログラム(人工知能の草分けとされる「ロジック・セオリスト」など)を開発していたアレン・ニューウェル、クリフ・ショー、ハーバート・サイモンらが1955〜56年ごろに考案したとされるIPL(Information Processing Language、情報処理言語)や、ジョン・マッカーシーが1958年に発表したLisp(リスプ)という言語では、データを「値」と「次のデータの場所」の組で表す方式が広く使われた。この発想を一般化した**連結リスト(れんけつリスト、水準五: 各データが「次のデータの場所」を示す情報〈ポインタ〉を持つことで、鎖のようにつながったデータ構造)**は、荷物に「次の荷物はこの棚」という付箋を貼っていくイメージに近い。
連結リストに新しいデータを挿入するには、前後のポインタを2本だけ繋ぎ替えればよく、後ろの要素を全部ずらす必要がない。挿入したい位置がすでに分かっているなら、この繋ぎ替えはO(1)(データ件数によらず一定の手間)で済む。ただし引き換えに、番地を指定して一瞬でアクセスするということができなくなる。目的のデータを探すには、先頭から鎖をたどるしかなく、二分探索のような「真ん中に一気に飛ぶ」芸当は使えない――探索は結局O(n)に逆戻りしてしまう。なお、この「値と、次の場所へのつながり」という発想そのものは、→BOOK-0341『自分の言語を作る』第1巻で扱われる、プログラムの文をひとまとまりずつ鎖のようにつないでいく構文木の考え方にも通じている。
### 二分探索木の登場 — 探索も挿入も両方欲しい
「探索は配列並みに速く、挿入は連結リスト並みに軽く」という欲張りな要求に応えるため、1960年前後、P.F.ウィンドリーやT.N.ヒバードといった複数の研究者がほぼ同時期に、鎖の発想と大小関係による絞り込みを組み合わせた構造を整理したとされる。これが**二分探索木(にぶんたんさくぎ、水準六: 各節〈ノード〉が最大2つの子を持ち、「左の子は自分より小さい値、右の子は自分より大きい値」という規則を守って値を配置した木構造)**である。
木構造は、根(ルート)と呼ばれる頂点から枝分かれし、各節が親子関係でつながる形をしている。二分探索木では、目的の値を探すとき、根から出発して「大きいか小さいか」を見て左右どちらかの枝に進む、を繰り返すだけでよい。
### 検算4 — 均整の取れた木の高さ
節の数がちょうど1,023個の二分探索木が、左右対称できれいに均整の取れた状態(完全二分木)になっているとする。木の高さ(根から最も深い葉までの段数)をhとすると、完全二分木の節の総数は2の(h+1)乗−1で表せるので、
```
2の(h+1)乗 − 1 = 1,023
2の(h+1)乗 = 1,024 = 2の10乗
h + 1 = 10 → h = 9(根を1段目に数えると、最大10段)
```
最悪でも10段たどるだけで1件に到達できる――二分探索とほぼ同じ速さである。しかも挿入は、この10段の道筋をたどって空いている場所に新しい節をぶら下げるだけでよく、後ろの要素をずらす必要がない。均整さえ取れていれば、探索も挿入もO(log n)で両立する、というのが二分探索木の狙いである。
---
> **定着量の目安(第三章)**: 連結リストと二分探索木、それぞれの「速いところ・遅いところ」の対比表を自分の手で書き出す練習と、完全二分木の節数と高さの関係`2の(h+1)乗−1=節数`を使った計算ドリルを20問程度こなすと、水準五〜六の内容がほぼ定着すると見込まれる。
---
## 第四章: 偏った木という落とし穴と、保険としての平衡木・ハッシュ(水準七〜八)
### 検算5 — 偏った木は配列に逆戻りする
均整さえ取れていれば、という条件には落とし穴がある。もし荷物の伝票番号が1番から1,000番まで、すでに整列された順に1件ずつ二分探索木へ挿入していったらどうなるか。新しい値は常にそれまでの最大値より大きいので、必ず一番右の枝にぶら下がり続ける。
```
1を挿入→根
2を挿入→1の右の子
3を挿入→2の右の子
…(以下同様に右へ右へと1本の鎖が伸びる)
1,000を挿入→999の右の子
木の高さ=999段。1,000番を探すには根から999段たどる必要があり、
これは線形探索の最悪回数(1,000回)とほぼ同じ手間になる
```
木という形をしていても、中身は連結リストと変わらないO(n)の構造に成り下がってしまった。「木構造さえ使えば必ず速い」という思い込みは誤りであり、挿入する順序次第で最悪の性能に転落しうる、というのがこの検算から読み取れる教訓である。
### 平衡木の発明 — 崩れない木という保険
この弱点への対策として、1962年にソ連の数学者ゲオルグ・アデルソン=ベリスキーとエフゲニー・ランディスが、左右の部分木の高さの差を常に1以内に保つよう、挿入・削除のたびに木の形を自動的に調整する仕組みを考案した。二人の頭文字から**AVL木(エーブイエルぎ、水準七: 左右の部分木の高さの差が常に1以内になるよう、挿入・削除のたびに自動的に形を調整する二分探索木)**と呼ばれ、最初の実用的な平衡木(へいこうぎ、高さが常にO(log n)に収まることが保証された木構造)とされている。1972年にはルドルフ・バイヤーが、後に「赤黒木(せきこくぎ)」と呼ばれることになる別の平衡条件(1978年にレオニダス・ギバスとロバート・セジウィックがこの呼び名を定着させたとされる)を考案し、こちらも広く使われるようになった。どちらの方式も、挿入順序がどれほど偏っていても、木の高さがO(log n)の範囲に収まることを保証する点で共通している。今日広く使われている多くのプログラミング言語の標準ライブラリで、順序付きの集合や辞書を実装する内部構造として赤黒木の系統が採用されていることが多いのも、この「崩れない」という保証が実務上どれほど重宝されているかを示している。
### ハッシュテーブルの発明 — 比較すらしない探索
木構造とは別の方向から探索を速くする発想もある。1953年、IBMの技術者ハンス・ピーター・ルーンが社内資料の中で提案したとされる**ハッシュテーブル(水準八: キーを一定の計算式〈ハッシュ関数〉で番地に変換し、その番地へ直接データを格納・取り出しする構造)**は、大小比較を一切せず、キーそのものから格納場所を計算してしまう。
### 検算6 — ハッシュの衝突を実際に確かめる
表の大きさを7、ハッシュ関数を「伝票番号を7で割った余り」とする小さな例で確かめる。
```
15 ÷ 7 = 2 あまり 1 → 番地1
22 ÷ 7 = 3 あまり 1 → 番地1
29 ÷ 7 = 4 あまり 1 → 番地1
```
3件とも同じ番地1に集中してしまった。これを**衝突(しょうとつ、水準八: 異なるキーが同じ番地に計算されてしまう現象)**と呼び、実務では番地ごとに小さな連結リストをぶら下げて衝突分を鎖でつなぐ(連結リストが、ここでもう一度部品として使われている)。表の大きさを素数の11に変え、同じ3件を計算し直すと、
```
15 ÷ 11 = 1 あまり 4 → 番地4
22 ÷ 11 = 2 あまり 0 → 番地0
29 ÷ 11 = 2 あまり 7 → 番地7
```
今度は3件とも別々の番地に収まり、衝突なしでそれぞれO(1)で取り出せる。表の大きさの選び方(特に素数を選ぶこと)や、キーの分布の偏りが、ハッシュテーブルの実際の速さを大きく左右することが、この2つの検算の比較から読み取れる。表の大きさに対して格納する件数の割合(**充填率〈じゅうてんりつ〉**)を低く保つことも、衝突を減らすもう一つの手段である。荷物1,024件を表の大きさ4,096(1,024の4倍)に格納すると、
```
充填率 = 1,024 ÷ 4,096 = 0.25
```
平均すれば1つの番地あたり0.25件、つまり衝突はまれで、平均するとO(1)(データ件数によらずほぼ一定の手間)で探索できる。ただし整列された順序は失われるため、「1番から順に全件を並べて見る」といった作業には向かない。
---
> **定着量の目安(第四章)**: 偏った木がO(n)に転落する理由の説明、AVL木・赤黒木が保証する性質の要点、ハッシュテーブルの衝突と充填率の計算を身につけるには、この3つの現象を自分の言葉で説明する練習を各5回、割り算による衝突判定ドリルを15問程度こなすと、水準七〜八の内容がほぼ定着すると見込まれる。
---
## 第五章: 木を超えるネットワーク、グラフの誕生(水準九〜十)
### グラフの必要性 — 親子関係だけでは表せないもの
木構造は「1つの根から枝分かれする、親子関係のネットワーク」を表すのに向いている。しかし配送センターの各拠点(ハブ)は、必ずしも1つの本社を頂点にした階層構造でつながっているわけではない。ハブAとハブBの間に直接の道があり、ハブBとハブCの間にも道があり、しかもハブAとハブCが別の道で直接つながっている――というような、複数の行き来が入り組んだ関係を木構造で表すことはできない。
こうした「点(ノード)と点を結ぶ線(エッジ)」の関係全般を表す構造が**グラフ(水準九: ノード〈頂点〉とエッジ〈辺、ノード同士のつながり〉の集まりで、任意の関係性を表現できるデータ構造)**である。グラフという考え方の起源は、木構造やハッシュテーブルよりもはるかに古く、1736年、数学者レオンハルト・オイラーが「ケーニヒスベルクの橋渡り問題(4つの陸地を7本の橋で結んだ町を、同じ橋を二度渡らずに一筆書きで巡れるか、という問題)」を論文で扱ったことが、グラフ理論の起点として広く紹介されている。エッジに向きがある場合を**有向グラフ**、向きがない場合を**無向グラフ**、エッジに距離や時間などの重みが付く場合を**重み付きグラフ**と呼び、配送センターの拠点間の道のりは、まさに重み付きグラフで表すのにふさわしい題材である。
### グラフの探索 — 幅優先と深さ優先
グラフの中を巡る基本的な方法として、**幅優先探索(BFS、水準十: 出発点に近いノードから順に、同じ距離のノードをすべて確認してから次の距離へ進む探索方法)**と**深さ優先探索(DFS、水準十: 1本の道を行き止まりまで進み、行き止まったら1歩戻ってまだ通っていない道を探す探索方法)**の2つがある。BFSの考え方は1959年にエドワード・F・ムーアが迷路の最短経路を求める手法として整理したとされ、DFSの考え方自体は19世紀の迷路解法(エドゥアール・リュカが1882年に紹介したことで知られる、いわゆる「壁伝い法」に近い)にまでさかのぼるとされるが、これをアルゴリズムとして体系的に分析したのは1972年のロバート・タージャンの論文が代表的とされる。
### 検算8 — BFSとDFSでは巡る順序が変わることを確かめる
5つの拠点A・B・C・D・Eが、次のように道でつながっているとする(向きも重みもない、単純なつながりだけの図)。
```
A-B、A-C、B-D、C-D、D-E
```
Aを出発点として、まずBFS(近い順)でたどると、
```
0ホップ目: A
1ホップ目: AとつながるB・C
2ホップ目: BとCの両方につながるD
3ホップ目: DにつながるE
訪問順: A → B → C → D → E(Eに到達するまで最短3ホップ)
```
一方、Aを出発点として、番号の小さい枝を優先して行き止まりまで進むDFSでたどると、
```
Aを訪問→隣接するBへ進む
Bを訪問→隣接する未訪問のDへ進む
Dを訪問→隣接する未訪問のCへ進む(Bはすでに訪問済み)
Cを訪問→隣接するA・Dはどちらも訪問済み、行き止まりなのでDまで1歩戻る
Dに戻り、まだ訪れていないEへ進む
訪問順: A → B → D → C → E
```
同じ地図なのに、訪問する順序がA→B→C→D→E(BFS)とA→B→D→C→E(DFS)とで異なることが確かめられる。BFSは「出発点から何ホップ〈道の本数〉で届くか」を調べるのに向き(EまでBFSは3ホップ目で到達しており、これが最短ホップ数であることが保証される)、DFSは「奥まで一気に潜ってから戻る」性質を生かして、迷路探索や依存関係の整理に向く――どちらも全てのノードとエッジを1回ずつ確認するという点では同程度の手間(O(ノード数+エッジ数))だが、たどる順序と得意な用途が異なる。
---
> **定着量の目安(第五章)**: ノード・エッジ・有向/無向/重み付きという用語、BFSとDFSの手順の違いを身につけるには、小さな地図(5〜8ノード程度)を自分で描いて両方の方法で実際にたどってみる練習を10回程度こなすと、水準九〜十の内容がほぼ定着すると見込まれる。
---
## 第六章: 最短経路とヒープ、そして適材適所の設計(水準十一〜十二)
### 検算7 — ダイクストラ法による最短経路
重み付きグラフの中で「出発点から目的地までの合計コストが最小になる道」を求める代表的な方法が**ダイクストラ法(水準十一: 出発点から各ノードまでの最短距離を、確定した中で最もコストの低いノードから順に確定させていく最短経路アルゴリズム)**である。オランダの計算機科学者エドガー・W・ダイクストラが1956年に着想し、1959年に論文として発表したとされる。
拠点A・B・C・Dの4つのハブが、次の道のりで結ばれているとする(数字は移動コスト)。
```
A-B: 2 A-C: 5 B-C: 1 B-D: 7 C-D: 3
```
AからDまでのすべての単純な経路(同じ拠点を二度通らない経路)を、まず力ずくで数え上げて検算の基準を作る。
```
A→B→D: 2 + 7 = 9
A→C→D: 5 + 3 = 8
A→B→C→D: 2 + 1 + 3 = 6
A→C→B→D: 5 + 1 + 7 = 13
最小値 = 6(経路 A→B→C→D)
```
次に、ダイクストラ法の手順どおりに解く。出発点Aの距離を0、他をすべて「未確定・無限大」として始める。
```
Aを確定(距離0)→隣接するBを2、Cを5に更新
未確定の中で最小のBを確定(距離2)→Cは 2+1=3 のほうが5より小さいので3に更新、Dは 2+7=9 に更新
未確定の中で最小のCを確定(距離3)→Dは 3+3=6 のほうが9より小さいので6に更新
未確定の中で最小のDを確定(距離6)→全ノード確定
```
ダイクストラ法で求めた最短距離は6となり、力ずくで数え上げた最小値6とぴったり一致する。この一致が、アルゴリズムが正しく最短経路を求められていることの検算になる。
### ヒープと優先度付きキュー — 「次の1件」を素早く取り出す
ダイクストラ法を大きなグラフで効率よく実行するには、「未確定のノードの中から距離が最小のものを毎回選ぶ」という操作を素早く行う必要がある。この操作に向いた構造が**ヒープ(水準十一: 親の値が常に子の値以下〈または以上〉になるよう並べられた木構造で、最小値〈または最大値〉を常に根に置くことで高速に取り出せる構造)**であり、1964年にJ・W・J・ウィリアムズが発表した整列手法(ヒープソート)の中で使われた構造として知られている。ヒープを使った**優先度付きキュー(水準十一: 値の大小〈優先度〉に応じて、常に最も優先度の高い要素から取り出せるキュー)**を使うと、荷物1,024件の中から「次に発送すべき最優先の1件」を取り出す操作が、未整列の配列を毎回端から探す場合のO(n)(最悪1,023回の比較)に対し、ヒープではO(log n)(木を約10段たどるだけ)で済む。
### 水準十二 — 適材適所の設計判断
ここまで見てきた構造を、目的別に並べて比較する。
| 構造 | 探索 | 挿入 | 削除 | 順序保持 | 向いている場面 |
|---|---|---|---|---|---|
| 配列(未整列) | O(n) | O(1)末尾のみ | O(n) | しない | とにかく記録を蓄積するだけの用途 |
| ソート済み配列 | O(log n) | O(n) | O(n) | する | 更新がまれで検索が主体の用途 |
| 連結リスト | O(n) | O(1)※位置既知 | O(1)※位置既知 | しない | 挿入・削除が頻繁で、範囲探索は不要な用途 |
| 平衡二分探索木 | O(log n) | O(log n) | O(log n) | する | 検索・更新の両方が頻繁で、範囲検索も必要な用途 |
| ハッシュテーブル | O(1)平均 | O(1)平均 | O(1)平均 | しない | 完全一致検索だけを高速化したい用途 |
| グラフ+ダイクストラ法 | 最短経路を算出 | ノード/エッジ追加 | ノード/エッジ除去 | 関係そのものを表現 | 拠点間の経路・つながりを扱う用途 |
| ヒープ | 最小/最大はO(1) | O(log n) | O(log n) | 優先度のみ | 「次の1件」を繰り返し取り出す用途 |
どの構造にも、必ず「得意なこと」と「その代わりに苦手になること」がある。新人整理係が最初にぶつかった「探すのを速くすると、しまうのが遅くなる」というトレードオフは、この巻を通じて姿を変えながら何度も現れてきた。情報構造の設計とは、この表を眺めて「自分の場面ではどの操作が一番頻繁に起きるか」を見極め、そこに最も強い構造を選ぶ判断そのものを指す。この「どの操作が一番頻繁に起きるかを見極める」という作業は、実は→BOOK-0345『要件定義とデザイナー思考』で扱う、曖昧な要望を検証可能な要件へ翻訳する作業と本質的に同じ形をしている。「速い検索が欲しい」という漠然とした要望を、「挿入と検索、どちらがどれだけの頻度で起きるのか」という具体的な問いに変換できて初めて、この表のどの行を選ぶべきかが決まる。
---
> **定着量の目安(第六章)**: ダイクストラ法の手順を小さなグラフ(4〜6ノード)で自分の手で解き、力ずくの数え上げと一致することを確かめる練習を5回、上の比較表を見ずに自分で再現できるようになるまでの反復を10回程度こなすと、水準十一〜十二の内容がほぼ定着すると見込まれる。
---
## コラム — なぜこの巻では「1,024件」を何度も使ったのか
第一章から第六章まで、荷物の件数としてたびたび1,024(2の10乗)という数を使ってきた。これは偶然ではなく、「二分探索なら最大10回」「完全二分木なら高さ9(最大10段)」「ヒープなら約10段」というふうに、異なる構造同士の手間をそろえて比べられるようにするための意図的な選択である。実際の配送センターが扱う荷物の数は、日によって数百件のこともあれば数万件のこともあり、きりのよい2の累乗になることはまずない。しかし件数がどのような数であっても、「件数が2倍になれば、線形探索の手間もおよそ2倍になるが、二分探索や平衡木の手間は1回しか増えない」という増え方の性質そのものは変わらない。数値検算で使った「1,024件・最大10回」という具体例は、あくまで増え方の感覚をつかむための足場であり、件数が100万件、1億件と大きくなるほど、この足場の効果はより劇的な差になって現れる。データベースの索引に、二分探索木ではなく子の数をさらに増やした**B木**が好んで使われるのも、記憶装置への読み書き回数そのものを減らしたいという、この延長線上の工夫である。
---
## 三つの実践解(§16.21) — 紙と手で確かめる情報構造3法
1. **トランプ探索実践**: トランプ1組(52枚)から数字だけを取り出し、バラバラに並べた状態と、数字順に並べた状態のそれぞれで、特定の1枚を探すのに何回めくったかを数える。バラバラな状態(線形探索)と整列済みの状態(二分探索)とで、めくる回数がどれだけ違うかを自分の手で検算する実践である。
2. **家系図・フォルダ構造の木構造実践**: 自分の家族の家系図、またはパソコンのフォルダ構造を、紙に木構造として描いてみる。どのノードが根で、どのノードが葉(子を持たない末端)かを確認し、ある人物(あるファイル)にたどり着くまで根から何段かかるかを数える練習である。
3. **最寄り施設の経路グラフ実践**: 自宅を中心に、駅・コンビニ・学校など身近な場所をノードとし、実際の道のりをエッジ(移動時間や距離を重みとして書き添える)としたグラフを手描きで作る。2地点間の最短経路を、指でたどりながら複数の経路を比較して求め、ダイクストラ法の手順(確定済みの中から最小のものを選び、隣接する距離を更新する)を自分の地図の上でなぞってみる実践である。
---
## まとめ — 一列の棚から、枝分かれする地図へ
本冊では、台帳の1,024件目の荷物を探せなかった新人整理係の物語から出発し、配列と線形探索の限界(第一章)、整列と二分探索がもたらす速さと、その代償としての挿入コスト(第二章)、連結リストが挿入を軽くする代わりに探索を重くすること、そして二分探索木がその両方を欲張って両立させようとしたこと(第三章)、均整の取れていない木が配列以下の性能に落ち込む落とし穴と、AVL木・赤黒木という保険、ハッシュテーブルという比較すらしない発想(第四章)、木構造では表せない複雑な関係を扱うためのグラフの誕生と、BFS・DFSという2つの巡り方(第五章)、そしてダイクストラ法による最短経路の計算と、ヒープによる「次の1件」の高速な取り出し、最後に構造を選ぶという判断そのもの(第六章)までをたどってきた。
配列から連結リストへ、連結リストから木構造へ、木構造からグラフへ――新しい構造が生まれるたびに、前の構造のどこかの弱点が解消され、代わりに別の何かが失われてきた。この年代的な比較史そのものが、「万能の構造は存在せず、場面に応じて選び取るしかない」という、情報構造の設計の核心を物語っている。
---
## 章末: 簡易構造図とまとめの階段図
**縦の階段(水準一〜十二を、具体的な数値とともに登る)**
```
[水準十二] 適材適所の設計判断
7種の構造を比較表で見渡し、場面に応じて選ぶ
▲
│ 「次の1件」を高速に取り出す
[水準十一] ダイクストラ法とヒープ
検算7: 4ノードの最短経路=6(力ずく数え上げと一致)
▲
│ 巡り方を2種類に分ける
[水準十] 幅優先探索(BFS)・深さ優先探索(DFS)
ノード+エッジの数だけ手間がかかる(O(V+E))
▲
│ 親子関係を超えたつながりを表す
[水準九] グラフの誕生
オイラー1736年・ケーニヒスベルクの橋渡り問題
▲
│ 崩れない木、比較しない探索
[水準七〜八] 平衡木とハッシュテーブル
検算6: 15・22・29が全て番地1に衝突(mod 7)
▲
│ 偏ると配列並みに遅くなる
[水準五〜六] 連結リストと二分探索木
検算4: 節1,023個・完全二分木の高さ=9(最大10段)
▲
│ 探すのが速くなると、しまうのが遅くなる
[水準三〜四] 整列と二分探索、挿入コスト
検算2: 1,024件→最大10回(2の10乗=1,024)
▲
│ 並べ替えを武器にする
[水準一〜二] 配列と線形探索
検算1: 1,024件→平均512.5回・最悪1,024回
通底テーマ: どの構造にも「得意」と引き換えの「苦手」がある。
```
**横の広がり(同じ水準にある姉妹概念)**
水準六(二分探索木)の姉妹に、子の数を2つに限らず複数許した**多分木**や、データベースの索引で広く使われる**B木**(子の数を大幅に増やし、木の段数そのものを減らす発想)がある。水準九(グラフ)の姉妹に、閉路〈同じノードに戻る経路〉を持たない有向グラフである**有向非巡回グラフ(DAG)**があり、タスクの依存関係の整理などに使われる。
**現在のフロンティア**
2018年、ティム・クラスカらの研究チームが「学習型索引構造(learned index structures)」という提案を発表し、機械学習モデルでB木のような索引の役割の一部を代替できないかという研究が今も続けられている。また、複数の処理が同時にアクセスしても壊れない**並行データ構造(concurrent data structures)**の設計は、マルチコア・分散システムが当たり前になった現在でも活発な研究領域であり続けている。
**次の冊子への矢印**
次巻(BOOK-0344『文章の解析と解読』): 構文解析・意味理解・機械翻訳の仕組みの入口を扱う予定 ─────▶
---
## 参照文献(定番教科書・歴史的原典)
1. 計算機科学の標準的な教科書に共通する、配列・連結リスト・木構造・グラフ・計算量(O記法)を扱う定番のデータ構造入門(大学初年次・情報系専門課程で広く使われている教科書群)。
2. レオンハルト・オイラーによるケーニヒスベルクの橋渡り問題の論文(1736年、グラフ理論の起点として広く紹介される)。
3. G. M. Adelson-Velsky and E. M. Landis, "An algorithm for the organisation of information", 1962年(AVL木の原論文とされる)。
4. Rudolf Bayer による対称二分B木の提案(1972年)、および Leonidas Guibas と Robert Sedgewick による「赤黒木」という呼称の定着(1978年)。
5. Hans Peter Luhn によるIBM社内資料でのハッシュ法(scatter storage)提案(1953年とされる)。
6. Edsger W. Dijkstra, "A note on two problems in connexion with graphs", *Numerische Mathematik*, 1959年。
7. J. W. J. Williams, "Algorithm 232: Heapsort", *Communications of the ACM*, 1964年。
8. Tim Kraska et al., "The Case for Learned Index Structures", 2018年(学習型索引構造の提案論文)。
---
（本冊子は現代学問宇宙図鑑シリーズ BOOK-0343。応用の軌道ステーション群・「作る力と生きる力シリーズ」計算機文明部の第4巻(情報構造の設計)。目録の正=gakumon/CATALOG_作る力と生きる力シリーズ.md。次巻はBOOK-0344『文章の解析と解読』の予定。GAKUMON_UNIVERSE.md 進捗台帳を参照。）
# BOOK-0343 作る力と生きる力シリーズ: 計算機文明部 第4巻 情報構造の設計 — 一列の棚から、枝分かれする地図へ