データ構造：不変条件と操作コストを説明する
データ構造には外から見える動作と、条件付きの効率があります。インターフェース、表現の不変条件、コストモデルを分け、動的配列で一回の高コストと系列の低い平均が両立する理由を学びます。
学習順路・例題の編集責任：University Reading List編集プロジェクト。 編集と選定の方法 · 出典確認日:
このページの目次
対象と編集責任
ループ、関数、配列、参照を学んだ後の第2科目向け。Morinは数学的解析、GoodrichはJavaのクラスとジェネリクス、Wengrowは具体的な手順の計数に向きます。以下は創作アルゴリズムの計数で、組込みリストの実測ではありません。
出発点を選ぶ
無料で厳密に学ぶ
Morin著者サイトのJavaまたは擬似コード版を使い、総和・対数・初歩の確率を復習して実装と証明を並べます。
Javaの実装課題がある
Goodrichで抽象データ型とAPIを学び、教材と課題のインターフェースを照合します。
コードは書けるがBig Oが難しい
Wengrowの図と計数から始め、償却の根拠をMorinで確認します。一例を全系列の証明にはしません。
三冊を比較する
Open Data Structures: An Introduction（オープンデータ構造入門）
Pat Morin · 2013
無料の解析主教材
- 選ぶ場面
- ループと総和を読め、表現から計算量を導きたい。
- 別の教材が適する場面
- 最初のプログラミングや添字と値の区別がまだ必要。
- 読む範囲
- 著者のJava／擬似コード版で配列リスト、連結リスト、ハッシュ表。2013年紙版では第2、3、5章。
- 限界と注意点
- 著者のオンライン本文・コードのAttribution条件と、AU Press PDFの非営利・改変禁止条件は別です。
選ぶ前に試す
n≤容量を述べ、12回の追加で移す全要素を数える。
確認すること: 添字が有効な理由と、拡張が一回の費用を増やす理由の両方を説明する。
Data Structures and Algorithms in Java（Javaによるデータ構造とアルゴリズム）
Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser · 版: 6 · 2014
Java実装主教材
- 選ぶ場面
- クラスと事前条件を設計し、抽象データ型を実装したい。
- 別の教材が適する場面
- 参照・例外・ジェネリクスを学ばず言語中立の近道だけを求める。
- 読む範囲
- 2014年第6版紙版ISBN 9781118771334。配列／リスト、スタック／キュー、解析を題名で選ぶ。
- 限界と注意点
- 学生用コードの公開は商用本文の無料公開ではありません。後の電子版は別の識別子です。
選ぶ前に試す
キューのAPIを書き、循環配列で空状態と追加・取り出しを追う。
確認すること: FIFOという動作と折返しという表現を分け、空と満杯を識別できる。
A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills（常識で分かるデータ構造とアルゴリズム）
Jay Wengrow · 版: 2 · 2020
直感的な計数の補助
- 選ぶ場面
- 基本的にコードを書け、記号の前に具体的な手順が欲しい。
- 別の教材が適する場面
- 図だけで最悪時や確率的な界を証明したい。
- 読む範囲
- 2020年第2版ISBN 9781680507225。構造の重要性、Big O、スタック／キュー、ノード構造。
- 限界と注意点
- JavaScript・Python・Rubyの例のライブラリ費用を手作りモデルと同一視しません。公開抜粋と全編は別です。
選ぶ前に試す
配列の先頭削除と、既知の連結リスト先頭参照を使う操作を比較する。
確認すること: シフトとリンク変更を分け、参照がなければノード探索も数える。
準備を確認する
不変条件とは？
例えば0≤n≤容量で、有効値が0…n−1を占め、各操作前後に成立する性質です。実行時間ではありません。
償却とは？
系列の総費用に界を与えて操作へ分担させる方法です。全操作が速い、入力がランダム、という意味ではありません。
何を数える？
新要素の書込みと旧要素の移動を各1。確保、読出し、ゼロ初期化、解放、削除スロットの消去は数えません。
六つのステップで学ぶ
完了したステップ: 0 / 6
自己記録用のチェックであり、評価ではありません。チェック情報は当サイトに送信されません。
-
動作を定める
読む範囲: 選んだリスト／キューの導入。
取り組む課題: 操作、空・満杯時、利用者が観察できる結果を書く。
確認すること: APIは配列か連結構造かを決めない。
-
表現を描く
読む範囲: Morinの配列リストまたはGoodrichの該当項目。
取り組む課題: 拡張前後のn、容量、使用スロット、挿入位置を描く。
確認すること: 旧値は順に一度ずつ現れ、新値が末尾に入る。
-
系列を数える
読む範囲: Wengrowの計数とMorinの拡張論。
取り組む課題: 12行の台帳に容量、コピー、累計書込みを記す。
確認すること: 一回の最悪費用と系列全体を分ける。
-
成長規則を変える
読む範囲: 同じ配列の議論。
取り組む課題: 倍増を容量+2へ替え、台帳を再作成。
確認すること: 等比和と等差和の違いを説明する。
-
縮小の間隔を調べる
読む範囲: 拡張・縮小の議論と変式。
取り組む課題: 正確な二つのしきい値で4組の追加／削除を追う。
確認すること: 間隔はこの振動を防ぐが、コピー自体をなくさない。
-
選択を弁護する
読む範囲: リストとキューの選読。
取り組む課題: 添字参照と先頭削除の負荷を別々に推奨する。
確認すること: 参照の有無、費用、不変条件、除外した費用を示す。
解答付きの例題
独自の追加台帳：平均が小さくても一回は高い
空の配列の初期容量は2。満杯で追加するときだけ倍増し、12要素を追加します。書込み総数と最終容量を求め、容量を2ずつ増やす案と比較してください。
前提
値は0…n−1。拡張では旧n値を全て移し、新値を一回書きます。初期確保、読出し、ゼロ化、削除消去は除外し、途中で削除しません。
- 倍増のコピーは追加3、5、9回目の2、4、8値、計14。新規12回を加えて26書込み、サイズ12・容量16です。
- 9回目だけでは8移動+1新規=9書込み。系列平均26/12=13/6は各回の上限ではありません。
- +2では2+4+6+8+10=30コピー、新規込み42書込み。最終サイズと容量は12。空きが少ない分、コピーが増えました。
- 倍増のコピーは等比和、固定増分は等差和です。このモデルでは総移動量が線形と二次に分かれますが、実測速度の順位ではありません。
解答と解釈
倍増は26書込み・容量16、+2は42書込み・容量12。倍増でも9回目は9書込み。
結果を検証する
全拡張を列挙。8→16では新旧を一時併存させるので確保スロットは24。最終の空き容量とは別です。
前提を変えて考える
しきい値を変更：縮小が拡張を取り消す
初期サイズ8・容量8とし、構築は数えません。追加一回・pop一回を4組。満杯なら倍増、pop後Hはn≤容量/2で半減、Qはn≤容量/4で半減。最小容量2。追加と移動の書込みだけ数えます。
- Hは各追加で8を移して容量16、pop後n=8ですぐ容量8へ縮小し8を移します。4組で64コピー+4追加=68。
- Qは最初の8コピーのみ。pop後n=8・容量16は四分の一の4を超え、縮小せず8+4=12。
- 最終サイズは両方8、容量はHが8、Qが16。Qは保持空間と引換えにこの往復移動を避けます。削除スロットの消去は数えません。
解答と解釈
同じ8操作でHは68、Qは12書込み。保持容量は異なります。
結果を検証する
8操作後のサイズ／容量を順に記す。除外した初期構築や消去コストを足さない。
よくある誤り
最悪時と償却の混同
一回の高費用は一回ごとの定数界を否定し、定数償却界は否定しません。
探索の省略
既知ノードのリンク更新と、そのノードの探索は別の費用です。
計数モデルのすり替え
実際の確保、キャッシュ、保持メモリーは重要ですが、この問題には実測値がありません。
次に進む前に
- 操作後に不変条件を回復できる。
- 追加台帳と二つの縮小経路を再計算できる。
- 負荷を指定して構造を選び、計数を実測時間と区別できる。
出典と版の確認
出典確認日:
- Morin: free online editions, source code and licence
無料版で実装と解析を組み合わせますが、プログラミングと数学記号の準備が必要です。
- AU Press: selected 2013 print identity and contents
2013年紙版の目次・識別子・許諾をオンライン版から区別します。
- Wiley: Java sixth edition and product formats
第6版紙版のJavaとAPIの重点が実装ルートを支えます。
- Pragmatic Bookshelf: second-edition contents and practice
第2版の図と計数を入口にします。数値台帳は本ガイド独自です。
提案する学習活動であり、公式の課題や全巻通読の主張ではありません。