CODEWITHSUNDEEP
c#.netgenericscollectionsgeneric-collections
OopsUser
OopsUser

Reputation: 4784

How to remove from List<T> efficiently (C#)?

If I understood correctly (and please correct me if i'm wrong), list is implemented by array in .NET, which means that every deletion of an item in the list will cause re-allocation of all the list (which in turn means O(n)).

I'm developing a game, in the game i have many bullets fly in the air on any giving moment, let's say 100 bullets, each frame I move them by few pixels and check for collision with objects in the game, I need to remove from the list every bullet that collided.

So I collect the collided bullet in another temporary list and then do the following:

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

Because the loop is O(n) and the remove is O(n), I spend O(n^2) time to remove.

Is there a better way to remove it, or more suitable collection to use?

Upvotes: 8

Views: 3517

Answers (7)

Mars
Mars

Reputation: 195

Ideally, it shouldn't be important to think about how C# implements its List methods, and somewhat unfortunate that it reassigns all the array elements after index i when doing somelist.RemoveAt(i). Sometimes optimizations around standard library implementations are necessary, though.

If you find your execution is expending unacceptable effort shuffling list elements around when removing them from a list with RemoveAt, one approach that might work for you is to swap it with the end, and then RemoveAt off the end of the list:

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

This is of course an O(1) operation.

Upvotes: 1

Griffin
Griffin

Reputation: 1595

In the spirit of functional idiom suggested by "usr", you might consider not removing from your list at all. Instead, have your update routine take a list and return a list. The list returned contains only the "still-alive" objects. You can then swap lists at the end of the game loop (or immediately, if appropriate). I've done this myself.

Upvotes: 0

sharp12345
sharp12345

Reputation: 4500

RemoveAt(int index) is faster than Remove(T item) because the later use the first inside it, doing reflection, this is the code inside each function.

Also, Remove(T) has the function IndexOf, which has inside it a second loop to evalute the index of each item.

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;
}

I would do a loop like this:

for (int i=MyList.Count-1; i>=0; i--) 
{
    // add some code here
    if (needtodelete == true)
    MyList.RemoveAt(i);
}

Upvotes: 1

Drew Noakes
Drew Noakes

Reputation: 310832

Sets and linked lists both have constant time removal. Can you use either of those data structures?

There's no way to avoid the O(N) cost of removal from List<T>. You'll need to use a different data structure if this is a problem for you. It may make the code which calculates bulletsToRemove feel nicer too.

ISet<T> has nice methods for calculating differences and intersections between sets of objects.

You lose ordering by using sets, but given you are taking bullets, I'm guessing that is not an issue. You can still enumerate it in constant time.

In your case, you might write:

mBullets.ExceptWith(bulletsForDeletion);

Upvotes: 8

usr
usr

Reputation: 171178

Create a new list:

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

Try to use functional idioms wherever possible. Don't modify existing data structures, create new ones.

This algorithm is O(N) thanks to hashing.

Upvotes: 6

Oded
Oded

Reputation: 498934

How a list is implemented internally is not something you should be thinking about. You should be interacting with the list in that abstraction level.

If you do have performance problems and you pinpoint them to the list, then it is time to look at how it is implemented.

As for removing items from a list - you can use mBullets.RemoveAll(predicate), where predicate is an expression that identifies items that have collided.

Upvotes: 1

usr-local-ΕΨΗΕΛΩΝ
usr-local-ΕΨΗΕΛΩΝ

Reputation: 26874

Can't you just switch from List (equivalent of Java's ArrayList to highlight that) to LinkedList? LinkedList takes O(1) to delete a specific element, but O(n) to delete by index

Upvotes: 2

Related Questions