配列データ構造

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスでは配列データ構造、または単に配列は、要素または変数)のコレクションで構成されるデータ構造であり、それぞれが少なくとも1つの配列インデックスまたはキーによって識別されます。配列は、各要素の位置が数式によってそのインデックスタプルから計算できるように格納されます。[1] [2] [3]最も単純なタイプのデータ構造は、1次元配列とも呼ばれる線形配列です。

たとえば、インデックス0〜9の32ビット(4バイト)整数変数10個の配列は、メモリアドレス2000、2004、2008、...、2036(16進数、 )に10ワードとして格納できます。 、、...、)、インデックスiの要素のアドレスが2000 +(i ×4)になるようにします。[4]0x7D00x7D40x7D80x7F4

配列の最初の要素のメモリアドレスは、最初のアドレス、基礎アドレス、またはベースアドレスと呼ばれます。

行列の数学的概念は2次元グリッドとして表すことができるため、2次元配列は行列と呼ばれることもあります。場合によっては、「ベクトル」という用語は、配列を指すために計算で使用されますが、ベクトルではなくタプルが数学的に正しい同等物です。多くの場合、テーブルは配列の形式で実装されます。特にルックアップテーブルです。テーブルという単語は、配列の同義語として使用されることがあります。

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

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

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

この用語は、特にアルゴリズムの説明で、連想配列または「抽象配列」、配列の本質的な特性をキャプチャすることを目的とし た理論的なコンピュータサイエンスモデル(抽象データ型またはADT)を意味するためにも使用されます。

歴史

最初のデジタルコンピュータは、機械語プログラミングを使用して、データテーブル、ベクトルおよび行列の計算、およびその他の多くの目的のために配列構造を設定およびアクセスしました。John von Neumannは、最初のストアドプログラムコンピュータの構築中に、1945年に最初の配列ソートプログラム(マージソート)を作成しました。[6] p。159配列のインデックス作成は、元々自己変更コードによって行われ、後にインデックスレジスタ間接アドレス指定を使用して行われました。Burroughs B5000やその後継機など、1960年代に設計された一部のメインフレームは、メモリセグメンテーションを使用してハードウェアのインデックス境界チェックを実行していました。[7]

アセンブリ言語は通常、マシン自体が提供するものを除いて、配列を特別にサポートしていません。FORTRAN(1957)、Lisp(1958)、COBOL(1960)、およびALGOL 60 (1960)を含む初期の高級プログラミング言語は、多次元配列をサポートし、C(1972)もサポートしていました。C ++ (1983)では、実行時に次元が固定される多次元配列[3] [5]と、実行時に柔軟な配列のクラステンプレートが存在します。[2]

アプリケーション

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

