1

I have a list of User objects, and I have to remove ONE item from the list with a specific UserID.

This method has to be as fast as possible, currently I am looping through each item and checking if the ID matches the UserID, if not, then I add the row to a my filteredList collection.

List allItems = GetItems();

for(int x = 0; x < allItems.Count; x++)
{
    if(specialUserID == allItems[x].ID)
        continue;
    else
        filteredItems.Add( allItems[x] );
}

11 Answers 11

8

If it really has to be as fast as possible, use a different data structure. List isn't known for efficiency of deletion. How about a Dictionary that maps ID to User?

4

Well, if you want to create a new collection to leave the original untouched, you have to loop through all the items.

Create the new list with the right capacity from the start, that minimises allocations.

Your program logic with the continue seems a bit backwards... just use the != operator instead of the == operator:

List<User> allItems = GetItems();

List<User> filteredItems = new List<User>(allItems.Count - 1);

foreach (User u in allItems) {
   if(u.ID != specialUserID) {
      filteredItems.Add(u);
   }
}

If you want to change the original collection instead of creating a new, storing the items in a Dictionary<int, User> would be the fastest option. Both locating the item and removing it are close to O(1) operations, so that would make the whole operation close to an O(1) operation instead of an O(n) operation.

1
  • +1 for recommendation of dictionary and creating a new list instead of removing from existing. clever.
    – Steve
    Aug 29, 2009 at 16:46
3

Use a hashtable. Lookup time is O(1) for everything assuming a good hash algorithm with minimal collision potential. I would recommend something that implements IDictionary

2

If you must transfer from one list to another here is the fasted result I've found:

        var filtered = new List<SomeClass>(allItems);
        for (int i = 0; i < filtered.Count; i++)
            if (filtered[i].id == 9999)
                filtered.RemoveAt(i);

I tried comparing your method, the method above, and a linq "where" statement:

            var allItems = new List<SomeClass>();
        for (int i = 0; i < 10000000; i++)
            allItems.Add(new SomeClass() { id = i });

        Console.WriteLine("Tests Started");
        var timer = new Stopwatch();

        timer.Start();
        var filtered = new List<SomeClass>();
        foreach (var item in allItems)
            if (item.id != 9999)
                filtered.Add(item);
        var y = filtered.Last();
        timer.Stop();
        Console.WriteLine("Transfer to filtered list: {0}", timer.Elapsed.TotalMilliseconds);

        timer.Reset();
        timer.Start();
        filtered = new List<SomeClass>(allItems);
        for (int i = 0; i < filtered.Count; i++)
            if (filtered[i].id == 9999)
                filtered.RemoveAt(i);
        var s = filtered.Last();
        timer.Stop();
        Console.WriteLine("Removal from filtered list: {0}", timer.Elapsed.TotalMilliseconds);

        timer.Reset();
        timer.Start();
        var linqresults = allItems.Where(x => (x.id != 9999));
        var m = linqresults.Last();
        timer.Stop();
        Console.WriteLine("linq list: {0}", timer.Elapsed.TotalMilliseconds);

The results were as follows: Tests Started

Transfer to filtered list: 610.5473

Removal from filtered list: 207.5675

linq list: 379.4382

using the "Add(someCollection)" and using a ".RemoveAt" was a good deal faster.

Also, subsequent .RemoveAt calls are pretty cheap.

1

I know it's not the fastest, but what about generic list and remove()? (msdn). Anybody knows how it performs compared to eg. the example in the question?

4
  • Remove() requires that you have the object you want to remove. If the question is to be believed, he has the ID of the user he wants removed, but not the object of type (well, presumably of type) "User" that he actually wants removed from the list.
    – lance
    Aug 28, 2009 at 21:45
  • Yes, a generic list would be faster. Aug 28, 2009 at 21:45
  • @Ezombort, @Gary: I'm guessing that the OP is already using List<T> despite there being no <T> in the declaration code in the question. If they were using ArrayList or some other non-generic collection then they'd need to cast each element to a specific type before checking its ID property, and they're not!
    – LukeH
    Aug 29, 2009 at 0:09
  • @Luke: Ah, that's true. And the for loop is much faster than foreach isn't it?
    – Ezombort
    Aug 29, 2009 at 9:14
