配列（データ構造）

コンピュータサイエンスでは、配列は、同じメモリサイズの要素（値または変数）の集合からなるデータ構造であり、各要素は少なくとも 1 つの配列インデックスまたはキーによって識別され、その集合はインデックス タプルと呼ばれるタプルである場合があります。一般に、配列は同じデータ型の要素の可変かつ線形な集合です。配列は、各要素の位置（メモリ アドレス）が、そのインデックス タプルから数式によって計算できるように格納されます。^{[ 1 ] [ 2 ] [ 3 ]}最も単純なタイプのデータ構造は、線形配列、または一次元配列です。

例えば、インデックスが 0 から 9 までの 10 個の32 ビット(4 バイト) 整数変数の配列は、メモリ アドレス 2000、2004、2008、...、2036 ( 16 進数: 、、、...、 ) に 10ワードとして格納され、インデックスiの要素のアドレスは 2000 + ( i × 4 ) になります。^{[ 4 ]} 配列の最初の要素のメモリ アドレスは、最初のアドレス、基礎アドレス、またはベース アドレスと呼ばれます。0x7D00x7D40x7D80x7F4

行列という数学的概念は二次元グリッドとして表現できるため、二次元配列も「行列」と呼ばれることがあります。コンピュータでは配列を指すのに「ベクトル」という用語が使われることもありますが、数学的に言えばベクトルよりもタプルの方がより正確な同義語です。テーブル、特にルックアップテーブルは配列の形で実装されることが多く、「テーブル」という言葉は配列の同義語として使われることもあります。

配列は最も古く、最も重要なデータ構造の一つであり、ほぼすべてのプログラムで使用されています。また、リストや文字列など、他の多くのデータ構造を実装するためにも使用されます。配列はコンピュータのアドレス指定ロジックを効果的に活用します。現代のほとんどのコンピュータや多くの外部記憶装置では、メモリはワードの1次元配列であり、そのインデックスがアドレスとなります。プロセッサ、特にベクトルプロセッサは、配列演算に最適化されていることがよくあります。

配列が便利なのは、主に要素のインデックスが実行時に計算できるためです。この機能により、1 つの反復ステートメントで配列の任意の数の要素を処理できます。そのため、配列データ構造の要素は同じサイズである必要があり、同じデータ表現を使用する必要があります。有効なインデックス タプルのセットと要素のアドレス (したがって要素のアドレス指定式) は、通常^{[ 3 ] [ 5 ]}ですが、常に^{[ 2 ]}固定されているわけではありません。

「配列」という用語は、配列データ型を指す場合もあります。配列データ型とは、ほとんどの高級プログラミング言語で提供されるデータ型の一種で、実行時に計算される1つ以上のインデックスによって選択できる値または変数の集合で構成されます。配列型は多くの場合、配列構造によって実装されますが、一部の言語ではハッシュテーブル、リンクリスト、検索木、またはその他のデータ構造によって実装される場合もあります。

この用語は、特にアルゴリズムの説明において、連想配列または「抽象配列」を意味する場合にも使用されます。これは、配列の本質的な特性を捉えることを目的とした、理論的なコンピュータサイエンスモデル（抽象データ型またはADT）です。

最初のデジタルコンピュータは、データテーブル、ベクトルおよび行列計算、その他多くの目的のために配列構造を設定およびアクセスするために機械語プログラミングを使用しました。ジョン・フォン・ノイマンは、最初のプログラム内蔵型コンピュータの構築中に、1945年に最初の配列ソートプログラム（マージソート）を作成しました。^{[ 6 ]}配列のインデックス付けは、当初は自己修正コードによって行われ、後にインデックスレジスタと間接アドレッシングが使用されるようになりました。1960年代に設計された一部のメインフレーム、例えばBurroughs B5000とその後継機は、メモリセグメンテーションを使用してハードウェアでインデックス境界チェックを実行しました。^{[ 7 ]}

アセンブリ言語は一般的に、マシン自体が提供するもの以外に配列に対する特別なサポートはありません。FORTRAN (1957)、Lisp (1958)、COBOL (1960)、ALGOL 60 (1960) などの初期の高級プログラミング言語は多次元配列をサポートしており、C (1972) も同様です。C ++ (1983)では、実行時に次元が固定される多次元配列^{[ 3 ] [ 5 ]と実行時に柔軟に変更できる配列[ 2 ]}の両方に対応するクラス テンプレートが存在します。

