15

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

  • システム。配列- Redim PreserveRAM 全体を古いものから新しいものにコピーします。既存の要素の量と同じくらい遅くなります
  • System.Collections。ArrayList - 十分ですか?
  • System.Collections。IList - 十分ですか?
4

5 に答える 5

19

いくつかのデータ構造を要約すると:

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

System.Collections.Generic.List(of t) : これはサイズ変更可能な配列を表します。このデータ構造は、バックグラウンドで内部配列を使用します。List へのアイテムの追加は、基になる配列が満たされていない限り 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) です。

于 2009-01-05T16:28:20.023 に答える
15

これには Generic List<> ( System.Collections.Generic.List ) を使用する必要があります。一定の償却時間で動作します。

また、次の機能を配列と共有します。

  • 高速ランダム アクセス (O(1) のリスト内の任意の要素にアクセスできます)
  • ループするのが早い
  • 最初または途中でオブジェクトを挿入および削除するのが遅い（リスト全体のコピーを実行する必要があるため）

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

于 2009-01-05T16:19:48.747 に答える
3

LinkedList< T> 構造は役に立ちますか? （場合によっては）ストレート配列ほど直感的ではありませんが、非常に高速です。

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

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

どちらが正しい方法であるかを判断するのに役立つ次のリファレンスもあります。

配列/配列リストよりもリンクされたリストを使用するのはいつですか?

于 2009-01-05T16:20:43.767 に答える
1

あなたにとって「十分に良い」とは何ですか？そのデータ構造で正確に何をしたいですか？

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

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

于 2009-01-05T16:32:44.603 に答える
1

速度が問題である場合、選択した回答が生の配列を使用するよりも優れている方法はわかりませんが、サイズは変更されますが、配列のサイズを変更するために使用するのとまったく同じメカニズムを使用します (少し時間がかかるはずです) ) 常に最後に追加している場合を除きます。その場合、要素を 1 つだけではなく、一度にチャンクを割り当てるため、少し賢く行う必要があります。

コレクションの先頭/中間近くに頻繁に追加し、中間/末尾に頻繁にインデックスを作成しない場合は、リンク リストが必要になる可能性があります。これにより、挿入時間が最速になり、反復時間が長くなります。インデックス作成がうまくいきません (最後から 3 番目の要素や 72 番目の要素を見るなど)。

于 2009-01-05T17:30:50.727 に答える