動的配列

コンピュータサイエンスにおいて、動的配列、拡張可能配列、サイズ変更可能配列、動的テーブル、可変配列、または配列リストは、要素を追加または削除できるランダムアクセスの可変サイズのリストデータ構造です。これは、多くの現代の主流プログラミング言語の標準ライブラリで提供されています。動的配列は、割り当て時に指定する必要がある固定容量を持つ静的配列の制限を克服します。

動的配列は、動的に割り当てられた配列や可変長配列とは異なります。どちらも配列が割り当てられるときにサイズが固定される配列ですが、動的配列はバックエンドとしてそのような固定サイズの配列を使用することがあります。^[1]

単純な動的配列は、通常、すぐに必要な要素数よりも大きい固定サイズの配列を割り当てることによって構築できます。動的配列の要素は、基になる配列の先頭に連続して格納され、基になる配列の末尾の残りの位置は予約済み、つまり未使用です。予約済みのスペースを使用して、このスペースが完全に消費されるまで、動的配列の末尾に要素を一定時間で追加できます。すべてのスペースが消費され、追加の要素を追加する場合は、基になる固定サイズの配列のサイズを増やす必要があります。通常、サイズ変更は、新しい基になる配列を割り当て、元の配列から各要素をコピーする必要があるため、コストがかかります。サイズ変更が不要なため、動的配列の末尾から要素を削除するには、一定時間で行うことができます。動的配列の内容によって使用される要素の数は、その論理サイズまたはサイズです。一方、基になる配列のサイズは、動的配列の容量または物理サイズと呼ばれ、データを再配置せずに可能な最大サイズです。^[2]

最大論理サイズが固定されている (たとえば仕様によって) アプリケーションや、配列が割り当てられる前に計算できるアプリケーションでは、固定サイズの配列で十分です。次の場合は、動的配列が適している可能性があります。

• 配列が割り当てられる前に、最大論理サイズが不明であるか、計算が困難である
• 仕様で規定された最大論理サイズは変更される可能性があると考えられる
• 動的配列のサイズ変更にかかる償却コストは、パフォーマンスや応答性に大きな影響を与えません。

何度もサイズ変更するコストを回避するために、動的配列はサイズを 2 倍にするなど大幅にサイズ変更し、将来の拡張のために予約されたスペースを使用します。末尾に要素を追加する操作は、次のように機能します。

function insertEnd ( dynarray a , element e ) if ( a . size == a . capacity ) // a を現在の容量の 2 倍にサイズ変更します: a . capacity ← a . capacity * 2 // (ここで内容を新しいメモリ位置にコピーします) a [ a . size ] ← e a . size ← a . size + 1    
       
        
             
        
      
        

n個の要素が挿入されると、容量は等比数列を形成します。配列を任意の定数割合aで拡張すると、 n個の要素の挿入に全体でO ( n )時間がかかることが保証されます。つまり、挿入ごとに償却定数時間かかります。多くの動的配列では、サイズが容量の 30% などの特定のしきい値を下回ると、基礎となるストレージの一部が解放されます。このしきい値は、ヒステリシス(繰り返し拡大と縮小を回避するための安定したバンドを提供)を提供し、償却定数コストでの挿入と削除の混合シーケンスをサポートするために、1/ aより厳密に小さくする必要があります。

動的配列は、償却解析を教えるときによく使われる例です。^{[3] [4]}

動的配列の成長係数は、空間と時間のトレードオフやメモリアロケータ自体で使用されるアルゴリズムなど、いくつかの要因に依存します。成長係数aの場合、挿入操作あたりの平均時間はおよそa /( a −1) ですが、無駄になるセルの数は ( a −1) n^{で上限が決まります[引用が必要]}。メモリアロケータがファーストフィット割り当てアルゴリズムを使用する場合、 a =2などの成長係数値では、大量のメモリがまだ使用可能であるにもかかわらず、動的配列の拡張でメモリが不足する可能性があります。^{[5]理想的な成長係数値については、}黄金比や 1.5 などの提案など、さまざまな議論が行われてきました。 ^[6]ただし、多くの教科書では、 単純化と分析の目的でa = 2 を使用しています。 ^{[3] [4]}

以下は、いくつかの一般的な実装で使用される成長係数です。

動的配列は配列と同様のパフォーマンスを持ちますが、要素を追加および削除する新しい操作が追加されています。

• 特定のインデックスの値を取得または設定する（一定時間）
• 要素を順番に反復処理する（線形時間、優れたキャッシュ パフォーマンス）
• 配列の途中に要素を挿入または削除する（線形時間）
• 配列の末尾に要素を挿入または削除する（一定の償却時間）

動的配列は、参照の局所性とデータ キャッシュの利用率、コンパクトさ (メモリ使用量が少ない)、ランダム アクセスなど、配列の多くの利点を享受できます。動的配列には通常、サイズと容量に関する情報を格納するためのわずかな固定の追加オーバーヘッドしかありません。このため、動的配列はキャッシュフレンドリなデータ構造を構築するための魅力的なツールです。ただし、参照セマンティクスを適用する Python や Java などの言語では、動的配列には通常、実際のデータは格納されず、メモリの他の領域にあるデータへの参照が格納されます。この場合、配列内の項目に順番にアクセスすると、実際には複数の連続していないメモリ領域にアクセスすることになるため、このデータ構造のキャッシュ フレンドリさによる多くの利点が失われます。

