Loading article…
コンピュータサイエンスにおいて、配列は、プログラム実行時に計算できる 1 つ以上のインデックス (識別キー) によって選択される要素(値または変数)の集合を表すデータ型です。このような集合は通常、配列変数または配列値と呼ばれます。[ 1 ]数学の概念であるベクトルと行列になぞらえて、インデックスが 1 つと 2 つの配列型は、それぞれベクトル型と行列型と呼ばれることがよくあります。より一般的には、数学の概念であるテンソルになぞらえて、多次元配列(またはn次元配列) 型はテンソル型と呼ばれることがあります。[ 2 ]
配列型の言語サポートには、特定の組み込み配列データ型、プログラマがそのような型を定義して配列変数を宣言するために使用できる構文構造（配列型コンストラクタ） 、および配列要素のインデックス付けのための特別な表記が含まれる場合があります。 [ 1 ]例えば、Pascal プログラミング言語では、宣言 は、 と呼ばれる新しい配列データ型を定義します。宣言では、その型の変数を定義します。これは、それぞれが 2 つのインデックスで識別される整数変数である 8 つの要素の集合です。Pascal プログラムでは、これらの要素は、、、 …、と表記されます。[ 3 ]特別な配列型は、多くの場合、言語の標準ライブラリによって定義されます。typeMyTable=array[1..4,1..2]ofintegerMyTablevar A: MyTableAA[1,1]A[1,2]A[2,1]A[4,2]
動的リストは、動的配列よりも一般的で実装も容易です。配列型は、主にPascalの代入のように、実行時に要素のインデックスを計算できるという点でレコード型と区別されます。この機能により、1つの反復文で配列変数の任意の数の要素を処理できます。A[I,J] := A[N-I,2*J]
より理論的な文脈、特に型理論や抽象アルゴリズムの説明においては、「配列」および「配列型」という用語は、抽象データ型（ADT）（抽象配列とも呼ばれる）を指す場合もあれば、連想配列を指す場合もあります。連想配列とは、ほとんどの言語における典型的な配列型の基本的な操作と動作を備えた数学モデルであり、基本的には実行時に計算されるインデックスによって選択される要素の集合です。
言語によっては、配列型はリストや文字列など、値の集合を表す他のデータ型と重複したり、同一視されたりすることがあります。配列型は多くの場合、配列データ構造によって実装されますが、ハッシュテーブル、リンクリスト、検索ツリーなど、他の方法で実装される場合もあります。
ハインツ・ルティシャウザーのプログラミング言語Superplan（1949年～1951年）には多次元配列が含まれていた。しかし、ルティシャウザーは自身の言語のコンパイラの構築方法を説明したものの、実際にコンパイラを実装することはなかった。
アセンブリ言語やBCPL [ 4 ]のような低レベル言語は、一般的に配列の構文サポートを持っていません。
効率的な計算において配列構造が重要であるため、 FORTRAN（1957年）、COBOL（1960年）、Algol 60 （1960年）などの初期の高級プログラミング言語は、多次元配列をサポートしていた。
配列データ構造は、 2つの操作を持つ抽象データ構造（抽象配列）として数学的にモデル化できます。
操作が定義されている任意の配列状態A、任意の値V、および任意のタプルI、Jに対して。
第一の公理は、各要素が変数のように振る舞うことを意味します。第二の公理は、異なるインデックスを持つ要素は互いに素な変数のように振る舞い、ある要素に値を格納しても他の要素の値には影響しないことを意味します。
これらの公理は有効なインデックスタプルの集合Iに制約を課さないため、この抽象モデルは三角行列やその他の奇妙な形状の配列にも使用できます。
配列構造（ポインタ演算によるインデックス付け）などの型の変数を効果的に実装するために、多くの言語ではインデックスを整数データ型[ 6 ] [ 7 ] （またはバイトや列挙型など、整数として解釈できる他の型）に制限し、すべての要素が同じデータ型と記憶領域サイズを持つことを要求します。また、これらの言語のほとんどは、各インデックスを有限の整数区間に制限し、その区間は配列変数の存続期間中固定されます。実際、一部のコンパイル言語では、インデックス範囲をコンパイル時に知っておく必要がある場合があります。
一方、一部のプログラミング言語では、浮動小数点数、文字列、オブジェクト、参照など、任意の値によるインデックス付けを可能にする、より自由な配列型が提供されています。このようなインデックス値は、区間、ましてや固定区間に制限することはできません。そのため、これらの言語では通常、任意の新しい要素をいつでも作成できます。この選択により、配列型を配列データ構造として実装することは不可能になります。つまり、これらの言語は配列のような構文を使用して、より一般的な連想配列のセマンティクスを実装するため、ハッシュテーブルまたはその他の検索データ構造によって実装する必要があります。
言語によって配列型の定義方法は異なります。たとえば、C言語では、配列は実際には連続したメモリのブロックであり、本質的にはポインタとして扱われます。[ 8 ]このような場合、配列宣言はポインタに変換されることがあります。
int a [ 10 ]; // 10 個の整数からなる配列 'a' int * p = a ; // 'p' は 'a' の最初の要素を指すvoid foo ( int arr []) { // パラメータ 'arr' は int[] です// 'arr' は最初の要素へのポインタに変換されます}しかし、 Javaなどの他の言語では、配列は実際の型です。任意の型にはT、対応する配列型がありT[]、これはフィールドを持つオブジェクトlengthです。[ 9 ]
int [] a = new int [ 5 ] ; // 5 つの整数からなる配列 'a' を宣言します
要素を指定するために必要なインデックスの数を、配列型の次元、次元数、またはランクと呼びます。 [ a ]
多次元配列をサポートするには、一般的に2つの方法があります。
多くの言語は一次元配列のみをサポートしています。そのような言語では、多次元配列は通常、イリフベクトル、つまり次元が1つ少ない配列への参照の1次元配列で表現されます。特に2次元配列は、その行へのポインタのベクトルとして実装されます。[ 10 ]したがって、配列Aのi行j列の要素は、二重インデックス（一般的な表記では）でアクセスされます。この多次元配列のエミュレーション方法により、各行のサイズが異なる、または一般的には、各インデックスの有効範囲が先行するすべてのインデックスの値に依存するジャグ配列を作成できます。A[i][j]
多次元配列のこの表現は、C および C++ ソフトウェアでは非常に一般的です。ただし、C および C++ では、コンパイル時に定数サイズで宣言された多次元配列（たとえば、または）に対して、従来の の代わりに線形インデックス式を使用します。[ 11 ]inta[10][20]inta[m][n]int**a
C99 規格では、実行時に次元が計算される配列型を定義できる可変長配列型が導入されました。動的な 4D 配列は、4D 配列へのポインタを使用して構築できます。例: 。個々の要素には、まず配列ポインタを逆参照してからインデックスを使用することでアクセスできます。例: 。あるいは、nd 配列は、(n-1) 次元配列である最初の要素へのポインタとして宣言でき、より慣用的な構文を使用してアクセスできます。例: 。int(*arr)[t][u][v][w]=malloc(sizeof*arr);(*arr)[i][j][k][l]int(*arr)[u][v][w]=malloc(t*sizeof*arr);arr[i][j][k][l]
一部の言語では、要素の位置を直接計算できます。要素の位置を直接計算できる言語では、通常、添え字リストを単一の区切り文字のペアで囲みます(foo,bar,baz)（例： FORTRAN、PL/I、ALGOL 60、Pascal）。各添え字を区切り文字のペアで囲むことはありません（例：）。配列要素の格納順序は言語によって異なり、たとえば、FORTRANは行優先配列ですが、PL/Iは列優先配列です。[foo,bar,baz][foo][bar][baz]
配列をサポートするほとんどのプログラミング言語は、ストア操作と選択操作をサポートしており、インデックス付けのための特別な構文を備えています。初期の言語では、FORTRAN のように括弧を使用していましたがA(i,j)、Algol 60 や Pascal のように角括弧を使用する言語もありました(関数呼び出しで括弧を使用する場合と区別するため)。A[i,j]A[i][j]
配列データ型は、多くの場合、配列構造として実装されます。インデックスは整数値（または全順序）に制限され、インデックス範囲は配列作成時に固定され、要素は多線形式でアドレス指定されます。これは、ほとんどの「第3世代」言語で採用されていた方式であり、Ada、C、C++などのほとんどのシステムプログラミング言語でも依然として採用されています。しかし、一部の言語では、配列データ型は連想配列のセマンティクスを持ち、インデックスは任意の型で、要素は動的に作成されます。これは、 AwkやLuaなどの一部のスクリプト言語や、標準C++ライブラリが提供する一部の配列型に当てはまります。
PascalやModulaなどの一部の言語は、アクセスするたびに境界チェックを実行し、インデックスが有効範囲外にある場合は例外を発生させるか、プログラムを中止します。コンパイラによっては、安全性を犠牲にして速度を向上させるために、これらのチェックを無効にできる場合があります。FORTRANやCなどの他の言語は、プログラマを信頼し、チェックを一切実行しません。優れたコンパイラは、プログラムを解析してインデックスが取り得る値の範囲を判断することもあり、この解析によって境界チェックを省略できる場合があります。
C などの一部の言語では、0 ベースの配列型のみが提供され、任意のインデックスの最小有効値は 0 です。[ 12 ]この選択は、配列の実装とアドレス計算に便利です。C などの言語では、負のインデックスを収容する擬似配列としてシンボル的に機能する、任意の配列の内部へのポインタを定義できます。これは、C が使用時にインデックスを境界と比較しない場合にのみ機能します。
他の言語では、各インデックスが 1 から始まる1 ベースの配列型のみが提供されています。これは、行列や数列に関する数学の伝統的な慣習です。Pascal や Lua などの一部の言語では、プログラマが最小有効インデックスを選択するn ベースの配列型がサポートされています。それぞれの選択肢の相対的な利点については、激しい議論が交わされてきました。ゼロベースのインデックス付けは、オフバイワンエラーやフェンスポストエラーを回避できます。[ 13 ]
配列宣言に現れる数値と、その配列の最後の要素のインデックスとの関係は、言語によって異なります。多くの言語（Cなど）では、配列に含まれる要素の数を指定する必要がありますが、他の言語（PascalやVisual Basic .NETなど）では、最後の要素のインデックスの数値を指定する必要があります。インデックスが1から始まるLuaなどの言語では、このような区別はありません。
一部のプログラミング言語は配列プログラミングをサポートしており、特定のデータ型に対して定義された演算や関数が、それらの型の要素からなる配列にも暗黙的に拡張されます。したがって、A + Bと記述することで、2つの配列AとBの対応する要素を加算できます。通常、これらの言語は要素ごとの乗算と線形代数の標準的な行列積の両方を提供しており、 *演算子でどちらを表すかは言語によって異なります。
APLのこの分野における革新以来、配列プログラミング機能を提供する言語が数多く登場しました。これらは、GAUSS、IDL、Matlab、Mathematicaといった ドメイン固有言語の中核機能です。また、 JuliaやFortranの最新バージョンといった新しい言語の中核機能でもあります。さらに、これらの機能は、他の汎用プログラミング言語（例えば、広く使われているPythonのNumPyライブラリなど）向けの標準拡張ライブラリを通じても提供されています。
多くの言語では、文字列データ型が組み込まれており、その型の値を構築するための特殊な表記法（「文字列リテラル」）が用意されています。一部の言語（Cなど）では、文字列は単なる文字の配列であるか、ほぼ同じように扱われます。[ 14 ] Pascalなどの他の言語では、文字列と配列に対して大きく異なる操作が提供される場合があります。
一部のプログラミング言語では、ベクトルのサイズ（要素数）を返す操作、あるいはより一般的には配列の各インデックスの範囲を返す操作が提供されています。C言語とC++では、配列はそのような関数をサポートしていないsize()ため、プログラマはサイズを保持するための別の変数を宣言し、それを別のパラメータとしてプロシージャに渡す必要がある場合がよくあります。
新しく作成された配列の要素は、未定義の値を持つ場合（C言語の場合）もあれば、0やヌルポインタなどの特定の「デフォルト値」を持つように定義される場合（Javaの場合）もある。
C++では、オブジェクトは、上記で説明したパフォーマンス特性を備えたstore、select、appendstd::vector操作をサポートします。 [ 15 ]ベクトルは、そのサイズを照会したり、サイズ変更したりできます。要素を中央に挿入するなどの遅い操作もサポートされています。
配列スライス操作は、配列型のエンティティ（値または変数）の要素のサブセットを取得し、それを別の配列型のエンティティとして組み立てます。この際、インデックスを変更する場合があります。配列型が配列構造として実装されている場合、構造体のドープベクトルを操作することで、多くの便利なスライス操作（サブ配列の選択、インデックスの交換、インデックスの方向の反転など）を非常に効率的に実行できます。可能なスライスは実装の詳細によって異なります。たとえば、Fortranでは行列変数の1列をスライスすることはできますが、行をスライスすることはできず、それをベクトルとして扱います。
一方、配列型が別の方法で実装されている場合は、他のスライス操作も可能です。
一部のプログラミング言語では、動的配列（リサイズ可能、拡張可能、またはエクステンシブルとも呼ばれる）が使用できます。これは、配列変数のインデックス範囲を、作成後いつでも拡張でき、現在の要素の値を変更する必要がないというものです。
1 次元配列の場合、この機能は、配列Aのサイズを1 増やし、最後の要素の値をxに設定する操作として提供される場合があります。他の配列タイプ (Pascal 文字列など) では、連結演算子が提供されており、スライスと組み合わせて使用することで、その効果などを実現できます。一部の言語では、配列の要素に値を割り当てると、必要に応じて配列が自動的に拡張され、その要素が含まれるようになります。他の配列タイプでは、スライスを異なるサイズの配列に置き換えることができ、後続の要素はそれに応じて番号が振り直されます。たとえば、Python のリスト代入では、要素 " A [5]の前に 3 つの新しい要素 (10、20、30) が挿入されます。サイズ変更可能な配列は概念的にはリストに似ており、一部の言語では 2 つの概念は同義です。append(A,x) A[5:5] = [10,20,30]
拡張可能な配列は、実際に使用されている要素数を記録するカウンタを備えた固定サイズの配列として実装できます。操作はappend単にカウンタをインクリメントするだけで、配列全体が使用されるまで続きます。配列全体が使用されると、操作は失敗するように定義できます。これは、Pascal の型のように、固定容量の動的配列appendの実装です。あるいは、操作によって基となる配列をより大きなサイズに再割り当てし、古い要素を新しい領域にコピーすることもできます。stringappend