Как эффективно удалить из List‹T› (C#)?

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

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

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

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

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

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


.net generics collections c# generic-collections
person OopsUser    schedule 29.12.2012    source источник
comment
Не извиняйся. Мы все здесь для того, чтобы учиться.   -  person Soner Gönül    schedule 29.12.2012
comment
Вы уверены, что у вас есть реальная проблема, или вы оптимизируете преждевременно?   -  person Oded    schedule 29.12.2012
comment
у меня нет реальной проблемы, он работает со скоростью 60 кадров в секунду, я просто чувствовал, что пишу что-то неправильное, потому что такая операция не должна быть O (n ^ 2).   -  person OopsUser    schedule 29.12.2012

Ответы (6)


arrow_upward
5
arrow_downward

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

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

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

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

person usr    schedule 29.12.2012
comment
Почему O(n)? когда он копирует переменную в другой список, ему нужно проверить каждый элемент, если он существует в списке deleteItems, это выглядит как O (n ^ 2) - person OopsUser; 29.12.2012
comment
@OopsUser Except строит внутреннюю хеш-таблицу, поэтому проверка существования составляет O (1) для каждого элемента в oldList. Это делает O(oldList.Count + deleteItems.Count) ~ O(N) - person usr; 29.12.2012
comment
+1. @OopsUser, метод расширения Except читается каждый элемент из исходного перечисления и выводит те, которых нет в deleteItems. Внутри он строит хэш deleteItems и проверяет наличие каждого ввода по этому хешу. На выход передаются только те элементы, которые не найдены в хэше. Это O(N), однако это приведет к выделению новых хэшей и новых массивов (созданных ToList). Возможно, вам не нужно беспокоиться об этих накладных расходах памяти, но вы должны знать, что они есть. - person Drew Noakes; 29.12.2012
comment
Спасибо, это именно то, что я хотел, потому что я думаю, что лучше не менять список на Set или LinkedList, чтобы у меня была лучшая производительность при чтении из него. - person OopsUser; 29.12.2012

arrow_upward
6
arrow_downward

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

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

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

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

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

mBullets.ExceptWith(bulletsForDeletion);
person Drew Noakes    schedule 29.12.2012
comment
Как установить в .net? я не вижу никакого универсального набора. Проблема со связанным списком (и наборами) заключается в том, что данные не находятся в одном и том же месте в памяти, поэтому, когда я читаю из списка, у меня есть преимущество кэширования, но когда я использую наборы/связанные списки, я теряю это преимущество. Хотя мне приходится удалять элементы из списка примерно раз в секунду, мне нужно читать из списка в 100 раз больше (проверка столкновений и т. д.) - person OopsUser; 29.12.2012
comment
@OopsUser, вы ищете ISet<T>, о котором вы можете прочитать здесь. - person Drew Noakes; 29.12.2012
comment
@OopsUser, также было бы полезно посмотреть, как вы вычисляете bulletsForDeletion. Возможно, есть способ сделать это более оптимальным. - person Drew Noakes; 29.12.2012
comment
Вот код: foreach (пуля, пуля в mBullets) { foreach (игрок, игрок в игроках) { if (player.Location.Intersects (bullet.Location) { bulletsForDeletion.Add (bullet); player.HP-=1; } } } - person OopsUser; 29.12.2012

arrow_upward
2
arrow_downward

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

person usr-local-ΕΨΗΕΛΩΝ    schedule 29.12.2012

arrow_upward
1
arrow_downward

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

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

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

person Oded    schedule 29.12.2012

arrow_upward
1
arrow_downward

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);
}
person sharp12345    schedule 29.12.2012
comment
Ваш последний блок кода — неэффективная версия MyList.Clear(). Вы хотели написать что-то другое? - person Drew Noakes; 29.12.2012
comment
@DrewNoakes, да, я предполагаю, что запрашивающий пользователь добавит несколько условий для удаления некоторых элементов, на самом деле он не будет удалять все элементы, отредактировал мой пост. - person sharp12345; 29.12.2012

arrow_upward
0
arrow_downward

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

person Griffin    schedule 29.12.2012