配列は、数学的なベクトルや行列、その他の種類の長方形テーブルを実装するために使用されます。大小を問わず、多くのデータベースは、要素がレコードである一次元配列で構成されているか、または一次元配列を含んでいます。

配列は、リスト、ヒープ、ハッシュテーブル、デック、キュー、スタック、文字列、VListなどの他のデータ構造を実装するために使用されます。配列ベースの他のデータ構造の実装は、多くの場合、シンプルでスペース効率が良く（暗黙的なデータ構造）、スペースのオーバーヘッドはほとんど必要ありませんが、特に変更された場合は、ツリーベースのデータ構造（ソート済み配列と検索ツリーを比較）と比較して、スペースの複雑さが劣る可能性があります。

プログラム内での動的メモリ割り当て、特にメモリプール割り当てをエミュレートするために、1つまたは複数の大きな配列が使用されることがあります。歴史的に見ると、これは「動的メモリ」を移植性の高い方法で割り当てる唯一の方法であった場合もありました。

配列は、プログラムにおける部分的または完全な制御フローを決定するために使用できます。IFこれは、（そうでなければ冗長になる）複数のステートメントに代わる簡潔な方法です。この文脈では、配列は制御テーブルと呼ばれ、配列に含まれる値に応じて制御フローが変更される専用のインタプリタと組み合わせて使用​​されます。配列には、プログラムの実行パスを指定するサブルーチンポインタ（またはSWITCHステートメントで操作可能な相対サブルーチン番号）を含めることができます。

データオブジェクトが配列に格納される場合、個々のオブジェクトは通常、非負のスカラー整数であるインデックスによって選択されます。インデックスは添え字とも呼ばれます。インデックスは、配列の値を格納されているオブジェクトにマッピングします。

配列の要素にインデックスを付ける方法は3つあります。

0（ゼロベースインデックス）

配列の最初の要素は、添え字0でインデックス付けされます。^{[ 8 ]}

1（1ベースのインデックス付け）

配列の最初の要素は、添え字1でインデックス付けされます。

n（nベースのインデックス）

配列の基底インデックスは自由に選択できます。通常、nベースのインデックス指定が可能なプログラミング言語では、負のインデックス値や、列挙型などの他のスカラーデータ型、あるいは文字を配列インデックスとして使用することもできます。

ゼロベースのインデックス付けは、 C、Java、Lispなど、多くの影響力のあるプログラミング言語で採用されている設計上の選択肢です。これにより、配列の開始位置からのオフセットを添え字で表すというシンプルな実装が可能になり、最初の要素のオフセットはゼロになります。

配列は複数の次元を持つことができるため、複数のインデックスを使用して配列にアクセスすることは珍しくありません。たとえば、A3行4列の2次元配列の場合、0ベースのインデックスシステムでは、2行目4列目の要素に次の式でアクセスできますA[1][3]。このように、2次元配列では2つのインデックス、3次元配列では3つのインデックス、n次元配列ではn個のインデックスが使用されます。

要素を指定するために必要なインデックスの数を、配列の次元、次元数、またはランクと呼びます。

標準的な配列では、各インデックスは連続する整数（または列挙型の連続する値）の特定の範囲に制限され、要素のアドレスはインデックスに対する「線形」式によって計算されます。

一次元配列

一次元配列（または単一次元配列）は、線形配列の一種です。その要素にアクセスするには、行または列のインデックスを表す単一の添え字を使用します。

例として、10 個の整数からなる 1 次元配列を宣言するC 言語の宣言を考えてみましょう。この配列には、 型の要素が 10 個格納できます。この配列のインデックスは 0 から 9 までです。例えば、 とはそれぞれ最初の要素と最後の要素です。inta[10];ainta[0]a[9]

線形アドレス指定を持つベクトルでは、インデックスiの要素はアドレスB + c · iに位置します。ここで、Bは固定ベースアドレス、c は固定定数であり、アドレス増分またはストライドと呼ばれることもあります。

有効な要素インデックスが0から始まる場合、定数Bは配列の最初の要素のアドレスになります。このため、C言語では配列インデックスは常に0から始まると規定されており、多くのプログラマーはその要素を「最初の要素」ではなく「 0番目の要素」と呼びます。

