動的配列

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
幾何学的展開を使用して、動的配列の最後にいくつかの値が挿入されます。灰色のセルは、拡張用に予約されたスペースを示します。ほとんどの挿入は高速(一定時間)ですが、再割り当てが必要なために低速な挿入もあります(Θ(n)時間、カメのラベルが付いています)。最終的なアレイ論理サイズ容量が表示されます。

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

動的配列は、動的に割り当てられた配列と同じではありません。動的に割り当てられた配列は、配列が割り当てられるときにサイズが固定される配列ですが、動的配列はそのような固定サイズの配列をバックエンドとして使用できます。[1]

制限付きサイズの動的配列と容量

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

固定サイズの配列は、最大論理サイズが固定されているアプリケーション(仕様など)で十分であるか、配列が割り当てられる前に計算できます。次の場合は、動的配列が推奨されます。

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

幾何学的拡張と償却原価

何度もサイズ変更のコストが発生しないように、動的配列はサイズを2倍にするなど、大幅にサイズ変更し、予約済みのスペースを将来の拡張に使用します。要素を最後に追加する操作は、次のように機能する可能性があります。

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

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

動的配列は、償却分析を教える場合の一般的な例です。[3] [4]

成長因子

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

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

実装 成長因子(a
Java ArrayList [1] 1.5(3/2)
Python PyListObject [7] 〜1.125(n + n >> 3)
Microsoft Visual C ++ 2013 [8] 1.5(3/2)
G ++ 5.2.0 [5] 2
Clang 3.6 [5] 2
Facebook folly / FBVector [9] 1.5(3/2)
Rust Vec [10] 2
スライスに行く[11] 1.25と2の間

パフォーマンス

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

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

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

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

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

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

バリアント

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

Goodrich [16]は、階層型ベクトルと呼ばれる動的配列アルゴリズムを提示しました。これは、配列内の任意の場所からの挿入と削除にOn 1 / k )のパフォーマンスを提供し、 Ok)は取得および設定されます。ここで、k≥2は定数パラメーターです。

ハッシュ配列ツリー(HAT)は、1996年にSitarskiによって公開された動的配列アルゴリズムです。[17]ハッシュ配列ツリーは、 n 1/2のストレージスペースを浪費します。ここで、 nは配列内の要素の数です。ハッシュされた配列ツリーの最後に一連のオブジェクトを追加すると、 アルゴリズムのパフォーマンスはO (1)で償却されます。

1999年の論文では、[18] Brodnik etal。階層化された動的配列データ構造を記述します。これは、任意の時点でn個の要素に対してn 1/2のスペースしか浪費しません。これらは、操作が一定時間償却されたままである場合、動的配列がこれだけのスペースを浪費する必要があることを示す下限証明ますさらに、それらは、バッファーの拡大と縮小が償却されるだけでなく、最悪の場合の一定時間になるという変形を示します。

Bagwell(2002)[19]は、動的配列を実装するように適合できるVListアルゴリズムを提示しました。

ナイーブなサイズ変更可能な配列(サイズ変更可能な配列の「最悪の実装」とも呼ばれます)は、配列に追加されたすべてのアイテムに対してreallocを呼び出すことにより、配列に割り当てられたサイズを、含まれるすべてのデータに対して十分な大きさに保ちます。ナイーブなサイズ変更可能な配列は、Cでサイズ変更可能な配列を実装する最も簡単な方法です。メモリを浪費することはありませんが、配列の最後に追加するには常にΘ(n)時間がかかります。[17] [20] [21] [22] [23] 線形に成長するアレイは、アレイのサイズを変更するたびにΘ(1)スペースを事前に割り当て(「無駄」)、ナイーブなサイズ変更可能なアレイよりも何倍も高速にします- -配列の最後に追加するには、まだΘ(n)時間ですが、定数ははるかに小さくなります。スペースに制約のあるアプリケーションで多くの小さなサイズ変更可能なアレイが必要な場合は、ナイーブなサイズ変更可能なアレイと直線的に成長するアレイが役立つ場合があります。それらは、指数関数的に成長する動的配列につながる教育的な例としても一般的に使用されます。[24]

言語サポート

C ++std::vectorRustは、 JavaAPI.NETFrameworkで提供される[25]クラスstd::vec::Vec同様に、動的配列の実装です[26]ArrayList

List<>.NET Frameworkのバージョン2.0で提供されるジェネリッククラスも、動的配列で実装されます。SmalltalkOrderedCollectionは、動的な開始インデックスと終了インデックスを備えた動的配列であり、最初の要素もO(1)で削除されます

