Which LINQ expression is better?

Question

I was wondering which of the following LINQ expressions is better (especially in terms of performance).

Notes:

• length of SearchKeywords is usually around 50
• length of keywords is usually around 3
• this method is called around 100,000 times

this one?

keywords.All(a => SearchKeywords.Contains(a));

or this one

keywords.Except(SearchKeywords).None();

Note: .None() is my extension method which simply returns !.Any()

Is there any better way to write this?

Regards

Answer 1

Except will be approximately a gazillion times faster because it uses a hashtable to find the set difference¹ and thus will give O(n) performance.

The Contains/All combo would have to do a naive linear search² over SearchKeywords for each element in keywords, so we are talking O(n²) performance (actually n * m, but the numbers you give are in the same range and take any excuse I can to type exponents).

Update: as expected, it's not even close unless you explicitly create a HashSet.

---

¹Unless of course SearchKeywords already is a HashSet<string>, as flq very rightly points out in a comment.

²At least if we 're talking about an IEnumerable, which uses the LINQ to objects standard implementation. An IQueryable could theoretically detect this and implement it any way it likes.

Answer 2

Not sure but I think

keywords.Except(SearchKeywords).None(); 

is faster than previous one because it may require to scan throught once for the collection of SearchKeywork.