ただし、ベースアドレスBを適切に選択することで、最初の要素のインデックスを指定できます。たとえば、配列に 1 から 5 までのインデックスを持つ 5 つの要素があり、ベースアドレスBをB + 30 cに置き換えると、同じ要素のインデックスは 31 から 35 になります。番号付けが 0 から始まらない場合、定数B はどの要素のアドレスにもならない可能性があります。

多次元配列

多次元配列の場合、インデックスi、jを持つ要素のアドレスはB + c · i + d · jとなり、係数cとdはそれぞれ行と列のアドレスの増分です。

より一般的には、 k次元配列において、インデックスi ₁、i ₂、 ...、i _kを持つ要素のアドレスは次のようになります。

B + c ₁ · i ₁ + c ₂ · i ₂ + … + c _k · i _k。

例えば、int a[2][3];

これは、配列 a が 2 行 3 列で、整数型であることを意味します。ここでは 6 つの要素を格納できます。要素は線形に格納されますが、最初の行から線形に開始し、次に 2 行に続きます。上記の配列は、a ₁₁、a ₁₂、a ₁₃、a ₂₁、a ₂₂、a ₂₃として格納されます。

この式は、メモリに収まる任意の配列に対して、k回の乗算とk回の加算のみを必要とします。さらに、係数のいずれかが2の固定べき乗である場合、乗算をビットシフトに置き換えることができます。

係数c _kは、有効なインデックス タプルがすべて異なる要素のアドレスにマッピングされるように選択する必要があります。

すべてのインデックスの最小有効値が 0 の場合、B はすべてのインデックスがゼロである要素のアドレスになります。1 次元の場合と同様に、ベース アドレスBを変更することで要素のインデックスを変更できます。したがって、2 次元配列の行と列のインデックスがそれぞれ 1 ～ 10 と 1 ～ 20 の場合、B をB + c ₁ − 3 c ₂に置き換えると、それぞれ 0 ～ 9 と 4 ～ 23 に番号が振り直されます。この機能を利用して、一部の言語 (FORTRAN 77 など) では、数学の伝統に従って配列のインデックスが 1 から始まるように指定されていますが、他の言語 (Fortran 90、Pascal、Algol など) では、ユーザーが各インデックスの最小値を選択できます。

コンパクトなレイアウト

係数は、要素がメモリ上の連続した領域を占めるように選択されることが多い。しかし、それは必ずしも必要ではない。配列は常に連続した要素で作成されるとしても、配列のスライス操作によっては、そこから非連続な部分配列が作成される場合がある。

2次元配列には、2つの体系的なコンパクトレイアウトがあります。たとえば、行列を考えてみましょう。

