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

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 construct 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).

Answer 2

List.FindAll is O(n) and will search the entire list.

If you want to run your own iterator with foreach, I'd recommend using the yield statement, and returning an IEnumerable if possible. This way, if you end up only needing one element of your collection, it will be quicker (since you can stop your caller without exhausting the entire collection).

Otherwise, stick to the BCL interface.

Answer 3

Any perf difference is going to be extremely minor. I would suggest FindAll for clarity, or, if possible, Enumerable.Where. I prefer using the Enumerable methods because it allows for greater flexibility in refactoring the code (you don't take a dependency on List<T>).

Answer 4

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.

Answer 5

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 == "match");

Answer 6

Yes, they both implementations are O(n). They need to look at every element in the list to find all matches. In terms of readability I would also prefer FindAll. For performance considerations have a look at LINQ in Action (Ch 5.3). If you are using C# 3.0 you could also apply a lambda expression. But that's just the icing on the cake:

var newList = aList.FindAll(s => s == "match");

Answer 7

Im with the Lambdas

List<String> newList = list.FindAll(s => s.Equals("match"));