Как эффективно удалить из списка<T> (C#)?

Question

Если я правильно понял (и, пожалуйста, поправьте меня, если я ошибаюсь), список реализуется массивом в.NET, что означает, что каждое удаление элемента в списке приведет к перераспределению всего списка (что, в свою очередь, означает, что O(n)).

Я разрабатываю игру, в игре у меня много пуль, летающих в воздухе в любой момент, скажем, 100 пуль, каждый кадр я перемещаю их на несколько пикселей и проверяю на предмет столкновения с объектами в игре, мне нужно удалить из списка каждая пуля, которая столкнулась.

Поэтому я собираю столкнувшуюся пулю в другой временный список и затем делаю следующее:

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

Потому что цикл O(n) и удаление O(n), Я потратил O(n^2время убрать.

Есть ли лучший способ удалить его или использовать более подходящую коллекцию?

Answer 1

Создать новый список:

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

Попробуйте использовать функциональные идиомы везде, где это возможно. Не изменяйте существующие структуры данных, создавайте новые.

Этот алгоритм O(N) благодаря хешированию.

Answer 2

Наборы и связанные списки имеют постоянное время удаления. Можете ли вы использовать любую из этих структур данных?

Там нет никакого способа избежать O(N) стоимость удаления из List<T>, Вам нужно будет использовать другую структуру данных, если это проблема для вас. Это может сделать код, который вычисляет bulletsToRemove, также более приятным.

ISet<T> имеет хорошие методы для вычисления различий и пересечений между наборами объектов.

Вы теряете порядок, используя наборы, но, учитывая, что вы принимаете пули, я думаю, это не проблема. Вы все еще можете перечислить его в постоянное время.

---

В вашем случае вы можете написать:

mBullets.ExceptWith(bulletsForDeletion);

Answer 3

Вы не можете просто переключиться с List (эквивалент Java ArrayList выделить это) LinkedList? LinkedList использует O(1) для удаления определенного элемента, но O(n) для удаления по индексу

Answer 4

То, как список реализован внутри, - это не то, о чем вы должны думать. Вы должны взаимодействовать со списком на этом уровне абстракции.

Если у вас есть проблемы с производительностью, и вы указываете их на список, самое время посмотреть, как это реализовано.

Что касается удаления элементов из списка - вы можете использовать mBullets.RemoveAll(predicate), где predicate это выражение, которое идентифицирует предметы, которые столкнулись.

Answer 5

В идеале не должно быть важно думать о том, как C# реализует свои методы List, и несколько прискорбно, что он переназначает все элементы массива после индекса. iкогда делаешь somelist.RemoveAt(i).Однако иногда необходима оптимизация реализаций стандартных библиотек.

Если вы обнаружите, что ваше выполнение требует неприемлемых усилий для перетасовки элементов списка при удалении их из списка с помощью RemoveAt, один подход, который может сработать для вас, — это поменять местами его с концом, а затем RemoveAtв конце списка:

      if (i < mylist.Count-1) {
     mylist[i] = mylist[mylist.Count-1];
}
mylist.RemoveAt(mylist.Count-1);

Это, конечно, операция O(1).

Answer 6

RemoveAt(int index) быстрее чем Remove(T item) потому что позже использовать первый внутри него, делая отражение, это код внутри каждой функции.

Также, Remove(T) имеет функцию 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);
}

Answer 7

В духе функциональной идиомы, предложенной "usr", вы можете вообще не удалять из своего списка. Вместо этого пусть ваша процедура обновления возьмет список и вернет список. Возвращенный список содержит только "еще живые" объекты. Затем вы можете поменять списки в конце игрового цикла (или сразу, если это необходимо). Я сделал это сам.