${\displaystyle A={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}$

行優先順序レイアウト（C言語で静的に宣言された配列に採用されている）では、各行の要素は連続した位置に格納され、ある行のすべての要素のアドレスは、連続する行のどの要素のアドレスよりも小さくなります。

列優先順序（従来Fortranで使用されていた）では、各列の要素はメモリ上で連続しており、ある列のすべての要素のアドレスは、連続する列のどの要素のアドレスよりも小さくなります。

3つ以上のインデックスを持つ配列の場合、「行優先順序」は、最後のインデックスのみが1つ異なる2つの要素を連続した位置に配置します。「列優先順序」は、最初のインデックスに関して同様の動作をします。

プロセッサキャッシュや仮想メモリを使用するシステムでは、配列の要素がメモリ内の連続した位置に格納されている場合、要素がまばらに分散されている場合よりも、配列のスキャンがはるかに高速になります。これは空間的局所性として知られており、参照の局所性の一種です。多次元配列を使用する多くのアルゴリズムは、予測可能な順序で配列をスキャンします。プログラマ（または高度なコンパイラ）は、この情報を使用して、各配列のレイアウトを行優先または列優先のどちらにするかを選択できます。たとえば、2つの行列の積A · Bを計算する場合、 Aを行優先、Bを列優先で格納するのが最適です。

storeとselectはどちらも（決定論的な最悪ケースでは）定数時間で動作します。配列は、保持する要素数nに対して線形（O ( n )）の空間を必要とします。

要素サイズがkの配列で、キャッシュラインサイズが B バイトのマシンでは、n個の要素を持つ配列を反復処理するには、要素が連続したメモリ位置を占めるため、最小限の ceiling( nk /B) 回のキャッシュミスで済みます。これは、ランダムなメモリ位置にあるn個の要素にアクセスするために必要なキャッシュミスの数よりも、おおよそ B/ k倍優れています。結果として、配列の逐次反復処理は、実際には他の多くのデータ構造の反復処理よりも明らかに高速です。これは参照の局所性と呼ばれる特性です (ただし、同じ (ローカル) 配列内で完全ハッシュまたは自明なハッシュを使用すると、さらに高速になり、定数時間で達成できないという意味ではありません)。ライブラリは、メモリ範囲をコピーするための低レベルの最適化された機能 ( memcpyなど) を提供しており、これを使用すると、個々の要素へのアクセスで達成できるよりもはるかに高速に、連続した配列要素のブロックを移動できます。このような最適化されたルーチンの高速化は、配列要素のサイズ、アーキテクチャ、および実装によって異なります。

メモリの観点から見ると、配列は要素ごとのオーバーヘッドのないコンパクトなデータ構造です。配列ごとのオーバーヘッド（インデックス境界を格納するなど）が発生する場合がありますが、これは言語に依存します。また、配列に格納された要素は、個々の変数に格納された同じ要素よりも少ないメモリを必要とする場合があります。これは、複数の配列要素を単一のワードに格納できるためです。このような配列は、パック配列と呼ばれることがよくあります。極端な例（ただしよく使用される例）はビット配列で、各ビットが単一の要素を表します。したがって、最もコンパクトな形式では、1つのオクテットに最大8つの異なる条件の256の異なる組み合わせを保持できます。

静的に予測可能なアクセスパターンを持つ配列アクセスは、データ並列性の主要な源泉である。

他のデータ構造との比較

動的配列または拡張可能配列は、配列に似ていますが、要素の挿入と削除機能が追加されています。特に末尾での追加と削除は効率的です。ただし、動的配列は線形（Θ（n））の追加ストレージを確保しますが、配列は追加ストレージを確保しません。

連想配列は、インデックス値が疎な場合に、膨大なストレージオーバーヘッドなしに配列のような機能を実現するメカニズムを提供します。たとえば、インデックス10億と20億にのみ値が含まれる配列は、このような構造を使用することでメリットが得られます。整数キーを持つ特殊な連想配列には、パトリシア・トライ、ジュディ配列、ファン・エムデ・ボアス・ツリーなどがあります。

バランスのとれたツリーは、インデックス付きアクセスにO(log n ) の時間を必要としますが、要素の挿入や削除も O(log n ) の時間で可能です^{[ 11 ]。}一方、拡張可能な配列は、任意の位置に要素を挿入または削除するのに線形 (Θ( n )) の時間を必要とします。

連結リストは、途中の要素の削除と挿入は定数時間で行えますが、インデックスによるアクセスには線形時間が必要です。メモリ使用量は一般的に配列よりも多くなりますが、それでも線形です。

イリフベクトルは、多次元配列構造の代替手段です。これは、次元が1つ少ない配列への参照の1次元配列を使用します。特に2次元の場合、この代替構造は、各行に対応するベクトルへのポインタのベクトルになります（CまたはC++ではポインタ）。したがって、配列Aのi行j列の要素には、二重インデックス（一般的な表記ではA[i][j]）でアクセスします。この代替構造は、各行のサイズが異なる、または一般的には、各インデックスの有効範囲が先行するすべてのインデックスの値に依存するジャグ配列を可能にします。また、列アドレスのインクリメントによる1回の乗算をビットシフト（行ポインタのベクトルをインデックス付けするため）と1回の追加のメモリアクセス（行アドレスのフェッチ）に置き換えることで、1回の乗算を節約できます。これは、一部のアーキテクチャでは有益となる場合があります。

配列の次元とは、要素を選択するために必要なインデックスの数です。したがって、配列を可能なインデックスの組み合わせの集合上の関数と見なすと、それはその定義域が離散部分集合である空間の次元になります。したがって、1 次元配列はデータのリスト、2 次元配列はデータの長方形、^{[ 12 ]} 3 次元配列はデータのブロックなどとなります。

これは、特定のドメインを持つすべての行列の集合の次元、つまり配列の要素数と混同してはならない。例えば、5行4列の配列は2次元だが、そのような行列は20次元空間を形成する。同様に、3次元ベクトルは、サイズ3の1次元配列で表現できる。

ウィキメディア・コモンズには、配列データ構造に関連するメディアがあります。

無料辞書であるWiktionaryで「array」を調べてみてください。

• ウィキブックのデータ構造/配列