Generic list FindAll() vs. foreach

Question

I'm looking through a generic list to find items based on a certain parameter.

In General, what would be the best and fastest implementation?
1. Looping through each item in the list and saving each match to a new list and returning that

foreach(string s in list)
{ 
    if(s == "match")
    {
       newList.Add(s);
    }
} 

return newList;

Or
2. Using the FindAll method and passing it a delegate.

newList = list.FindAll(delegate(string s){return s == "match";});

Don't they both run in ~ O(N)? What would be the best practice here?

Regards, Jonathan

Answer 1

You should definitely use the FindAll method, or the equivalent LINQ method. Also, consider using the more concise lambda instead of your delegate if you can (requires C# 3.0):

var list = new List<string>();
var newList = list.FindAll(s => s.Equals("match"));

Answer 2

I would use the FindAll method in this case, as it is more concise, and IMO, has easier readability.

You are right that they are pretty much going to both perform in O(N) time, although the foreach statement should be slightly faster given it doesn't have to perform a delegate invocation (delegates incur a slight overhead as opposed to directly calling methods).

I have to stress how insignificant this difference is, it's more than likely never going to make a difference unless you are doing a massive number of operations on a massive list.

As always, test to see where the bottlenecks are and act appropriately.

Answer 3

Jonathan,

A good answer you can find to this is in chapter 5 (performance considerations) of Linq To Action.

They measure a for each search that executes about 50 times and that comes up with foreach = 68ms per cycle / List.FindAll = 62ms per cycle. Really, it would probably be in your interest to just create a test and see for yourself.