高速にサイズ変更できる配列

StackOverflow https://stackoverflow.com/questions/413618

質問

パフォーマンスを低下させることなく、アイテムを簡単に追加できる一種の配列データ型を探しています。

  • システム。アレイ-Redim Preserve既存の要素の量と同じくらい遅く、RAM全体を古いものから新しいものにコピーします
  • System.Collections。 ArrayList -十分ですか？
  • System.Collections。 IList -十分ですか？
役に立ちましたか？

解決

ちょうどいくつかのデータ構造を要約する：

System.Collections.ArrayList ：型指定されていないデータ構造は廃止されました。代わりにList（of t）を使用してください。

System.Collections.Generic.List（of t）：これはサイズ変更可能な配列を表します。このデータ構造は、背後で内部配列を使用します。リストに項目を追加するのは、基礎となる配列が埋められていない限りO（1）です。そうでなければ、内部配列のサイズを変更して要素をコピーするためのO（n + 1）です。

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

アイテムの追加は、リストの最後に追加する場合にのみ効率的です。中央に挿入すると、配列はすべての項目を前方にシフトします。これはO（n）操作です。配列はアイテムを後方にシフトする必要があるため、アイテムの削除もO（n）です。

System.Collections.Generic.LinkedList（of t）：リスト内のアイテムへのランダムアクセスまたはインデックス付きアクセスが必要ない場合、たとえば、アイテムの追加と最初からの反復のみを計画します。最後に、LinkedListはあなたの友達です。挿入と削除はO（1）、ルックアップはO（n）です。

他のヒント

汎用リストを使用する必要があります<！> lt; <！> gt; （ System.Collections.Generic.List ）。 一定の償却時間で動作します。

また、以下の機能を配列と共有しています。

  • 高速ランダムアクセス（O（1）のリスト内の任意の要素にアクセスできます）
  • ループは簡単です
  • 開始または中間のオブジェクトの挿入と削除が遅い（リスト全体のコピーを実行する必要があるため）

最初または最後にすばやく挿入および削除する必要がある場合は、リンクリストまたはキューを使用してください

LinkedList <！> lt; T <！> gt;あなたのための構造の仕事？ （場合によっては）まっすぐな配列ほど直感的ではありませんが、非常に高速です。

  • 最後に追加するAddLast
  • リストに挿入するAddBefore / AddAfter
  • 先頭に追加するAddFirst

ただし、アイテムにアクセスするには構造を反復処理する必要があるため、ランダムアクセスではそれほど高速ではありません。ただし、リスト内の構造のコピーを取得するための.ToList（）および.ToArray（）メソッドがあります。 / array形式なので、読み取りアクセスのために、ピンチでそれを行うことができます。挿入のパフォーマンスの向上は、ランダムアクセスの必要性のパフォーマンスの低下を上回る場合もあれば、そうでない場合もあります。それはあなたの状況に完全に依存します。

正しい参照方法を判断するのに役立つこのリファレンスもあります：

リンクリストを使用するタイミング配列/配列リスト？

<！> quotとは何ですか？十分な<！> quot;あなたのために？そのデータ構造で正確に何をしたいのですか？

配列構造がない（つまり、O（n）アクセス）ため、O（n）ランタイムなしで中央に挿入できます。最後に挿入すると、O（n）最悪の場合、O（1）はArrayListのような自己サイズ変更配列に対して償却されます。

おそらく、ハッシュテーブル（どこでもO（1）アクセスと挿入を償却しましたが、挿入のO（n）最悪ケース）またはツリー（どこでもアクセスと挿入のO（log（n））が保証されています）が適しています。

速度が問題の場合、選択された答えが生の配列を使用するよりも優れているとは思いません最後に追加する場合を除き、1つの要素ではなく一度にチャンクを割り当てるため、少し賢くする必要があります。

コレクションの先頭/中央付近に頻繁に追加し、中央/末尾に頻繁にインデックス付けしない場合は、おそらくリンクリストが必要です。これは最速の挿入時間を持ち、素晴らしい反復時間を持ちます。インデックス付けで終わります（最後から3番目の要素や72番目の要素を見るなど）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top