配列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

この記事では、コンピュータ・プログラムにおいて配列(はいれつ、Array)と呼ばれているデータ構造について説明する。計算科学方面ではベクトルという場合もある。また、リストも参照。一般に、添え字で個々の要素を区別する。

配列とは[編集]

複数の値を格納するのに用いられるのが配列である。

ここでは例示にC言語を使う。

例えば、6人の生徒の平均点を計算するプログラムを書くとする。あきらかにまずいやりかたは、それぞれの生徒に対応する変数を、次のように個別に用意することだろう。

int score1;
int score2;
int score3;
...

より良い解は6要素の配列を使うことである。

int score[6];

このようにすると、Cでは6要素の配列が作られる。各要素へは、変数scoreを通してscore[0]からscore[5]のようにしてアクセスする。

計算オーダー[編集]

「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、Ο(1) でアクセスできる具象あるいは実装を特に指す場合がある(その場合、次節の連想配列などは、そのような名前だが「配列」ではない、ということになる)。

要素に「隙間」が無いようにするには、線形リストと異なり、挿入・削除にO(n)時間かかる。探索は一般的には線型探索になるためΟ(n)だが、データがソート済みであれば二分探索を使うことでΟ(log n)に軽減することもできる(抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。en:Sorted array を参照)。

さまざまな配列[編集]

連想配列[編集]

添え字は一般に通例0か1始まりの(非負)整数である。一方、文字列など他のデータ型を添え字のように使用できる配列を連想配列という。

一般に次節の動的配列のように、任意に拡大されるものが多いが、固定サイズのものもありえなくはない。また、完全ハッシュ(ハッシュ関数#完全ハッシュ関数)の利用も考えられる。

動的配列[編集]

言語によっては、最初に指定されたサイズからはみ出してアクセスしても、自動的に拡大されるような配列を持っているものがあり、動的配列(dynamic array)、可変長配列(variable-length array)などという。要素の末尾追加や途中挿入がいくらでもできる。ライブラリで提供されるもの(C++のstd::vector、Javaのjava.util.ArrayList、.NETのSystem.Collections.ArrayListやSystem.Collections.Generic.List[1]など)と言語に組み込まれているもの(PerlDなど)がある。

逆に決まった要素数しか格納できない配列を、静的配列(static array)あるいは固定長配列(fixed length array)と言う。

なおC言語では(C99以降)、int foo[n];のように、要素数を変数にして静的配列を宣言でき、それを可変長配列(variable-length array)と呼んでいる。

動的配列の拡大などの場合には、最悪の場合、メモリ上の別の場所が確保されて、そこに全体をコピーする、というような時間のかかる操作が起きる可能性があるものもある(そのシステムの設計次第で、配列の内部にあるものが他からポインタで指されていて、それを更新できないなど、そういうことができない場合もある)。最悪ではなく償却計算量でNにならなければ良い、という考え方もある。

多次元配列[編集]

1次元だけではなく2次元・3次元などの多次元配列がある言語もある。

C♯FORTRANなど、一部の言語には「本物の」多次元配列があり、a[i, j] などといったような構文でアクセスする。C♯には、後述するジャグ配列となる「配列の配列」もある。

なお、C言語について「多次元配列がサポートされていると考えるべきである。」などとウィキペディアに書く者がいるが、C言語にあるのは「配列の配列」であって、「多次元配列」ではない。次のようなコードのことを考えてみればわかる。

void
f(int (*p_arr3)[3])
{
  ……
}

  (別の関数内)
  ……
  int arr5_arr3[5][3];
  f(arr5_arr3);

ここで arr5_arr3 は「「intの3要素の配列」の5要素の配列」である。そして、関数fに渡される際には、C言語の「配列は引数として渡される際は、その先頭要素を指すポインタに縮退する」というルールにより、その先頭の「intの3要素の配列」を指すポインタ、がp_arr3に渡される。

もしC言語で「多次元配列がサポートされていると考えるべきであ」ったら、それぞれ「intの5x3要素の配列」「intの5x3要素、を指すポインタ」(あるいは、単にintを指すポインタに縮退するかもしれない)などと、「考えるべきであ」ろうが、そう考えるのは難しいし、実際、そうなってはいない。

また同様に、Javaに関しても、「多次元配列がサポートされていると考えるべきである。」などとウィキペディアに書く者がいるが、Javaの「配列の配列」はC言語よりもさらに緩く、Javaの型システムにおける「配列の配列」では、外側の配列は、内側の配列のサイズを固定しない(C言語では、内側の配列のサイズは固定である)。さらに、Javaにはプリミティブ型と参照型があり、参照型は一種のポインタだが、配列は参照型であるので、Javaの「配列の配列」は後述の「ジャグ配列」になっており、どのように考えても「多次元配列がサポートされていると考えるべきで」ない。

(もちろん、1次元配列に対し多次元配列風にアクセスするようなクラスを実装することはできるだろうが、そういうものは、どう考えても「多次元配列がサポートされていると考えるべき」とは考えられないのが普通の考え方であろう)

ジャグ配列[編集]

Jagged Array Representation.png

「配列の配列」の場合、内側の配列について、要素数が揃っていることを要求しないデータ構造のことがある。ジャグ配列、不規則配列などと言う。これに対し、内側の配列の要素数が揃った配列を矩形配列などと言う。Javaにおける配列の配列はジャグ配列である。C♯には前述の通り、「本物の多次元配列」もあるが、それとは別に配列の配列もあり、そちらはJavaと同様のジャグ配列である。

  int[][] numArr = new int[3][];
  numArr[0] = new int[]{1, 2, 3};
  numArr[1] = new int[]{4, 5, 6, 7};
  numArr[2] = new int[]{8, 9};

C言語では、配列を指すポインタは、その配列のサイズを固定しなければならない。配列を指すポインタではなく、「「配列の先頭要素を指すポインタ」の配列」によって、次のようにしてジャグ配列のようなデータ構造を作ることができる。

  int *numArr[3];
  int tmp0[] = {1, 2, 3};
  int tmp1[] = {4, 5, 6, 7};
  int tmp2[] = {8, 9};
  numArr[0] = &(tmp0[0]);
  numArr[1] = &(tmp1[0]);
  numArr[2] = &(tmp2[0]);
  printf("%d\n", numArr[1][1]);  // print "5"

例示したように、「配列の配列」と同様の構文でアクセスできるが、データ構造としては異なっている。当然、(生成されるコードを読めばわかるが)意味的に違うものであって、混同してはならない。ましてや「多次元配列がサポートされていると考えるべき」などと考えるのは、混乱の元でしかない。

Iliffe vector[編集]

2D array.png

「ジャグ配列と同様な構造で実装された、多次元配列」という意味の、Iliffe vector という語がある("Iliffe" は、人名 John K. Iliffe に由来)。それに対し、連続した領域を多次元配列として扱うデータ構造を指す dope vector(en:Dope vector)という語がある。

脚注[編集]

  1. ^ リンクリストではなく、メモリ上で連続しているため、ランダムアクセスは定数時間のO(1)となる。