Pythonlistデータ型の実装は動的配列であり、その成長パターンは0、4、8、16、24、32、40、52、64、76、... [27]

DelphiDは、言語のコアに動的配列を実装します。

AdaAda.Containers.Vectors汎用パッケージは、特定のサブタイプに動的配列の実装を提供します。

PerlRubyなどの多くのスクリプト言語は、組み込みのプリミティブデータ型として動的配列を提供します

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

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

参考文献

  1. ^ a b たとえば、OpenJDK6のjava.util.ArrayListクラスのソースコードを参照してください。
  2. ^ Lambert、Kenneth Alfred(2009)、「物理サイズと論理サイズ」Pythonの基礎:最初のプログラムからデータ構造まで、Cengage Learning、p。510、ISBN 978-1423902188
  3. ^ a b グッドリッチ、マイケルT .; Tamassia、Roberto(2002)、「1.5.2拡張可能なアレイ実装の分析」、アルゴリズム設計:基礎、分析、およびインターネットの例、Wiley、39〜41ページ
  4. ^ a b コルメン、トーマスH .; レイザーソン、チャールズE。; リベスト、ロナルドL。; スタイン、クリフォード(2001)[1990]。「17.4動的テーブル」。アルゴリズム入門(第2版)。MITPressとMcGraw-Hill。pp。416–424。ISBN 0-262-03293-7
  5. ^ a b c "C ++ STLベクトル:定義、成長因子、メンバー関数"2015年8月6日にオリジナルからアーカイブされまし2015年8月5日取得
  6. ^ 「1.5のベクトル成長因子」comp.lang.c ++。moderatedGoogleグループ。[デッドリンク]
  7. ^ github.com/python/cpython/からオブジェクトの実装を一覧表示し、2020-03-23を取得しました。
  8. ^ ブレイス、ハディ。「C ++ STLベクトルの分析:パート3-容量とサイズ」マイクロミステリー2015年8月5日取得
  9. ^ 「facebook / folly」GitHub 2015年8月5日取得
  10. ^ "rust-lang / rust"GitHub 2020年6月9日取得
  11. ^ "golang / go"GitHub 2021年9月14日取得
  12. ^ 1日目の基調講演-BjarneStroustrup:Channel9.msdn.comのGoingNative2012でのC ++ 11スタイル45またはフォイル44
  13. ^ 数の計算:kjellkod.wordpress.com、コードでリンクリストを二度と使用してはいけない理由
  14. ^ Brodnik、Andrej; カールソン、スヴァンテ; セッジウィック、ロバート; マンロー、JI; Demaine、ED(1999)、最適な時間と空間でのサイズ変更可能なアレイ(テクニカルレポートCS-99-09)(PDF)、ウォータールー大学コンピュータサイエンス学部
  15. ^ a b c クリス・オカサキ(1995)。「純粋関数型ランダムアクセスリスト」。機能プログラミング言語とコンピュータアーキテクチャに関する第7回国際会議の議事録:86–95。土井10.1145 /224164.224187
  16. ^ グッドリッチ、マイケルT .; Kloss II、John G.(1999)、「Tiered Vectors:Efficient Dynamic Arrays for Rank-Based Sequences」Workshop on Algorithms and Data Structures、Lecture Notes in Computer Science、1663205–216doi10.1007 / 3-540 -48447-7_21ISBN 978-3-540-66279-2
  17. ^ a b Sitarski、Edward(1996年9月)、「HATs:ハッシュ配列ツリー」、Algorithm Alley、Dr。Dobb's Journal21(11)
  18. ^ Brodnik、Andrej; カールソン、スヴァンテ; セッジウィック、ロバート; マンロー、JI; Demaine、ED(1999)、最適な時間と空間でのサイズ変更可能なアレイ(PDF)(テクニカルレポートCS-99-09)、ウォータールー大学コンピュータサイエンス学部
  19. ^ Bagwell、Phil(2002)、高速機能リスト、ハッシュリスト、Dequesおよび可変長配列、EPFL
  20. ^ マイクラム。 「動的配列」
  21. ^ 「償却時間」
  22. ^ 「ハッシュ化された配列ツリー:配列の効率的な表現」
  23. ^ 「複雑さのさまざまな概念」
  24. ^ ピーターカンコウスキー。 「Cの動的配列」
  25. ^ JavadocオンArrayList
  26. ^ ArrayListクラス
  27. ^ listobject.c(github.com)

外部リンク