2

順次アクセスするだけの高速コレクションタイプが必要です。高速追加と高速クリアが必要です。非常に短い処理時間でクリアできるコレクションタイプがいくつかあると思います。

List<>私はそれがO（n）操作であることを読みました。超高速クリア能力のあるコレクションタイプはありますか？多分スタック？List<int>またはList<Double>（非参照型）はより高速な操作を可能にしますか？

4

4 に答える 4

4

O（n）は検索中です。Enumerable（およびおそらくその部分について私が知らないインデクサー）を使用してリストをステップスルーしている場合、それはO（1）ルックアップになります。呼び出しを行っていない限り、クリアもO（1）で、非常に高速になります。Remove(T obj)Clear()クリアはまだO（n）です。

サイズ変更が必要ない場合は、配列を宣言するだけでO（1）インデクサーが作成され、「クリア」するには、逆参照して新しい配列を作成します。

于 2012-11-17T06:18:03.233 に答える
2

明確にするために O(1) を主な目標とする場合、適切なコレクション (List、LinkedList、Array) をカスタム クラスのメンバーとして実装するIListかICollection、そのメンバーにインデックス作成/反復を転送します。clear simple を実装するには、その内部メンバーの新しいインスタンスを作成します。

class FastClearList<T> : IList<T>
{
  List<T> inner = new List<T>();

  public void Clear()
  {
     inner = new List<T>(); // recreating list here will give O(1)
  }

  public IEnumerator<T> GetEnumerator()
  {
     return inner.GetEnumerator();
  }
  // forward everything else ...
}
于 2012-11-17T06:42:44.973 に答える
2

本当に高速なクリアが必要で、毎回新しいメモリを割り当てたくない場合は、内部カウンターを 0 にリセットするだけで、O(1)IList<T>である a を使用して の独自の実装を作成することもできます。クラスは保持しますリストが現在どこにあるかを決定するカウンター。リセットするには、独自の実装でこれを 0 に設定できます。内部配列は実際にはクリアされませんが、リストに追加されたアイテムは古い値を上書きし、列挙はそれ以上継続しないため、古い値に触れることはありません。ClearList<T>_size_size

基本的に、gettable だけでなく、List<T>where is settable を 0 に設定する必要があります。Count

ただしT、 が参照型の場合、この種のリストは古い値への参照を保持し、それらがガベージ コレクションされるのを防ぐことに注意してください。したがって、値の型を保存する場合にのみ使用するのが最適です。

于 2012-11-17T17:49:55.157 に答える
0

List は、クリアされたオブジェクトへの参照をクリアする必要があります。最善の方法は、List<> をクリアする代わりに新しい List<> を作成するか、そのようなアプローチを実装するラッパー/ファクトリを作成することです。

于 2012-11-17T21:37:32.337 に答える