6

私が正しく理解していれば (間違っている場合は訂正してください)、リストは .NET の配列によって実装されます。つまり、リスト内の項目を削除するたびに、すべてのリストが再割り当てされます (つまり、O(n)）。

私はゲームを開発しています。ゲームでは、特定の瞬間に多くの弾丸が空中を飛んでいます.100個の弾丸としましょう.フレームごとに数ピクセルずつ移動し、ゲーム内のオブジェクトとの衝突をチェックします.削除する必要がありますリストから衝突したすべての弾丸。

そこで、衝突した弾丸を別の一時リストに集めてから、次のことを行います。

foreach (Bullet bullet in bulletsForDeletion)
    mBullets.Remove(bullet);

ループはO(n)であり、削除はであるため、削除に) 時間をO(n)費やします。O(n^2

それを削除するより良い方法、またはより適切なコレクションを使用する方法はありますか?

4

7 に答える 7

6

セットとリンクされたリストは両方とも一定時間の削除があります。これらのデータ構造のいずれかを使用できますか?

からの削除の O(N) コストを回避する方法はありませんList<T>。これが問題になる場合は、別のデータ構造を使用する必要があります。bulletsToRemove を計算するコードも気持ちよくなるかもしれません。

ISet<T>オブジェクトのセット間の差異と交差を計算する優れた方法があります。

セットを使用すると順序が失われますが、弾丸を使用していることを考えると、それは問題ではないと思います。定数時間で列挙できます。

あなたの場合、次のように書くかもしれません：

mBullets.ExceptWith(bulletsForDeletion);
于 2012-12-29T13:19:11.857 に答える
5

新しいリストを作成します。

var newList = `oldList.Except(deleteItems).ToList()`.

可能な限り機能的なイディオムを使用するようにしてください。既存のデータ構造を変更せず、新しいデータ構造を作成してください。

このアルゴリズムは、ハッシュのおかげで O(N) です。

于 2012-12-29T13:21:49.960 に答える
2

（それを強調するListJavaの同等のもの）からに切り替えることはできませんか？LinkedList は、特定の要素を削除するには O(1) を必要としますが、インデックスで削除するには O(n) を必要としますArrayListLinkedList

于 2012-12-29T13:18:41.420 に答える
1

RemoveAt(int index)Remove(T item)後でその内部の最初のものを使用し、リフレクションを行うため、これは各関数内のコードよりも高速です。

また、各アイテムのインデックスを評価するための 2 番目のループを内部に持つRemove(T)functionがあります。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;
}

次のようなループを行います。

for (int i=MyList.Count-1; i>=0; i--) 
{
    // add some code here
    if (needtodelete == true)
    MyList.RemoveAt(i);
}
于 2012-12-29T13:25:58.927 に答える
1

リストが内部でどのように実装されるかは、考えるべきことではありません。その抽象化レベルでリストを操作する必要があります。

パフォーマンスの問題があり、それをリストに特定した場合は、それがどのように実装されているかを確認する時が来ました。

リストからアイテムを削除する場合は、 を使用できますmBullets.RemoveAll(predicate)。ここpredicateで、 は衝突したアイテムを識別する式です。

于 2012-12-29T13:19:06.780 に答える
0

「usr」によって提案された機能的なイディオムの精神では、リストからまったく削除しないことを検討するかもしれません。代わりに、更新ルーチンでリストを取得してリストを返すようにします。返されるリストには、「まだ生きている」オブジェクトのみが含まれます。その後、ゲーム ループの最後に (または、必要に応じてすぐに) リストを交換できます。私はこれを自分でやった。

于 2012-12-29T14:20:17.833 に答える