471,570 Members | 940 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

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

.NET Lookup Algorithm: Which is fastest?

I have a list of DateTime objects stored in a collection:

SortedList<DateTime,Object> MyDates=new SortedList<DateTime,Object>();

The dates, which can be accessed via MyDates.Keys, are stored in ascending
order. What is the fastest way to find the MAXIMUM date within 'MyDates'
which is LESS THAN or EQUAL to 12/30/05?

MyDates.ContainsKey() will tell me if the 12/30/05 exists in the list. If,
however, 12/30/05 does NOT exist in the list but 12/29/05 DOES exist in the
list, I'd like 12/29/05 to be returned.

The brute force method of iterating through the entire MyDates.Keys
collection will work of course, but this method strikes me as inefficient
since it's not taking advantage of the fact that the items are in fact
ordered.

The other idea that I came up with is to start looking in the middle of the
list and gradually narrow my search area based upon each 'hit'.

What's the best way to approach this problem? Is there an instance method
that I'm overlooking ?

Dave

Dec 30 '05 #1
2 1715
Dave,

The way I would handle this is to use a modified binary search
algorithm.

You hinted on it in your email, so you kind of know already what you
have to do. Basically, you have a sorted array with N elements. You start
at element N/2 and see if it is a match. If not, and the value you are
looking for is less than the element at N/2, you find the middle point of 0
and N/2, and then continue, over and over.

Fortunately, this is implemented for you in the static BinarySearch
algorithm on the Array class. Additionally, if the value you are looking
for is not found, it will return the bitwise compliment of the index of the
first element greater than your value.

All you have to do is take your sorted keys and then run them through
the BinarySearch method, and it should give you what you want.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"The One We Call 'Dave'" <gh****@englewood.com> wrote in message
news:G8******************************@giganews.com ...
I have a list of DateTime objects stored in a collection:

SortedList<DateTime,Object> MyDates=new SortedList<DateTime,Object>();

The dates, which can be accessed via MyDates.Keys, are stored in ascending
order. What is the fastest way to find the MAXIMUM date within 'MyDates'
which is LESS THAN or EQUAL to 12/30/05?

MyDates.ContainsKey() will tell me if the 12/30/05 exists in the list. If,
however, 12/30/05 does NOT exist in the list but 12/29/05 DOES exist in
the list, I'd like 12/29/05 to be returned.

The brute force method of iterating through the entire MyDates.Keys
collection will work of course, but this method strikes me as inefficient
since it's not taking advantage of the fact that the items are in fact
ordered.

The other idea that I came up with is to start looking in the middle of
the list and gradually narrow my search area based upon each 'hit'.

What's the best way to approach this problem? Is there an instance method
that I'm overlooking ?

Dave

Dec 30 '05 #2
Beautiful, thanks!

"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote in
message news:u9**************@TK2MSFTNGP10.phx.gbl...
Dave,

The way I would handle this is to use a modified binary search
algorithm.

You hinted on it in your email, so you kind of know already what you
have to do. Basically, you have a sorted array with N elements. You
start at element N/2 and see if it is a match. If not, and the value you
are looking for is less than the element at N/2, you find the middle point
of 0 and N/2, and then continue, over and over.

Fortunately, this is implemented for you in the static BinarySearch
algorithm on the Array class. Additionally, if the value you are looking
for is not found, it will return the bitwise compliment of the index of
the first element greater than your value.

All you have to do is take your sorted keys and then run them through
the BinarySearch method, and it should give you what you want.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"The One We Call 'Dave'" <gh****@englewood.com> wrote in message
news:G8******************************@giganews.com ...
I have a list of DateTime objects stored in a collection:

SortedList<DateTime,Object> MyDates=new SortedList<DateTime,Object>();

The dates, which can be accessed via MyDates.Keys, are stored in
ascending order. What is the fastest way to find the MAXIMUM date within
'MyDates' which is LESS THAN or EQUAL to 12/30/05?

MyDates.ContainsKey() will tell me if the 12/30/05 exists in the list.
If, however, 12/30/05 does NOT exist in the list but 12/29/05 DOES exist
in the list, I'd like 12/29/05 to be returned.

The brute force method of iterating through the entire MyDates.Keys
collection will work of course, but this method strikes me as inefficient
since it's not taking advantage of the fact that the items are in fact
ordered.

The other idea that I came up with is to start looking in the middle of
the list and gradually narrow my search area based upon each 'hit'.

What's the best way to approach this problem? Is there an instance method
that I'm overlooking ?

Dave


Dec 30 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Neal D. Becker | last post: by
3 posts views Thread by Richard Cavell | last post: by
2 posts views Thread by Peter Schmitz | last post: by
2 posts views Thread by The One We Call 'Dave' | last post: by
reply views Thread by XIAOLAOHU | last post: by
reply views Thread by leo001 | last post: by
reply views Thread by lumer26 | 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.