私が正しく理解していれば間違っていれば修正してください。リストは.NETの配列で実装されています。つまり、リスト内の項目を削除するとすべてのリストが再割り当てされますターンを意味するO(n)）。リスト<T>を効率的に削除するには（C＃）？
私は多くの弾丸を空中に飛ばしています.100個の弾丸を各フレームごとに数ピクセル移動させ、ゲーム内のオブジェクトとの衝突をチェックしてみましょう。私は衝突したすべての弾丸をリストから削除する必要があります。
は、だから私は、別の一時リストで衝突した弾丸を収集して、次の操作を行います。ループがO(n)で、削除がO(n)あるので
foreach (Bullet bullet in bulletsForDeletion)
mBullets.Remove(bullet);
、私は削除するO(n^2）の時間を費やしています。
これを削除するには、より良い方法がありますか、それともより適切なコレクションがありますか？
新しいリストを作成します。
var newList = `oldList.Except(deleteItems).ToList()`.
は、可能な限り機能イディオムを使用してみてください。既存のデータ構造を変更したり、新しいデータ構造を作成したりしないでください。
このアルゴリズムはハッシングのおかげでO（N）です。
変数が別のリストにコピーされたときに、なぜ "deleteItems"リストに存在する場合は各アイテムをチェックする必要があるのですか？ O（n^2） – OopsUser
@OopsUser 'Except'は内部的にハッシュテーブルを構築しますので、存在チェックは' oldList'の項目ごとにO（1）であり、 'O（oldList.Count + deleteItems.Count）〜O （N） ' – usr
+1。 @OopsUser、[Except拡張メソッド]（http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except.aspx）は、ソース列挙からすべての項目を読み込み、 'deleteItems'にはありません。内部的には、 'deleteItems'のハッシュを構築し、そのハッシュに対する各入力の存在をテストします。ハッシュで見つからない項目だけが出力に渡されます。これはO（N）ですが、新しいハッシュと新しい配列（ 'ToList'によって作成された）を割り当てる結果になります。このメモリのオーバーヘッドを心配する必要はないかもしれませんが、それがあることを知っておく必要があります。 –
List（JavaのArrayListに相当）からLinkedListに切り替えることはできませんか？ LinkedListは特定の要素を削除するのにO（1）を使いますが、インデックスで削除するにはO（n）を使用します。
リストが内部的にどのように実装されているかは、その抽象化レベルのリストと対話する必要があります。
パフォーマンスの問題があり、それらをリストに示している場合は、その実装方法を見てみましょう。
リストからアイテムを削除する場合、mBullets.RemoveAll(predicate)を使用できます。predicateは、衝突したアイテムを識別する式です。
セットとリンクされたリストは両方とも一定の時間の削除を持っています。これらのデータ構造のいずれかを使用できますか？
O（N）の除去コストをList<T>から避ける方法はありません。これが問題の場合は、別のデータ構造を使用する必要があります。 bulletsToRemoveを計算するコードをより良く感じるかもしれません。
ISet<T>には、オブジェクトのセット間の差と交差を計算するための優れた方法があります。
あなたはセットを使って注文を失いますが、あなたが弾丸を持っているとすれば、それは問題ではないと思います。一定の時間内に列挙できます。あなたのケースでは
、あなたが書くかもしれない：
mBullets.ExceptWith(bulletsForDeletion);
"set"はどのように.netで呼び出されましたか？私はセットと呼ばれる総称を見ません。 リンクされたリスト（とセット）の問題は、データがメモリ内の同じ場所に置かれないことです。リストから読み込むと、キャッシュの利点がありますが、セット/リンクリストを使用すると、この利点を失う。 私は約1秒でリストから項目を削除する必要がありますが、リストから100回以上（衝突チェックなど）読む必要があります。 – OopsUser
@OopsUser、あなたは 'ISet
@OopsUser、また、 'bulletsForDeletion'の計算方法を知ることは役に立ちます。おそらく、それをより最適にする方法もあります。ここ –
RemoveAt(int index)は、後で最初の内部を使用してリフレクションを実行するため、各機能の内部のコードであるため、Remove(T item)より高速です。
また、Remove(T)には、それぞれの項目のインデックスを評価する第2のループが内部にあるIndexOfという機能があります。私はこのようなループだろう
public bool Remove(T item)
{
int index = this.IndexOf(item);
if (index < 0)
return false;
this.RemoveAt(index);
return true;
}
public void RemoveAt(int index)
{
if ((uint) index >= (uint) this._size)
ThrowHelper.ThrowArgumentOutOfRangeException();
--this._size;
if (index < this._size)
Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);
this._items[this._size] = default (T);
++this._version;
}
「USR」によって提案された機能的なイディオムの精神で
for (int i=MyList.Count-1; i>=0; i--)
{
// add some code here
if (needtodelete == true)
MyList.RemoveAt(i);
}
最後のコードブロックは 'MyList.Clear（）'の非効率なバージョンです。何か別のものを書くことを意味しましたか？ –
@DrewNoakes、はい、私は、質問するユーザーがいくつかのアイテムを削除するための条件を追加すると仮定し、彼は実際にはすべてのアイテムを削除しないで、自分の投稿を編集します。 – sharp12345
を、あなたは、すべてのあなたのリストから削除しないで考えるかもしれません。代わりに、更新ルーチンがリストを取得し、リストを返すようにしてください。返されるリストには、「静止している」オブジェクトのみが含まれます。その後、ゲームループの最後に（または必要に応じてすぐに）リストを入れ替えることができます。私はこれを自分でやった。
申し訳ありません。私たちはすべてここで学びます。 –
実際に問題があるのですか、または時期尚早に最適化していますか？ – Oded
実際の問題はありません.60fpsで動作します。このような操作がO（n^2）であってはならないため、私は間違ったことを書いているように感じました。 – OopsUser