この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "配列"
この記事は中立的な観点に基づく疑問が提出されているか、議論中です。そのため、中立的でない偏った観点から記事が構成されているおそれがあり、場合によっては記事の修正が必要です。議論はノートを参照してください。(2018年11月)
.mw-parser-output .hatnote{margin:0.5em 0;padding:3px 2em;background-color:transparent;border-bottom:1px solid #a2a9b1;font-size:90%}
この項目では、コンピュータ・プログラムにおける配列について説明しています。DNAの配列については「塩基配列」を、タンパク質の配列については「アミノ酸配列」を、コンピュータのキーボードにおける配列については「キー配列」をご覧ください。また「配列」は、英語では array 以外に arrangement のこともあります。
この記事では、コンピュータ・プログラムにおいて配列(はいれつ、英: array)と呼ばれているデータ構造およびデータ型について説明する。計算科学方面ではベクトルという場合もある。また、リストも参照。一般に、添え字で個々の要素を区別する。 複数の要素(値)の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造(コレクションあるいはコンテナ)には連結リストやハッシュテーブルなどがあるが、通常はメモリアドレス上での連続性の違いなどから配列とは区別される。1次元の配列は特に線形配列 (linear array) とも呼ばれる。 例えば、6人の生徒の平均点を計算するプログラムを書くとする。配列を使わない方法では、それぞれの生徒に対応する変数を、次のように個別に用意することだろう。int score1;int score2;int score3;int score4;int score5;int score6;// 例えば標準入力経由で各生徒の得点を各変数に読み込んだとする。double mean = (double)(score1 + score2 + score3 + score4 + score5 + score6) / 6; しかし、この方法では生徒数が増減したときに、変更や拡張が大変になってしまう。より良い解は6要素の配列を使うことである。int score[6]; // 6要素の配列が作られる。// 例えば標準入力経由で各生徒の得点を配列scoreに読み込んだとする。double mean = 0;for (int i = 0; i < 6; ++i) { mean += score[i]; // 配列の各要素へは、変数scoreを通してscore[0]からscore[5]のようにしてアクセスする。}mean /= 6; 配列を用いることで、添え字演算子による統一的なアクセスおよび一括処理が可能となる。また、処理すべきデータ個数が増減したときにも対応しやすくなる。 前述の例では、プログラム中で宣言時に指定した固定のサイズ(整数定数)による配列確保(静的確保)であった。実用的には、配列の要素数が宣言時(あるいはコンパイル時)に静的に決まってしまうよりも、実行時に要素数を動的に指定して配列を確保できたほうが便利なことがある。例えば、縦横任意サイズの画像ファイルから全画素情報を読み出す場合や、コンピュータで利用可能な空きメモリ量に合わせて扱うデータ個数上限を変化させたい場合などである。 多くのプログラミング言語では、配列のサイズをプログラム実行時に指定して配列を生成する(動的に確保する)手段が用意されている。例えばC言語ではmalloc関数やcalloc関数を利用する。確保に成功するとメモリブロック(配列先頭要素)へのポインタが返却され、このポインタ経由で配列を操作する。int numStudents;// 例えば標準入力経由でnumStudentsに生徒数 (> 0) を読み込んだとする。int* score = calloc(numStudents, sizeof(int)); // 要素数がnumStudents、各要素のサイズがint型のサイズであるような配列を動的に確保し、0で初期化する。// 例えば標準入力経由で各生徒の得点を配列scoreに読み込んだとする。double mean = 0;for (int i = 0; i < numStudents; ++i) { mean += score[i]; // 動的に確保した場合でも、配列の添え字シンタックスは同じ。}mean /= numStudents;free(score); // 使い終わった配列のメモリ領域を解放する。 C++などの後発の言語では、動的メモリ確保のために通例new演算子が用意されていることが多く、配列の動的確保には型と要素数を指定するnew[]演算子を使用する。int numStudents;// 例えば標準入力経由でnumStudentsに生徒数 (> 0) を読み込んだとする。int* score = new int[numStudents](); // 要素数がnumStudentsであるようなint型の配列を動的に確保し、0で初期化する。// 例えば標準入力経由で各生徒の得点を配列scoreに読み込んだとする。double mean = 0;for (int i = 0; i < numStudents; ++i) { mean += score[i]; // 動的に確保した場合でも、配列の添え字シンタックスは同じ。}mean /= numStudents;delete[] score; // 使い終わった配列のメモリ領域を解放する。 いずれにせよ、C/C++ではmallocあるいはnewによってヒープ領域から確保したメモリは明示的に解放する必要があり、解放を忘れるとメモリリークの原因となる。プログラミングの煩雑さを解消するため、C++ではコンストラクタ・デストラクタを使ったメモリ寿命管理手法 (RAII) が使われることが多い。Javaなどの後発の言語ではガベージコレクションによる自動解放を導入していることが多く、また配列の確保に関して静的確保・動的確保といった区別をしない(配列の確保はすべて動的確保である)ことが多い。 通例、上記のようにして「動的に確保された配列」は、後述の「動的配列」とは異なり、要素の追加時に自動的にサイズを増加させるようなことはできない。 なお、C言語には後述する可変長配列も言語機能として備わっているが、メモリの生存期間などの面で違いがある。 「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、Ο(1) でアクセスできる具象あるいは実装を特に指す場合がある(その意味では、次節の連想配列などは「配列」ではない、ということになる)。 配列に要素を挿入/削除する際、要素間に「隙間」が無いようにするには、線形リストと異なり、挿入/削除位置から後ろの領域にあるすべてのデータの移動(コピー)が必要となる。そのため、挿入/削除にO(n)時間かかる。さらに配列は連続領域を必要とするため、挿入時に領域が不足した場合に拡張する際のメモリ再確保のコストが高い。 探索は一般的には線型探索になるためΟ(n)だが、データがソート済みであれば二分探索を使うことでΟ(log n)に軽減することもできる(抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。en:Sorted array 添え字は一般に通例0か1始まりの (非負) 整数である。一方、文字列など他のデータ型を添え字のように使用できる配列を連想配列という。 決まった要素数しか格納できない配列を、固定長配列 (fixed-length array, fixed-size array) あるいは静的配列 (static array) と呼ぶ。 要素数によって自動的にサイズが拡張される配列を、動的配列 (dynamic array, growable array, resizable array) と呼ぶ。メモリが許す限り、要素の末尾追加や途中挿入がいくらでもできる。標準ライブラリで提供されるもの(C++のstd::vector[1]、Javaのjava.util.ArrayList[2]、.NETのSystem.Collections.Generic.List[3][注釈 1]、Pythonのlist[4]、ECMAScriptのArray[5]など)と、言語に組み込まれているもの(PerlやDなど)がある。またPerlなど、言語によっては、最初に配列を生成する際に指定されたサイズからはみ出してアクセス(範囲外アクセス)しても、自動的に拡大されるような配列を持っているものもある。 動的配列の拡大などの場合には、最悪の場合、メモリ上の別の場所が確保されて、そこに全体をコピーする、というような時間のかかる操作が起きる可能性があるものもある(そのシステムの設計次第で、配列の内部にあるものが他からポインタで指されていて、それを更新できないなど、そういうことができない場合もある)。最悪計算量ではなく償却計算量でO(1)になれば良い、という考え方もある。 なおC言語では、下記のように、実行時に(整数定数式ではない)要素数を指定してスタック上に自動変数として確保することのできる静的配列を可変長配列 (variable-length array) と呼んでいる[6]。GCCに拡張として実装されていたが、C99以降で標準化された。
配列とは
配列の動的確保「動的メモリ確保」も参照
計算オーダー
さまざまな配列
連想配列詳細は「連想配列」を参照
固定長配列
動的配列
可変長配列詳細は「可変長配列」を参照
Size:35 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef