How does LINQ exploit sorted collections?

[WebSnozz]

Some collections are such that efficient search algorithms work on them
such as binary search if the collection is a type which is sorted.

I'm wondering how LINQ searches these collections and if it takes
advantage of the fact that some collections are sorted?

We were speculating that the standard .net 2.0 collections might
implement the IQueryable interface for those collections where there
are more efficient search algorithms.

What would seem awful is if it searched through all objects only by
iteration, which would always be a sequential search.

I did try a Google but didn't come up with anything relevant, so please
don't flame me if you found something. Just because my choice of
keywords may have been bad is no reason to get angry.

Thanks.

 

[Dave Sexton]

Hi,

I think LINQ just iterates over the collection. Doesn't it just use
IEnumerable<T> (or ICollection<T> if certain methods exist)? - though I
could be wrong.

 

[Dave Sexton]

Hi,

On second thought, what's to stop a LINQ expression from containing an
explicit call to BinarySearch, for example?

 

[WebSnozz]

What would stop it I think(I say I think cause I don't know much about
LINQ) is that only certain data structures would support BinarySearch,
and LINQ working on any structure that implements IQueryable means that
isn't guaranteed. All LINQ sees(I think) is what is available in
IQueryable and IEnumerable. So it wouldn't know to call BinarySearch,
cause it doesn't know it exists, nor should it. But it would seem
there should be some mechanism that allows the developer of the
collection to specify how the collection is searched.

How much control does the developer have over how IQueryable operates?
If you can create a concrete implementation of IQueryable for the
collection, then inside IQueryable you could write the query executing
code such that it exploits the advantages of the data structure when
doing searches. You'd probably have to evaluate the query being run to
some extent in order to know how to perform the search.

I don't know anything about IQueryable though, so I'm not sure. But if
it is true that IQueryable can be implemented in that way, then the
next question is, does Microsoft write efficient IQueryable
implementations for all of their collections provided through the .net
framework, or do they just iterate through the collection. I guess
only MS staff or someone delving into the MS assemblies would be able
to determine that.

I guess I could read up a bunch on IQueryable and see if that was
possible. But still that wouldn't answer the above regarding how
standard collections implement IQueryable.

Thanks for the replies.

 

[Dave Sexton]

Hi,

Yes, that was ignorant. It's been a while since I played around with LINQ

 

[Barry Kelly]

Some collections are such that efficient search algorithms work on them
such as binary search if the collection is a type which is sorted.

I'm wondering how LINQ searches these collections and if it takes
advantage of the fact that some collections are sorted?

They would have to implement the appropriate methods and decompose the
predicate to see if it consists only of operators (==, <, etc.) that
work well with the internal structure.

We were speculating that the standard .net 2.0 collections might
implement the IQueryable interface for those collections where there
are more efficient search algorithms.

I can see a possible case for some collections implementing
Where<T>(Expression<Func<T,bool>> predicate) and friends (OrderBy,
OrderByDescending), but I'm not sure if the gain would be worth the cost
of implementing them.

We'll know more when it's closer to release.

-- Barry