動的配列（Dynamic Array）完全ガイド：仕組み・リサイズ戦略・言語別実装と性能最適化
エバープレイ編集部動的配列とは — 概要と定義
動的配列（dynamic array）は、要素を連続したメモリ領域に格納しつつ、必要に応じて領域を拡張・縮小できるデータ構造です。静的配列（固定長配列）と異なり、実行時にサイズが変化するため、要素の追加・削除に柔軟に対応できます。配列の利点であるランダムアクセスの高速性（インデックスによる O(1) アクセス）を保ちながら、必要に応じてメモリを確保し直すことで可変長を実現する点が特徴です。
基本操作と計算量
アクセス（a[i]）: 連続したメモリにオフセットで到達するため O(1)。
末尾への追加（append / push_back）: 通常は O(1)、ただし容量不足時の再確保（リサイズ）では O(n) のコピーコストが発生する。なお、増加戦略によっては「償却」して平均 O(1)（amortized O(1)）になる。
末尾からの削除（pop）: O(1)。単にサイズを減らすだけで済む。縮小ポリシーによりリサイズが起きれば追加コストあり。
任意位置への挿入/削除: 挿入・削除に伴う要素のシフトが必要なため O(n)。
メモリ使用量: 実際の要素数 size と割り当てられた容量 capacity があり、capacity >= size。未使用の余剰容量が存在する。
リサイズ戦略（成長ポリシー）
動的配列が満杯になった際、新しいメモリ領域を確保して既存要素をコピーする必要があります。重要なのは「どれだけ増やすか（増分）」の戦略で、代表的なものは次の通りです。
倍増（倍々戦略、例: ×2）: 最も一般的で、容量を常に 2 倍にする方法。償却コストが低く、追加操作は平均 O(1) になる。
幾何増加（例: ×1.5）: Java の ArrayList は歴史的に約 1.5 倍（old + old/2）で増やす。メモリの利用効率とコピー頻度のトレードオフを調整するために用いられる。
定数増加（例: +k）: 毎回一定分だけ増やす方法。n 回の追加で総コピーコストが O(n^2) になり、償却コストが O(n) となるため大規模用途には不向き。
償却解析（なぜ push が平均 O(1) になるか）
倍増戦略（容量を 1 → 2 → 4 → 8 ... のように増やす）を例に、n 回の append の総コストを考えます。再確保とコピーが起きるのは容量が一杯になったときだけで、容量 2^k に到達する際に直前の 2^{k-1} 要素をコピーします。したがって総コピー回数は
1 + 2 + 4 + ... + 2^{m-1} < 2^m ≦ n
となり、コピーの合計は O(n) です。各追加操作の通常コスト（要素を配置する単純な操作）と合わせても、n 回で O(n) の総コストとなるため、1 回あたりの平均コストは O(1) になります。別の会計的証明（銀行員法）では、各追加操作に定額の余剰コストを割り当て、将来のコピーに備えることで一定の定数を積み立てられることを示します。
言語別・ライブラリ別の実装例と挙動
C++（std::vector）: C++ 標準は具体的な増加率を規定していませんが、多くの実装は幾何的増加（多くは 2 倍）を採用します。push_back は償却 O(1)。realloc により既存領域が拡張できればコピーは不要ですが、多くの場合新領域へコピーされます。reallocation はイテレータやポインタを無効にします。reserve() により事前に容量確保が可能で、shrink_to_fit() は縮小を要求するが必ずしも実行されるとは限らない（非強制）。
Java（ArrayList）: OpenJDK の実装では成長は old + (old >> 1)（約 1.5 倍）。ensureCapacity や trimToSize（古いメソッド）で制御できます。ArrayList はスレッド非安全（スレッドセーフでない）。
Python（list、CPython 実装）: CPython は単純な倍増とは異なるオーバーアロケーションポリシーを採用しています。一般には new_alloc = (newsize >> 3) + newsize + 6 のような式（小さな配列のための余分なオフセットを含む）で成長します。これにより小規模での追加性能とメモリ効率を両立しています。Python の list は連続メモリであり、インデックスアクセスは O(1) です。
JavaScript（配列）: JavaScript の配列は語義上は可変長リストですが、実行エンジン（例: V8）では内部的に「密配列」や「ハッシュ風の辞書表現」など複数表現を持ち、一定条件下で効率的に動作するように最適化されています。つまり、常に単純な動的配列の実装でない点に注意が必要です。
メモリと性能の観点
連続メモリの利点: CPU キャッシュに親和性が高く、隣接要素へのアクセスが速い。ランダムアクセスも O(1) で高速。
オーバーヘッド: 余剰容量分の未使用メモリが発生するため、メモリ利用効率は 100% ではない。増加率が大きいとより多くの未使用領域が残る。
再確保のコスト: リサイズ時には全要素を新領域へコピーする必要があり、特に要素が大きい（コピーコストが高い）場合に高コストとなる。ムーブ操作（C++11 のムーブコンストラクタなど）でコスト低減が可能な場合もある。
断片化とアロケータの挙動: 大きな連続領域を確保する必要があるため、ヒープの断片化やアロケータの制約により失敗することがある。realloc が in-place で拡張できる場合はコピーを回避できるが、常に成功するとは限らない。
動的配列と連結リストの比較
ランダムアクセス: 動的配列は O(1)、連結リストは O(n)。
挿入/削除（任意位置）: 連結リストはノード操作が中心で O(1)（位置が分かっている場合）、動的配列は要素のシフトが必要で O(n)。
キャッシュ効率: 動的配列が圧倒的に有利。連結リストはメモリアロケーションが分散しやすくキャッシュミスが多い。
メモリオーバーヘッド: 連結リストは各ノードにポインタ分のオーバーヘッドがあり、小さな要素を大量に扱う場合に不利。
実運用での注意点とベストプラクティス
事前にサイズが分かるなら reserve を使う: 追加回数が多い場合は事前に容量を確保することで再確保を防ぎ、パフォーマンスを安定させられる。
頻繁な shrink と growth を繰り返さない: 要素数の増減を頻繁に行い、毎回縮小・拡張を行うと再確保コストで性能が低下する。閾値を設けて縮小は控えめにすること。
要素が大きい場合は参照を格納することを検討: 要素自身を配列に置くとコピーコストが高い場合がある。ポインタや参照（あるいはインデックス）を格納して間接参照することで再配置コストを軽減できる。
スレッド安全性: 多くの言語実装の配列はスレッド安全ではない。並列・並行で操作する場合はロックやスレッドセーフなデータ構造を利用する。
例外安全性: 言語によっては要素のコピーやムーブで例外が発生する可能性がある。再確保処理が例外安全（状態を壊さない）であることを確認する必要がある。
高度な話題（オプション）
ロックフリー/並行動的配列: 並列処理向けに設計された動的配列は実装が複雑で、通常の倍増ポリシーに加え、アトミック操作やコピー時の協調が必要。実務では並行キューや専用ライブラリの利用が一般的です。
カスタムアロケータの活用: メモリ割当を制御したい場合はカスタムアロケータ（C++ の allocator など）を用いることで断片化対策や高速化が可能。
外部ストレージとの折衷: 極端に大きなデータ集合を扱う場合は、スワッピングやメモリマップ（mmap）を使う、あるいはチャンク単位で保持する戦略が採られることがある。
いつ動的配列を選ぶべきか
動的配列は次のような場合に適しています。
頻繁にランダムアクセスを行う（インデックスアクセス中心）
末尾への追加・末尾からの削除が主要な操作である
アクセス局所性（キャッシュ効率）が重要な場合
一方、任意位置への頻繁な挿入/削除や、各要素が小さく大量でポインタオーバーヘッドを許容できない場合は、他のデータ構造（木、リンクリスト、ブロック連結リスト、B 木など）を検討します。
まとめ
動的配列は、連続メモリによる高速なランダムアクセスと、必要時に容量を拡張する柔軟性を兼ね備えた基本的かつ重要なデータ構造です。リサイズ戦略や言語実装による振る舞いの違い（成長率、再確保の挙動、API の用意され方）を理解し、事前確保や縮小ポリシーの工夫を行えば、ほとんどの汎用用途で高い性能を発揮します。特に大量データやリアルタイム性が求められる場面では、メモリの確保・再確保コストとキャッシュ効率を意識して実装を選ぶことが重要です。
参考文献
- Dynamic array — Wikipedia
- std::vector — cppreference.com
- Java Platform SE 8 — ArrayList (公式 Javadoc)
- CPython listobject.c — CPython ソースコード（list のオーバーアロケーション）
- V8 / JS エンジンの内部表現に関する資料（例: V8 のドキュメントやブログ）
- Open Data Structures — Array-based collections（償却解析など）
投稿者プロフィール
