6

だから、私はアイテムの配列が必要です。そして、どれが（C＃で）使用するのに最も高速/最適か疑問に思っていました。次のことを行います。

  1. 最後に要素を追加する
  2. 最初に要素を削除する
  3. 最初と最後の要素を見る (すべてのフレーム)
  4. たまにクリア
  5. それを通常の配列に変換します (リストではありません。私は iTween を使用しており、通常の配列を要求します)。ほぼすべてのフレームでこれを行います。

では、これらのことを考慮して、どのようなものを使用するのが最善でしょうか? 特に最後のものは、フレームごとにやっているからです。配列を使用する必要がありますか、それとも非常に高速に配列に変換し、開始と終了で要素を簡単に追加/削除できるものがありますか?

4

5 に答える 5

4

をご覧くださいLinkedList<T>。

最初または最後にアイテムを検査、追加、および削除するための O(1) サポートがあります。配列にコピーするには O(n) が必要ですが、それは避けられないようです。ICollection<T>使用している API がorを受け入れた場合、コピーを回避できますが、IEnumerable<T>それを変更できない場合は、 の使用に固執する可能性がありますToArray。

リストがフレームごとに 1 回未満しか変更されない場合は、配列をキャッシュしToArrayて、前のフレームからリストが変更された場合にのみ再度呼び出すことができます。この潜在的な最適化がどのように機能するかを理解するために、いくつかのメソッドの実装を次に示します。

private LinkedList<T> list = new LinkedList<T>();

private bool isDirty = true;

private T[] array;

public void Enqueue(T t)
{
    list.AddLast(t);
    isDirty = true;
}

public T[] ToArray()
{
    if (isDirty) 
    {
        array = list.ToArray();
        isDirty = false;
    }

    return array;
}
于 2012-12-16T23:14:51.393 に答える
4

要件 1) および 2) は を指しますQueue<T>。これは、これら 2 つの操作用に最適化された唯一の標準コレクションです。

3) 最後の要素に到達するには、ちょっとした工夫が必要です。最初はPeek()です。
4) 簡単です ( .Clear())
5) 標準的な.ToArray()方法でこれを行います。

O(n)項目 5 のすべての要素 ( ) のコピーを回避することはできません)

于 2012-12-16T23:17:50.757 に答える
2

クラス（構造体ではなく）を使用していると思いますか？(構造体 (値の型) を使用している場合は、状況が少し変わります。)

クラスを使用すると、これらSystem.Collections.Generic.Listすべてをすばやく実行できます。LinkedList で改善できる唯一の部分は、最初から削除することですが、単一のブロック メモリのコピーはそれほど苦痛ではなく、手間をかけずに配列を作成できます。

リンク リストを使用することはお勧めしません。特に、最初または最後からのみ削除する場合はそうです。(標準の LinkedList コレクションを使用して) 追加するたびに、メモリ割り当てが必要です (実際に追加したいものを参照するためにオブジェクトを構築する必要があります)。

リストには便利な関数もたくさんありますが、パフォーマンスが問題になる場合は注意が必要です。リストは基本的に配列であり、要素を追加すると大きくなります (リストをいっぱいにするたびに、リストは非常に大きくなり、過剰なメモリ操作が節約されます)。それらをクリアするのに労力は必要なく、割り当てられたメモリは別の日に使用するために残されます。

個人的な経験では、.NET は一般的なリンク リストには適していません。.NET 全体で動作するようにコードを記述する必要があります。リスト:

  • 使いやすい

  • やりたいことは全部やる

  • 記憶をスイスチーズのように残すことはありません (まあ、フレームごとに新しい配列を割り当てるときにできる最善のことです。新しい配列を作成する前にガベージ コレクターに古い配列を取り除く機会を与えることをお勧めします。これらの配列は、配列参照を再利用し、必要のないものを null にすることで大きくなります)。

正しい選択はアプリケーションの仕様に大きく依存しますが、私に言わせれば、List は常に安全な賭けであり、機能させるために構造固有のコードを記述する必要はありません。

リストを使用したい場合は、次のメソッドとプロパティを調べてください。

  • ToArray() // 必要な配列を作成します

  • Clear() // 配列をクリアします

  • Add(item) // 最後にアイテムを追加します

  • RemoveAt(index) // 最初の項目のインデックス 0、最後の項目の .Count - 1

  • Count // リスト内のアイテムの数を取得します - 無料のルックアップではないため、不要なリクエストを避けるようにしてください

この投稿全体がやり過ぎの場合は申し訳ありません。

于 2012-12-16T23:36:11.633 に答える
0

通常のリストは作業を行い、挿入の場合は LinkedList よりも高速です。

  • 最後に要素を追加 -> myList.Insert(myList.Count - 1)
  • 最初の要素を削除 -> myList.RemoveAt(0)
  • 最初と最後の要素 (フレームごと) を見る -> myList[0] または myList[myList.Count - 1]
  • ときどきクリア -> myList.Clear()
  • それを通常の配列に変換します (リストではありません。私は iTween を使用しており、通常の配列を要求します)。ほぼすべてのフレームでこれを行います。-> myList.ToArray()
于 2012-12-16T23:33:08.413 に答える
0

円形配列はどうですか？最後の要素と最初の要素のインデックスを保持すると、指定したすべての基準に対して O(1) を持つことができます。

編集: 容量に対して C++ ベクトル アプローチを取ることができます: いっぱいになるとサイズが 2 倍になります。

于 2012-12-16T23:20:22.393 に答える