Hello Rick,
I have a large list of objects where each object has a unique
(non-overlapping) date range. The list is sorted chronologically. What is
the most efficient way to search this list for a single object that spans
a specified date?
My suggestion below... you mention that the list is sorted
chronologically. I don't think that information is of any use here, as
long as you don't have any good information about the distribution of the
elements in the list, or the lengths of the spans covered by a typical
element. Of course you could implement an algorithm that looks at a first
element and tries to heuristically guess where the element you're looking
for may be in the list - but without knowing the total range of elements,
the number, the distribution and the lengths of the spans, I find it very
hard to say whether the algorithm would be any more efficient than the
basic one below.
If you want efficiency without having good estimates of these details,
maybe you should organize your data in a different way - using
dictionaries for certain ranges of data, for instance. Once more it's hard
to say what that structure should best look like, without knowing details
about the data you're expecting.
And finally, don't forget: it's usually better to write a reasonably good
algorithm and to optimize it only when it proves to be a problem.
[TestFixture]
public class Tests {
[Test]
public void Test( ) {
List<ClassValidWithinRange> list = new List<ClassValidWithinRange>(new
ClassValidWithinRange[] {
new ClassValidWithinRange(new DateTime(2007, 1, 1), new DateTime(2007,
1,15)),
new ClassValidWithinRange(new DateTime(2007, 1, 16), new DateTime(2007,
1,31)),
new ClassValidWithinRange(new DateTime(2007, 2, 1), new DateTime(2007,
2,28))
});
ClassValidWithinRange checkVal = new ClassValidWithinRange(new
DateTime(2007, 3, 1), new DateTime(2007, 3, 31));
list.Add(checkVal);
ClassValidWithinRange foundVal = list.Find(delegate(ClassValidWithinRange
entry) {
return entry.IsValidOn(new DateTime(2007, 3, 15));
});
Assert.AreEqual(checkVal, foundVal);
}
}
public class ClassValidWithinRange {
public ClassValidWithinRange(DateTime from, DateTime to) {
this.from = from;
this.to = to;
}
public bool IsValidOn(DateTime date) {
// Implement with your choice of <, <=, > and >=
return from < date && to > date;
}
private DateTime from;
public DateTime From {
get {
return from;
}
set {
from = value;
}
}
private DateTime to;
public DateTime To {
get {
return to;
}
set {
to = value;
}
}
}
Oliver Sturm
