Are there any cases where LINQ.Where () will be faster than O (N)?

Question

Think the name describes my thoughts pretty well :)

I have seen a lot of people lately swearing LINQ, and although I also find it awesome, I also think you should not confuse the fact that on most (all?) IEnumerable types this performance is not so great. Am I really wrong about that? Especially the questions, where are you nesting Where () on large datasets?

Sorry if this question is a bit vague, I just want to confirm my thoughts with the fact that when using LINQ you have to be careful.

[EDIT] Just for clarification - I'm thinking of Linq for objects here :)

Answer 1

Here's a project that promises introduces indexing for LINQ2Objects. This should provide better asymptotic behavior: http://i4o.codeplex.com/

Answer 2

It depends on the supplier. For Linq to Objects, it will be O (n), but for Linq to SQL or Entities, it can ultimately use indexes to defeat it. For objects, if you need Where functionality, you probably need O (n). Linq will almost certainly have a large constant, mainly due to function calls.

Answer 3

It depends on how you use it and what you are comparing.

I have seen many implementations using foreache , which would be much faster with linq. For instance. because they forget to break or because they return too many items. The trick is that lambda expressions execute when an element is actually used. When you have First at the end, it can only lead to one call.

Therefore, when you bind Where s, if the element does not pass the first condition, it will also not be checked for the second condition. it is similar to the && operator, which does not evaluate the condition on the right side if the first is not satisfied.

We can say that it is always O (N). But N is not the number of elements in the source, but the minimum number of elements needed to create the target set. This is a pretty good optimization IMHO.