配列
配列の100万番目の値を読むのは1ステップですが、同じ配列の先頭に新しい値を入れると100万個の値が動きます。
データ構造とは何か
名前のリスト、印刷待ちの行列、値段の表を持つプログラムは、そのデータをどこかに保存し、それについての問いに答えなければなりません。3番目の項目は何か、この名前はリストにあるか、次の仕事はどれか、といった問いです。データ構造とは、データの保存のしかたと、そうした問いに答える方法を組にしたものです。MITの6.006の講義では、ここで2つの考えを分けています。インターフェースは、「位置iの項目を取り出す」や「末尾に項目を加える」のように、どんな操作を頼めるかを決めます。データ構造は、それらの操作を実際にメモリ上でどう行うかです。1つのインターフェースの裏にいくつものデータ構造がありえて、その速さは大きく違うことがあります。
このコースでは、アルゴリズムのコースと同じようにステップを数えます。そうすれば、ストップウォッチなしで2つの構造を比べられます。このユニットでは、メモリのマス1つを読むか書くことを1ステップとします。下のラボが数えてくれます。
並んだマスのひとかたまり
配列は、値を切れ目のない1つのメモリのかたまりに保存します。値はそれぞれ同じ大きさのマスに入り、マスには0から番号がついています。この並べ方のおかげで、配列は読むのが速いのです。かたまりがアドレスsから始まり、マス1つがcバイトなら、a[i] はアドレス s + i × c にあります。コンピューターはかけ算1回と足し算1回でそれを求め、iが3でも3,000,000でもまっすぐそこへ飛びます。MITの講義ノートでは、配列の「get at(i)」と「set at(i, x)」を Θ(1) としています。費用が長さによって増えないという意味です。
同じ並べ方のせいで、途中の変更は遅くなります。配列に7、3、9、4、6が入っていて、先頭に1を入れたいとしましょう。7の前にすき間はないので、まずすべての値を1マスずつ右へ動かさなければなりません。何も上書きしないように、最後の値から動かします。移動5回と書きこみ1回で、6ステップです。先頭の値を取り除くのはその逆で、値を読んでから、ほかの4つの値を1マスずつ左へ動かします。n個の値の配列で位置iに挿入すると、移動 n − i 回と書きこみ1回がかかるので、先頭がいちばん悪く、末尾がいちばんよい場所です。
ドラッグで回転、スクロールまたはピンチで拡大・縮小。
かたまりがいっぱいになったら
メモリのかたまりの大きさは決まっています。では、すべてのマスがうまっているときに値を加えるとどうなるでしょうか。配列は、新しい値を書く前に、もっと大きな新しいかたまりを用意してもらい、すべての値をそこへ写さなければなりません。ラボでは、5マスのいっぱいのかたまりにプッシュすると、写し5回と書きこみ1回がかかります。毎回1マスずつしか大きくしなければ、プッシュのたびにすべてを写すことになり、n回のプッシュで約 n²/2 回の写しがかかります。
MITの講義ノートにある解決法は、一度に大きく、たとえば2倍に増やすことです。容量1から始めると、写しが起きるのは配列に1、2、4、8、16個の値があるときなので、17回のプッシュで写しは合計 1 + 2 + 4 + 8 + 16 = 31 回、プッシュ1回あたり2回未満です。1回のプッシュが遅くなることはまだありますが、長く続けてプッシュすれば、1回あたりの費用は平均すると一定になります。これを償却 Θ(1) 時間と言います。JavaScriptの配列も外から見るとこのようにふるまいます。MDNは配列を大きさを変えられるものと説明していて、push と pop は安上がりな末尾で動きます。
| n個の値に対する操作 | ラボでのステップ | 増え方 |
|---|---|---|
| a[i] を読む・書く | 1 | Θ(1) |
| 先頭に挿入 | 移動n回 + 書きこみ1回 | Θ(n) |
| 先頭を削除 | 読み1回 + 移動 (n − 1) 回 | Θ(n) |
| 末尾にプッシュ（空きあり） | 1 | Θ(1) |
| 末尾にプッシュ（かたまりがいっぱい） | 写しn回 + 書きこみ1回 | 1回なら Θ(n)、償却で Θ(1) |
const a = [7, 3, 9, 4, 6];
console.log(a[3]); // 4、1ステップ
a.push(8); // 安上がり: 末尾
a.unshift(1); // すべての値が1マス右へ動く
console.log(a.join(" ")); // 1 7 3 9 4 6 8| インターフェース | get at(i) や insert last(x) のような、頼める操作の一覧。 |
| データ構造 | それらの操作をメモリ上でどう行うか。 |
| 配列 | 同じ大きさのマスが並んだ1つのかたまりに入った値。a[i] は 先頭 + i × マスの大きさ にある。 |
| 動的配列 | もっと大きな、ふつう2倍の大きさのかたまりへ写して大きくなる配列。 |
| 償却費用 | 1回ずつでは遅い操作があっても、長く続けたときの操作1回あたりの平均の費用。 |
- このユニットの数え方で、1,000,000個の値の配列から a[700000] を読むのは何ステップですか？
- 1
- 20
- 700,000
- 1,000,000
- 配列に7、3、9、4、6が入っていて、空きは十分にあります。先頭に値を挿入するのは何ステップですか（移動と書きこみ）？
- 同じ5個の値の配列で、先頭の値を削除するのは何ステップですか（読み1回と移動）？
- 空きのある5個の値（位置0〜4）の配列で、位置2に挿入するのは何ステップですか？
- 2倍に増える配列に5個の値があり、容量は5です。もう1つ値をプッシュします。このプッシュは何ステップですか？
- そのプッシュの後、容量はいくつですか？
- 容量1から始めて2倍に増やすとき、17回のプッシュで写しは合計何回ですか？
- 2倍に増える配列のプッシュが償却 Θ(1) と呼ばれるのはなぜですか？
- どのプッシュもちょうど1ステップだから
- 写しはまれなので、n回のプッシュの合計がある定数かけるn以下にとどまるから
- コンピューターが裏でただで写してくれるから
- JavaScriptは配列を決して写さないから
- MIT 6.006の言葉で、「insert last(x) と delete last()」は
- データ構造
- インターフェース
- メモリのアドレス
- ソートの方法
- 長さnで0から数える配列があります。最後の値のインデックスはいくつですか？
- n
- n − 1
- n + 1
- 1
- インターフェースは操作の一覧、データ構造はそれをどう行うか。
- 配列は値を1つのかたまりに保存するので、a[i] は1ステップ。
- 先頭近くでの挿入や削除では、約n個の値が動く。
- 2倍に増える配列ではプッシュが償却 Θ(1)。容量1から17回プッシュすると31個の値を写す。
このコースの出典 (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
確認日: 2026-10-18