配列は、リスト、ヒープハッシュテーブル、両端キューキュースタック文字列、 VListなどの他のデータ構造を実装するために使用されます他のデータ構造の配列ベースの実装は、多くの場合、単純でスペース効率が高く(暗黙のデータ構造)、スペースオーバーヘッドはほとんど必要ありませんが、ツリーベースのデータ構造(ソートされた配列検索ツリー

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

配列は、(そうでなければ反復的な)複数のステートメントのコンパクトな代替手段として、プログラムの部分的または完全な制御フローを決定するために使用できます。IFこれらは、このコンテキストでは制御テーブルとして知られており、配列に含まれる値に応じて制御フローが変更される専用のインタープリターと組み合わせて使用​​されます。配列には、実行のパスを指示する サブルーチン ポインター(またはSWITCHステートメントによって操作できる相対的なサブルーチン番号)が含まれる場合があります。

要素識別子とアドレス指定式

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

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

0(ゼロベースのインデックス付け
配列の最初の要素は、0の添え字でインデックス付けされます。[8]
1(1ベースのインデックス作成
配列の最初の要素は、添え字1でインデックス付けされます。
n(nベースのインデックス
配列のベースインデックスは自由に選択できます。通常、 nベースのインデックス付けを許可するプログラミング言語では、負のインデックス値や、列挙型などの他のスカラーデータ型も許可されます。または、文字を配列インデックスとして使用することもできます。

ゼロベースのインデックスを使用することは、CJavaLispを含む多くの影響力のあるプログラミング言語の設計上の選択です。これにより、下付き文字が配列の開始位置からのオフセットを参照するため、最初の要素のオフセットがゼロになる、より簡単な実装につながります。

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

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

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

一次元配列

1次元配列(または1次元配列)は、線形配列の一種です。その要素へのアクセスには、行または列のインデックスを表すことができる単一の添え字が含まれます。

int anArrayName[10];例として、 10個の整数の1次元配列を宣言するC宣言について考えてみます。ここで、配列は型の10個の要素を格納できintます。この配列には、0から9までのインデックスがあります。たとえば、式anArrayName[0]anArrayName[9]はそれぞれ最初と最後の要素です。

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

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

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

多次元配列

多次元配列の場合、インデックスijを持つ要素は、アドレスB + ci + djを持ちます。ここで、係数cdは、それぞれ列のアドレスの増分です。

より一般的には、k 次元配列では、インデックスi 1i 2、...、ikを持つ要素のアドレスは次のようになります。

B + c 1i 1 + c 2i 2 +… + c kik

例:int a [2] [3];

これは、配列aに2行3列があり、配列が整数型であることを意味します。ここでは、6つの要素を格納できます。これらの要素は線形に格納されますが、最初の行から線形に始まり、2番目の行に続きます。上記配列11、12、13、21、22、23として格納ます_

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

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

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

ドープベクトル

アドレス指定式は、次元d、ベースアドレスB、および増分c 1c 2、...、ckによって完全に定義されますこれらのパラメータを、配列の記述子またはストライドベクトルまたはドープベクトルと呼ばれるレコードにパックすると便利なことがよくあります[2] [3]各要素のサイズ、および各インデックスに許可されている最小値と最大値も、ドープベクトルに含めることができます。ドープベクトルは配列の完全なハンドルであり、配列を引数としてプロシージャに渡すための便利な方法です。多くの便利な配列スライシング操作(サブ配列の選択、インデックスの交換、インデックスの方向の反転など)は、ドープベクトルを操作することで非常に効率的に実行できます。[2]

コンパクトなレイアウト

多くの場合、係数は、要素がメモリの連続した領域を占めるように選択されます。ただし、それは必要ありません。配列が常に連続した要素で作成されている場合でも、一部の配列スライシング操作では、それらから非連続のサブ配列が作成される場合があります。

行と列の主要な順序の図

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

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

1 2 3 4 5 6 7 8 9

列優先順(従来はFortranで使用されていました)では、各列の要素はメモリ内で連続しており、列のすべての要素のアドレスは、連続する列のどの要素よりも低くなっています。

1 4 7 2 5 8 3 6 9

3つ以上のインデックスを持つ配列の場合、「行メジャーオーダー」は、インデックスタプルが最後のインデックスで1つだけ異なる2つの要素を連続した位置に配置します。「列の主な順序」は、最初のインデックス に関して類似しています。

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

サイズ変更

静的配列のサイズは作成時に固定されているため、要素を挿入または削除できません。ただし、新しい配列を割り当て、古い配列の内容をその配列にコピーすることにより、動的バージョンの配列を効果的に実装することができます。動的配列を参照してくださいこの操作が頻繁に行われない場合、配列の最後に挿入するには、償却された定数時間のみが必要です。

一部の配列データ構造はストレージを再割り当てしませんが、カウントまたはサイズと呼ばれる、使用中の配列の要素数のカウントを格納します。これにより、アレイは事実上、最大サイズまたは容量が固定された動的アレイになります。Pascal文字列はこの例です。

非線形式

より複雑な(非線形)式が使用されることがあります。たとえば、コンパクトな2次元三角配列の場合、アドレス式は2次の多項式です。

効率

保存選択の両方で、 (決定論的な最悪の場合)一定の時間がかかります。配列は、保持する要素数nの線形(On))空間を取ります。

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

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

静的に予測可能なアクセスパターンを使用した配列アクセスは、データの並列処理の主な原因です。

他のデータ構造との比較

リストデータ構造の比較
ピーク
(インデックス)
で変更(挿入または削除)… 余剰スペース、
平均
始まり 終わり 真ん中
リンクリスト Θ(n Θ(1) Θ(1)、既知の終了要素。
Θ(n)、未知の末端要素
ピーク時間+
Θ(1)[9] [10]
Θ(n
配列 Θ(1) 該当なし 該当なし 該当なし 0
動的配列 Θ(1) Θ(n Θ(1)償却 Θ(n Θ(n[11]
平衡二分木 Θ(logn) Θ(logn) Θ(log n Θ(log n Θ(n
ランダムアクセスリスト Θ(logn)[12] Θ(1) 該当なし[12] 該当なし[12] Θ(n
ハッシュ配列ツリー Θ(1) Θ(n Θ(1)償却 Θ(n Θ(√n

動的配列または拡張可能な配列は配列に似ていますが、要素を挿入および削除する機能が追加されています。最後に追加と削除を行うと特に効率的です。ただし、それらは線形(Θn))の追加ストレージを予約しますが、アレイは追加のストレージを予約しません。

連想配列は、インデックス値がまばらな場合に、ストレージのオーバーヘッドを大幅に増やすことなく、配列のような機能を実現するメカニズムを提供します。たとえば、インデックス10億と20億の値のみを含む配列は、このような構造を使用することでメリットが得られる場合があります。整数キーを持つ特殊な連想配列には、PatriciaトライJudy配列、およびvan EmdeBoasツリーが含まれます。

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

リンクリストを使用すると、途中で一定時間の削除と挿入が可能になりますが、インデックス付きアクセスには線形時間がかかります。それらのメモリ使用量は通常、アレイよりも劣りますが、それでも線形です。

1次元配列(行)の1次元配列として格納された2次元配列。

Iliffeベクトルは、多次元配列構造の代替手段です。1次元未満の配列への参照の1次元配列を使用します。特に2次元の場合、この代替構造は、各行に1つずつ、ベクトルへのポインターのベクトルになります(cまたはc ++のポインター)。したがって、配列Aの行iと列jの要素には、ダブルインデックス(通常の表記ではA [ i ] [ j ])によってアクセスされます。この代替構造により、ジャグ配列が可能になります、各行のサイズが異なる場合があります。または、一般に、各インデックスの有効な範囲は、先行するすべてのインデックスの値によって異なります。また、ビットシフト(行ポインタのベクトルにインデックスを付けるため)と1つの追加メモリアクセス(行アドレスのフェッチ)に置き換える1つの乗算(列アドレスの増分による)を節約します。これは、一部のアーキテクチャでは価値がある場合があります。

寸法

配列の次元は、要素を選択するために必要なインデックスの数です。したがって、配列が可能なインデックスの組み合わせのセットの関数として見られる場合、それはそのドメインが離散サブセットである空間の次元です。したがって、1次元配列はデータのリスト、2次元配列はデータの長方形、[14] 3次元配列はデータのブロックなどです。

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

も参照してください

参考文献

  1. ^ ブラック、ポールE.(2008年11月13日)。「配列」アルゴリズムとデータ構造の辞書米国国立標準技術研究所2010年8月22日取得
  2. ^ a b c d e Bjoern Andres; Ullrich Koethe; Thorben Kroeger; ハンプレヒト(2010)。「ランタイム-C ++ 98およびC ++ 0x用の柔軟な多次元配列とビュー」。arXiv1008.2909 [ cs.DS ]。
  3. ^ a b c d ガルシア、ロナルド; ラムズデイン、アンドリュー(2005)。「MultiArray:配列を使用したジェネリックプログラミング用のC ++ライブラリ」。ソフトウェア:実践と経験35(2):159–188。土井10.1002 /spe.630ISSN0038-0644_ S2CID10890293_  
  4. ^ デビッド・R・リチャードソン(2002)、データ構造に関する本。iUniverse、112ページ。ISBN 0-595-24039-9 ISBN978-0-595-24039-5 _  
  5. ^ a b Veldhuizen、Todd L.(1998年12月)。Blitz ++の配列(PDF)オブジェクト指向並列環境でのコンピューティング。コンピュータサイエンスの講義ノート。1505.スプリンガーベルリンハイデルベルク。pp。223–230。土井10.1007 / 3-540-49372-7_24ISBN  978-3-540-65387-52016年11月9日にオリジナル (PDF)からアーカイブされました。
  6. ^ Donald Knuth、 The Art of Computer Programming、vol。3.アディソン-ウェスリー
  7. ^ Levy、Henry M.(1984)、機能ベースのコンピュータシステム、デジタルプレス、p。22、ISBN 9780932376220
  8. ^ 「配列コードの例-PHP配列関数-PHPコード」コンピュータプログラミングWebプログラミングのヒント。2011年4月13日にオリジナルからアーカイブされました2011年4月8日取得ほとんどのコンピューター言語では、配列のインデックス(カウント)は1からではなく0から始まります。配列の最初の要素のインデックスは0、配列の2番目の要素のインデックスは1というように続きます。以下の名前の配列で、インデックスと値を確認できます。
  9. ^ 1日目の基調講演-BjarneStroustrup:Channel9.msdn.comのGoingNative2012でのC ++ 11スタイル45またはフォイル44
  10. ^ 数の計算:kjellkod.wordpress.com、コードでリンクリストを二度と使用してはいけない理由
  11. ^ Brodnik、Andrej; カールソン、スヴァンテ; セッジウィック、ロバート; マンロー、JI; Demaine、ED(1999)、最適な時間と空間でのサイズ変更可能なアレイ(テクニカルレポートCS-99-09)(PDF)、ウォータールー大学コンピュータサイエンス学部
  12. ^ a b c クリス・オカサキ(1995)。「純粋関数型ランダムアクセスリスト」。機能プログラミング言語とコンピュータアーキテクチャに関する第7回国際会議の議事録:86–95。土井10.1145 /224164.224187
  13. ^ 「カウントされたBツリー」
  14. ^ 「2次元配列\ Processing.org」processing.org 2020年5月1日取得

外部リンク