配列 さまざまな配列

配列

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/13 01:36 UTC 版)

さまざまな配列

連想配列

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

動的配列

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

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

なおC言語では、下記のように、実行時に(整数定数式ではない)要素数を指定してスタック上に自動変数として確保することのできる静的配列を可変長配列 (variable-length array) と呼んでいる[1]GCCに拡張として実装されていたが、C99以降で標準化された。この可変長配列は後から要素を追加したりすることはできない。

void func(size_t n) {
  int data[n];
}

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

多次元配列

1次元だけではなく2次元・3次元などの多次元配列 (multidimensional array) を備える言語もある。 マトリックスやグリッドのような矩形構造を持ったデータ構造であることから、矩形配列 (rectangular array) と呼ばれることもある[2]

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

C#による多次元配列の例を示す。

int[,] array2d = {
  {0, 1, 2, 3},
  {4, 5, 6, 7},
  {8, 9, 10, 11},
};
System.Console.WriteLine(array2d[2, 3]);

C#には、後述するジャグ配列となる「配列の配列」もある。

C言語の場合

C言語は規格で多次元配列に関する言及があるが、実際にサポートされているのは「配列の配列」であって、真の多次元配列ではない[3]。次のようなコードのことを考えてみればわかる。

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

int main(void) {
  int arr5_arr3[5][3];
  f(arr5_arr3);
  return 0;
}

ここで 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)、不規則配列などと言う。これに対し、内側の配列の要素数が揃った配列を矩形配列 (rectangular array) などと言う。Javaにおける配列の配列はジャグ配列である。C#には前述の通り、「真の多次元配列」もあるが、それとは別に配列の配列もあり、そちらはJavaと同様のジャグ配列である。

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};
System.out.println(numArr[1][1]);

C#によるジャグ配列の例を示す。

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};
System.Console.WriteLine(numArr[1][1]);

要素のアドレスを指定するための参照の展開は、ジャグ配列では次元の数だけ必要なのに対し、矩形配列では1回で済む。また配列の領域を確保する際、ジャグ配列では次元ごとに領域確保を繰り返す必要があるのに対し、矩形配列では1回のnew演算子の使用で領域が確保できる。ただし矩形配列は全要素が収まる連続領域を確保しなければならず、疎行列などのまばらな配列には空間的オーバーヘッドが大きくなってしまうことから向いていない。また、.NET Frameworkの中間言語には1次元配列の要素アクセスに関する専用命令が存在するため、矩形配列よりもジャグ配列のほうが速度性能面で有利になるケースも存在する[4]

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

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

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

Iliffe vector

Iliffe Vectorのイメージ

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




「配列」の続きの解説一覧




固有名詞の分類


品詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

「配列」に関係したコラム

辞書ショートカット

すべての辞書の索引

「配列」の関連用語

配列のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



配列のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの配列 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2022 GRAS Group, Inc.RSS