471,089 Members | 1,768 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,089 software developers and data experts.

How does LINQ exploit sorted collections?

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.

Jan 23 '07 #1
5 2495
Hi,

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

--
Dave Sexton
http://davesexton.com/blog
http://www.codeplex.com/DocProject (Sandcastle in VS IDE)

"WebSnozz" <sh******@cs.fsu.eduwrote in message
news:11*********************@s48g2000cws.googlegro ups.com...
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.

Jan 23 '07 #2
Hi,

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

--
Dave Sexton
http://davesexton.com/blog
http://www.codeplex.com/DocProject (Sandcastle in VS IDE)

"WebSnozz" <sh******@cs.fsu.eduwrote in message
news:11*********************@s48g2000cws.googlegro ups.com...
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.

Jan 23 '07 #3
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.

On Jan 23, 5:53 pm, "Dave Sexton" <dave@jwa[remove.this]online.com>
wrote:
Hi,

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

--
Dave Sextonhttp://davesexton.com/bloghttp://www.codeplex.com/DocProject(Sandcastle in VS IDE)

"WebSnozz" <shuma...@cs.fsu.eduwrote in messagenews:11*********************@s48g2000cws.go oglegroups.com...
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.
Jan 24 '07 #4
Hi,

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

--
Dave Sexton
http://davesexton.com/blog
http://www.codeplex.com/DocProject (Sandcastle in VS IDE)

"WebSnozz" <sh******@cs.fsu.eduwrote in message
news:11**********************@l53g2000cwa.googlegr oups.com...
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.

On Jan 23, 5:53 pm, "Dave Sexton" <dave@jwa[remove.this]online.com>
wrote:
>Hi,

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

--
Dave
Sextonhttp://davesexton.com/bloghttp://www.codeplex.com/DocProject(Sandcastle
in VS IDE)

"WebSnozz" <shuma...@cs.fsu.eduwrote in
messagenews:11*********************@s48g2000cws.g ooglegroups.com...
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.

Jan 24 '07 #5
WebSnozz wrote:
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

--
http://barrkel.blogspot.com/
Jan 25 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Peter Olcott | last post: by
1 post views Thread by Bob Johnson | last post: by
5 posts views Thread by =?Utf-8?B?cmF1bGF2aQ==?= | last post: by
3 posts views Thread by Vivien Parlat | last post: by
9 posts views Thread by Cirene | last post: by
21 posts views Thread by hrishy | last post: by
4 posts views Thread by George | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.