Is LINQ Where extension method optimized for SortedDictionary?

Question

Folks,

If I call the LINQ Where extension method, does it take advantage of the sorting in SortedDictionary or does it traverse each KVP and make the comparison? Is there an advantage to using SortedDictionary for the search-by-criteria scenario?

Thanks!

Answer 1

No, whilst LINQ methods attempt a few basic casts (ie to ICollection when a length estimate is needed), they cannot begin to cast the IEnumerable to every .net collection out there to see if they can make use of that collection's properties.

However as you know the properties of your SortedDictionary source, could you use TakeWhile or SkipWhile instead of Where?

Answer 2

As far as I can tell from examining the source code (via Reflector), no special handling is performed for SortedDictionary<TKey, TValue>.

Answer 3

That depends entirely on the behavior of SortedDictionary's enumerator implementation. Use Reflector there to see what behavior that enumerator exhibits.

Answer 4

No, the Linq query will enumerate the collection as a sequence of KeyValuePair objects and apply the predicate to each. Therefore, you won't get the benefit of the fast lookup that a SortedDictionary provides in this case.

However, you should realize that it's not really possible to use the efficient key lookup of a dictionary (sorted or otherwise) to perform this particular type of query, because the efficient key lookup will resolve to a single entry. That's because duplicate keys are not allowed in the data structure, so for a given key that can be used to do fast lookup you will only ever resolve to a single resulting value, not a sequence.

Therefore, the scenario does not really make sense.