Are LINQ Query Expressions Optimized?

Question

Does LINQ do any optimization by sorting/converting data structures?

i.e.

Does LINQ iterate in this code, or is there any type of sorting/conversion done on the data to optimize the find operation?

var list = new List<IdCard> {new IdCard(){Name = "a", Number = 1}, new IdCard() { Name = "b", Number = 2 } };

var idA = list.FirstOrDefault(id => id.Name == "a");
var idB = list.FirstOrDefault(id => id.Name == "b");

I'm trying to understand if my LINQ code is directly translated to an iterative approach. If it is, then it would be better for the above code to use a dictionary lookup (given the case there were to be many look-ups) instead of relying on LINQ, right?

You can see what FirstOrDefault method does behind the curtain with hovering over the method and press f12 in Visual Studio. You can then check weather your approach would be efficient. But to get rid of multiple lookups you could use where and contains and you can pass the list of ids to the contains method. — Gregor Ojstersek, Aug 01 '18 at 21:29

Servy · Answer 1 · 2018-08-01T21:32:58.433

Does LINQ do any optimization by sorting/converting data structures?

Yes. There are all sorts of optimizations that take place throughout various LINQ methods.

Does LINQ iterate in this code

Yes.

is there any type of sorting/conversion done on the data to optimize the find operation?

No. The work spent constructing an entirely new data structure, in some sorted or hashed manner, would be more work than just iterating the sequence until you find the first item. Creating a collection in the LINQ implementation would not only be more processing work per item (as you're not only executing the predicate, but also whatever work that collection needs to do to store it for later), and using way more memory by storing the items for longer, but you can't quit as soon as you find the match, the way you could with a simple iteration.

then it would be better for the above code to use a dictionary lookup (given the case there were to be many look-ups) instead of relying on LINQ, right?

Yes, that code would be better off if you simply construct the collection using a type that natively provides operations that most effectively do what you want to perform on that collection (in this case, a collection that optimzies searching speed based on a key, so either a dictionary or sorted dictionary), rather than using an improper collection type and using LINQ methods.

Using LINQ is useful when the best algorithm for finding what you want for whatever collection you have (or can have, if you can control what collection you use) is the same as the algorithm you'd use for any arbitrary sequence. That's true in a lot of cases. This isn't one of those cases.

score 0 · Accepted Answer · answered Aug 02 '18 at 18:01

Thank you for your answers! They are very informative.

It looks like the answer for this query is really that some LINQ code may be optimized, and the best way to check is to simply look at the source.

Please correct me if I'm wrong, but the code appears to be available here:

https://github.com/Microsoft/referencesource/blob/master/System.Core/System/Linq/Enumerable.cs

Slai · Answer 3 · 2018-08-01T22:29:34.493

-1

No, all System.Linq extensions with predicate parameter enumerate the source collection, and don't modify or optimize the source collection. Some cases such as OrderBy, GroupBy, and Intersect use local collection to prevent enumerating the source more than once.

Lookup (it's similar to Dictionary<K, List<V>>) can be used as an alternative to Dictionary :

var list = new List<IdCard> {new IdCard(){Name = "a", Number = 1}, new IdCard() { Name = "b", Number = 2 } };
var lookup = list.ToLookup(c => c.Name);

var idA = lookup["a"].FirstOrDefault();
var idB = lookup["b"].FirstOrDefault();

edited Aug 01 '18 at 22:29

answered Aug 01 '18 at 21:55

Slai

22,144
5
45
53

A `Lookup` is designed to have a *sequence* of values associated with any given key. That doesn't appear to be the case here. If you want to get a value out of a dictionary when you aren't sure if it's there you can simply use `TryGetValue`. – Servy Aug 01 '18 at 21:59
This also doesn't actually answer the question in the OP. They weren't asking how to use different collection, instead of a LINQ operation, to more efficiently do these queries. They asked what LINQ does, and if they *need* to write the code to use a different collection themselves. – Servy Aug 01 '18 at 22:00

Are LINQ Query Expressions Optimized?

3 Answers3