リンク リストと比較すると、動的配列はインデックス作成が高速 (線形時間に対して定数時間) で、参照の局所性が向上するため、通常は反復処理も高速です。ただし、動的配列では、後続のすべての要素を移動する必要があるため、任意の場所で挿入または削除を行うには線形時間が必要ですが、リンク リストでは定数時間で実行できます。この欠点は、以下のバリアントで説明するギャップ バッファーと階層型ベクターバリアントによって軽減されます。また、高度に断片化されたメモリ領域では、大規模な動的配列用の連続した領域を見つけるのにコストがかかったり、不可能になったりすることがありますが、リンク リストでは、データ構造全体を連続して格納する必要はありません。

バランスのとれたツリーは、動的配列とリンク リストの両方のすべての操作をかなり効率的に提供しながらリストを格納できますが、非連続ストレージとツリーのトラバーサル/操作のオーバーヘッドにより、理論上も実際上も、末尾への挿入とリストの反復処理は動的配列よりも遅くなります。

ギャップ バッファは動的配列に似ていますが、同じ任意の場所の近くに集約された効率的な挿入および削除操作を可能にします。一部のdeque実装では配列 dequeが使用され、これにより、片側だけではなく、両端での均等償却定数時間の挿入/削除が可能になります。

Goodrich ^[18]は、配列内の任意の場所からの挿入と削除に対してO ( n1 ^{/ k} )のパフォーマンスを提供し、 O ( k )の取得と設定を提供する階層型ベクトルと呼ばれる動的配列アルゴリズムを提示した。ここでk≥2は定数パラメータである。

ハッシュ配列ツリー（HAT）は、1996年にSitarskiによって発表された動的配列アルゴリズムです。^[19]ハッシュ配列ツリーは、配列内の要素の数nのオーダーのnの^半分の量のストレージスペースを浪費します。このアルゴリズムは、ハッシュ配列ツリーの末尾に一連のオブジェクトを追加するときに、 O（1）の償却パフォーマンスを発揮します。

1999年の論文^[20]で、 Brodnikらは階層型動的配列データ構造について説明しており、これはどの時点でもn要素に対してn ^1/2のスペースしか無駄にせず、操作が償却定数時間のままであるためにはどの動的配列もこれだけのスペースを無駄にしなければならないことを示す下限を証明しています。さらに、彼らはバッファの拡大と縮小が償却時間だけでなく最悪の場合の定数時間になる変種を提示しています。

Bagwell(2002) ^[21]は、動的配列を実装するために適応できるVListアルゴリズムを提示した。

ナイーブなサイズ変更可能な配列は、サイズ変更可能な配列の「最悪の実装」とも呼ばれ、配列に追加された各項目ごとにrealloc を呼び出すなどして、配列の割り当てサイズを、含まれるすべてのデータに対してちょうど十分な大きさに保ちます。ナイーブなサイズ変更可能な配列は、C でサイズ変更可能な配列を実装する最も簡単な方法です。メモリを無駄にしませんが、配列の末尾への追加には常に Θ( n ) 時間がかかります。^{[19] [22] [23] [24] [25]} 線形に増加する配列は、配列のサイズを変更するたびに Θ(1) のスペースを事前割り当て (「無駄に」) するため、ナイーブなサイズ変更可能な配列よりも何倍も高速になります。配列の末尾への追加には依然として Θ( n ) 時間がかかりますが、その定数ははるかに小さくなります。ナイーブなサイズ変更可能な配列と線形に増加する配列は、スペースが制限されたアプリケーションで小さなサイズ変更可能な配列が多数必要な場合に役立ちます。これらは、指数関数的に増加する動的配列につながる教育的な例としてもよく使用されます。^[26]

C++とstd::vectorRustは動的std::vec::Vec配列の実装であり、Java API ^{[28] : 236}と.NET Frameworkで提供されるArrayList^[27]クラスも同様である。^{[29] [30] : 22}

List<>.NET Framework バージョン 2.0 で提供される汎用クラスも、動的配列を使用して実装されています。Smalltalkのは、OrderedCollection動的な開始インデックスと終了インデックスを持つ動的配列であり、最初の要素の削除も O(1) になります。

Pythonのlistデータ型の実装は動的配列であり、その成長パターンは次の通りである: 0、4、8、16、24、32、40、52、64、76、... ^[31]

DelphiとD は、言語の中核に動的配列を実装します。

Adaの Ada.Containers.Vectors ジェネリック パッケージは、特定のサブタイプに対して動的配列の実装を提供します。

PerlやRubyなどの多くのスクリプト言語では、組み込みのプリミティブ データ型として動的配列が提供されています。

いくつかのクロスプラットフォーム フレームワークは、Core Foundationのや、GLibのなど、Cの動的配列実装を提供します。 CFArrayCFMutableArrayGArrayGPtrArray

Common Lisp は、組み込み型を調整可能に設定し、挿入位置をフィルポインタで設定できるarrayようにすることで、サイズ変更可能なベクトルの基本的なサポートを提供します。

• スタック（データ構造）
• キュー（データ構造）

• NIST アルゴリズムとデータ構造辞書: 動的配列
• VPOOL - 動的配列の C 言語実装。
• CollectionSpy — ArrayList および Vector 関連の問題のデバッグを明示的にサポートする Java プロファイラー。
• オープン データ構造 - 第 2 章 - 配列ベースのリスト、Pat Morin