配列

定義

同じ型の要素を連続したメモリ領域に格納するデータ構造。インデックスでO(1)アクセス。

詳細解説

要素アドレスを「先頭+インデックス×要素サイズ」で計算でき、ランダムアクセスがO(1)で高速。一方、要素の挿入・削除は配列の末尾以外ではO(n)を要する。サイズが固定の静的配列と、容量を超えると再確保する動的配列（ArrayList、Vector）がある。多次元配列は行優先（C, Python）か列優先（Fortran, MATLAB）で格納順が異なる。連結リストと対比される基本データ構造で、キャッシュ局所性に優れる。

「配列」が出る問題

• キャッシュメモリのライトスルー方式の説明として、正しいものはどれか。

• キャッシュメモリのヒット率が0.9、キャッシュアクセス時間が10ns、主記憶アクセス時間が100nsのとき、実効アクセス時間は何nsか。

• マルチプロセッサ構成で、共有メモリを介して通信する方式を何というか。

関連用語

よくある質問