1

Here's a thought, how about you don't remove it per se. What I mean is something like this:

public static IEnumerable<T> LoopWithExclusion<T>(this IEnumerable<T> list, Func<T,bool> excludePredicate)
{
   foreach(var item in list)
   {
      if(excludePredicate(item))
      {
         continue;
      }

      yield return item;
   }
}

The point being, whenever you need a "filtered" list, just call this extension method, which loops through the original list, returns all of the items, EXCEPT the ones you don't want.

Something like this:

List<User> users = GetUsers();

//later in the code when you need the filtered list:

foreach(var user in users.LoopWithExclusion(u => u.Id == myIdToExclude))
{
   //do what you gotta do
}
1

Assuming the count of the list is even, I would :

(a) get a list of the number of processors

(b) Divide your list into equal chunks for each processors

(c) spawn a thread for each processor with these data chunks, with the terminating condition being if the predicate is found to return a boolean flag.

2
  • 2
    This is exactly what the Parallel.For does in .net 4.0. Using this would save you a lot of hassle.
    – Mez
    Aug 29, 2009 at 0:20
  • All very well if you have .net 4.0!
    – Darknight
    Aug 29, 2009 at 18:20
1
public static void RemoveSingle<T>(this List<T> items, Predicate<T> match)
{
    int i = -1;
    while (i < items.Count && !match(items[++i])) ;
    if (i < items.Count)
    {
        items[i] = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
    }
}
0

I cannot understand why the most easy, straight-forward and obvious solution (also the fastest among the List-based ones) wasn't given by anyone. This code removes ONE item with a matching ID.

for(int i = 0; i < items.Count; i++) {
    if(items[i].ID == specialUserID) {
        items.RemoveAt[i];
        break;
    }
}
1
  • Because it's simply not fast Dec 5, 2020 at 11:47
0

If you have a list and you want to mutate it in place to remove an item matching a condition the following is faster than any of the alternatives posted so far:

        for (int i = allItems.Count - 1; i >= 0; i--)
            if (allItems[i].id == 9999)
                allItems.RemoveAt(i);

A Dictionary may be faster for some uses, but don't discount a List. For small collections, it will likely be faster and for large collections, it may save memory which may, in turn make you application faster overall. Profiling is the only way to determine which is faster in a real application.

-1

Here is some code that is efficient if you have hundreds or thousands of items:

List allItems = GetItems();
//Choose the correct loop here

if((x % 5) == 0 && (X >= 5))
{
     for(int x = 0; x < allItems.Count; x = x + 5)
     {
         if(specialUserID != allItems[x].ID)
             filteredItems.Add( allItems[x] );
         if(specialUserID != allItems[x+1].ID)
             filteredItems.Add( allItems[x+1] );
         if(specialUserID != allItems[x+2].ID)
             filteredItems.Add( allItems[x+2] );
         if(specialUserID != allItems[x+3].ID)
             filteredItems.Add( allItems[x+3] );
         if(specialUserID != allItems[x+4].ID)
             filteredItems.Add( allItems[x+4] );
      }
 }

Start testing if the size of the loop is divisible by the largest number to the smallest number. if you want 10 if statements in the loop then test if the size of the list is bigger then ten and divisible by ten then go down from there. For example if you have 99 items --- you can use 9 if statements in the loop. The loop will iterate 11 times instead of 99 times

"if" statements are cheap and fast

2
  • 1
    Can you explain this one some more?
    – David
    Aug 29, 2009 at 1:55
  • It is highly unlikely that unrolling the loop in this way will provide any measurable benefit. By making a loop larger you risk making it not fit in the various on-chip caches.
    – Ian Mercer
    Mar 20, 2017 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.