アルゴリズム・データ構造図鑑 · 入門

配列:添字で直接アクセスできる理由

連続した領域の位置計算から、配列の高速な参照と挿入時の移動コストを理解する。

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

更新日

この記事の目次
  1. 位置を計算して取り出す
  2. 途中への挿入で何が動くか
  3. 動的配列の末尾追加
  4. 選ぶときの確認点
  5. この記事をロゲイアに質問する理解を確かめる

位置を計算して取り出す

固定長要素を連続した領域に並べる配列では、要素iの位置は「先頭アドレス+i×要素の大きさ」で求められます。0番目から数え、各要素が4バイトなら、先頭から12バイト先にあるのは3番目の要素です。この直接計算が、通常のRAMモデルで添字参照をO(1)とする理由です。要素がオブジェクトへの参照なら連続するのは参照の領域であり、オブジェクト本体まで連続するとは限りません。

途中への挿入で何が動くか

配列[10,20,30,40]の添字1へ15を挿入すると、順序を保つには20、30、40を一つずつ後ろへ移します。空き領域があっても移動は必要です。長さnの配列で先頭付近への挿入や削除を行えば、移動数はnに比例します。対して、順序を保つ必要がない削除なら、最後の要素で穴を埋める設計も考えられます。操作の目的を明確にすると、同じ配列でも必要な処理が変わります。

動的配列の末尾追加

動的配列は長さと確保済み容量を分けて持ちます。容量4に4要素が入っているとき、5要素目の追加で容量8へ増やす方式なら、既存4要素を別の領域へ移します。この1回の追加はO(n)ですが、容量を一定倍率で増やす方式では、多数の追加を合計したコストから末尾追加を償却O(1)と評価できます。毎回ちょうど1要素分だけ拡張する方式に、この評価をそのまま当てはめることはできません。

選ぶときの確認点

配列は順次走査と添字参照に向いています。ただし、未整列の配列から値を探す処理は、位置が分からないので通常O(n)です。添字参照のO(1)と値検索のO(n)を混同しないようにします。実際の速度はキャッシュ、要素サイズ、再確保、言語の境界検査にも影響されます。頻繁な中間挿入があるなら、連結リストや木も候補にし、探索の頻度とメモリ使用量を含めて選びます。

操作条件時間
添字参照添字が既知O(1)
値検索未整列O(n)
中間挿入順序を保つO(n)
末尾追加一定倍率の容量拡張償却O(1)

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

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

CS基礎を固める · STEP 9

学習コースから次を選ぶ