CODEWITHSUNDEEP
c#.netgenerics
jon37
jon37

Reputation: 1379

Generic list FindAll() vs. foreach

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

Upvotes: 32

Views: 99165

Answers (8)

casperOne
casperOne

Reputation: 74530

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.

Upvotes: 11

William Niu
William Niu

Reputation: 15853

Unless the C# team has improved the performance for LINQ and FindAll, the following article seems to suggest that for and foreach would outperform LINQ and FindAll on object enumeration: LINQ on Objects Performance.

This artilce was dated back to March 2009, just before this post originally asked.

Upvotes: 0

Egil Hansen
Egil Hansen

Reputation: 15598

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

Upvotes: 49

MRFerocius
MRFerocius

Reputation: 5629

Im with the Lambdas

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

Upvotes: 2

olli-MSFT
olli-MSFT

Reputation: 2546

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

Upvotes: 3

matt_dev
matt_dev

Reputation: 5236

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.

Upvotes: 6

Daniel Pratt
Daniel Pratt

Reputation: 12077

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

Upvotes: 3

Reed Copsey
Reed Copsey

Reputation: 564413

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.

Upvotes: 5

Related Questions