I have a list of DateTime objects stored in a collection:
SortedList<Date Time,Object> MyDates=new SortedList<Date Time,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.Contain sKey() 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
2  1679 
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.co m
"The One We Call 'Dave'" <gh****@englewo od.com> wrote in message
news:G8******** *************** *******@giganew s.com... I have a list of DateTime objects stored in a collection:
SortedList<Date Time,Object> MyDates=new SortedList<Date Time,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.Contain sKey() 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
Beautiful, thanks!
"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard .caspershouse.c om> wrote in
message news:u9******** ******@TK2MSFTN GP10.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.co m
"The One We Call 'Dave'" <gh****@englewo od.com> wrote in message
news:G8******** *************** *******@giganew s.com...I have a list of DateTime objects stored in a collection:
SortedList<Date Time,Object> MyDates=new SortedList<Date Time,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.Contain sKey() 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
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Neal D. Becker |
last post by:
I need a fairly small lookup table, and I'm wondering which data python data
structure would be fastest. I could use a list, tuple, dictionary, numeric
array, or maybe plain python array. The table would be indexed by simple
integers and would be dense (filled).
|
by: tommazzo |
last post by:
Hi!
I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which is
the fastest?
Thanks already in advance!
|
by: PWalker |
last post by:
Hi, I have written code that I would like to optimize. I need to push it to
the limit interms of speed as the accuracy of results are proportional to
runtime.
First off, would anyone know any resources that explains how to optimize
code i.e. give some rules on c++ optimization? e.g. using memcpy to copy an
array (which i have done).
...
|
by: yee young han |
last post by:
I need a fast data structure and algorithm like below condition.
(1) this data structure contain only 10,000 data entry.
(2) data structure's one entry is like below
typedef struct _DataEntry_
{
char szInput;
char szOutput;
int iSum;
|
by: microsoft |
last post by:
I have a very "flat" doc structure like this
<root>
<one>
<two>
<three>
...
n <=100
</root>
| | |
by: Roy Gourgi |
last post by:
Hi,
I am new to C#. I have the same time scheduling program written in C++ and
it is 5 times faster than my version in C#.
Why is it so slow as I thought that C# was only a little slower than C++?
What am I doing wrong?
Here is my code:
using System;
|
by: Peter Schmitz |
last post by:
Hi again,
I just need to write the following function to search in a binary buffer for
a given pattern:
BOOL CheckBufferForPattern(BYTE *buffer,int bufferlen,BYTE *pattern, int
patternlen, BOOL casesensitive).
What's the best/fastest algorithm for a usual buffer size of 1500bytes or
so? Is there any source code available for this?
|
by: The One We Call 'Dave' |
last post by:
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?
...
|
by: pj |
last post by:
Hi,
I 'm currently writing a program that performs transliteration (i.e.,
converts greek text written using the english alphabet to "pure" greek
text using the greek alphabet) as part of my thesis. I have decided to
add the capability to convert words using some sort of lookup
algorithm as a sidekick to the "normal" conversion algorithm,...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it. ...
| | |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |
