Here's an example of an interpolated search... there might be easier ways,
but it appears to work very well if the data is approximately linear (i.e.
the keys are coming in at a fairly regular spacing - they don't have to be
exactly spaced).
Note that it doesn't recurse - it takes a stab using interpolation and then
walks the rest of the way from there. My reasoning is: if the first guess is
fairly close, then we haven't got far to go anyway; if the first guess is
wrong, then it means that the list is wildly non-linear, so there is no
reason to suspect that another interpolation will be any better - may as
well just treck...
You wouldn't keep the [On]Performance event/method in production code - this
is just to prove that it hasn't had to walk very far, even for long lists.
With neatly spaced data like above, I get "1" for a value that is an exact
match (i.e. we jumped to the item on our first guess) and "2" otherwise
(meaning it had to check a second value). Not bad.
using System;
using System.Collections.Generic;
static class Program
{
static void Main()
{
LinearList<DateTime, Foo> list = new LinearList<DateTime,
Foo>(Interpolate);
list.Performance += new
EventHandler<CounterEventArgs>(list_Performance);
// lots of sample data...
// note that it is *roughly* linear (doesn't have to be exact)
Random rand = new Random(987654);
DateTime lookForThis = DateTime.MaxValue;
for (int days = -350; days < 350; days++)
{
DateTime key = DateTime.Today.AddDays(days).
AddMinutes(rand.Next(-600, 600));
if (days == 100)
{
lookForThis = key;
}
list.Add(key, new Foo { A = days });
}
Foo foo1 = list.FindNearestValue(DateTime.Today.AddHours(-6)),
foo2 = list.FindNearestValue(DateTime.Today.AddHours(6)),
foo3 = list.FindNearestValue(DateTime.Today.AddHours(18)),
foo4 = list.FindNearestValue(lookForThis);
}
static void list_Performance(object sender, CounterEventArgs e)
{
Console.WriteLine("OpCount: {0}", e.Counter);
}
public static double Interpolate(DateTime min, DateTime value, DateTime
max)
{
long minTicks = min.Ticks,
range = max.Ticks - minTicks;
double offset = value.Ticks - minTicks;
return range == 0 ? 0 : offset / range;
}
}
class Foo
{
public int A { get; set; }
public int B { get; set; }
private readonly Bar c = new Bar();
public Bar C { get { return c; } }
}
class Bar
{
public int X { get; set; }
public int Y { get; set; }
}
public class LinearList<TKey, TValue> : SortedList<TKey, TValue>
{
private readonly Func<TKey, TKey, TKey, double> interpolation;
public LinearList(Func<TKey, TKey, TKey, double> interpolation) :
this(interpolation, null) { }
public LinearList(Func<TKey, TKey, TKey, double> interpolation,
IComparer<TKey> comparer)
: base(comparer ?? Comparer<TKey>.Default)
{
if (interpolation == null) throw new
ArgumentNullException("interpolation");
this.interpolation = interpolation;
}
private int ThisOrNext(int index, TKey value)
{
TKey left = Keys[index];
if (Comparer.Compare(value, left) <= 0) return index;
TKey right = Keys[index + 1];
if (Comparer.Compare(value, right) >= 0) return index + 1;
double factor = interpolation(left, value, right);
if (factor < 0 || factor > 1)
{
throw new InvalidOperationException("Interpolation expected in
interval [0,1] since value is in range");
}
return factor <= 0.5 ? index : index + 1;
}
public TValue FindNearestValue(TKey key)
{
int index = FindNearestIndex(key);
return index < 0 ? default(TValue) : this.Values[index];
}
public int FindNearestIndex(TKey key)
{
int count = Count, opCount = 1;
try
{
switch (count)
{ // trivial cases
case 0: return -1;
case 1: return 0;
case 2: return ThisOrNext(0, key);
}
TKey lowerBound = this.Keys[0], upperBound = this.Keys[count -
1];
IComparer<TKey> comparer = Comparer;
// check if it goes outside [or is on boundary of] our range
(return min/max)
if (comparer.Compare(key, lowerBound) <= 0) return 0;
if (comparer.Compare(key, upperBound) >= 0) return count - 1;
double factor = interpolation(lowerBound, key, upperBound);
int testIndex = (int)Math.Round((count - 1) * factor),
compare = comparer.Compare(key, this.Keys[testIndex]);
if (compare == 0)
{
return testIndex; // hit!
}
else if (compare < 0)
{
// we guessed too high... look lower
for (int i = testIndex - 1; i >= 0; i--)
{
opCount++;
compare = comparer.Compare(key, this.Keys);
if (compare == 0) return i; // hit!
if (compare > 0)
{
return ThisOrNext(i, key);
}
}
return ThisOrNext(0, key);
}
else // compare > 0
{
// we guessed too low... look higher
for (int i = testIndex + 1; i < count - 1; i++)
{
opCount++;
compare = comparer.Compare(key, this.Keys);
if (compare == 0) return i; // hit!
if (compare < 0)
{
return ThisOrNext(i - 1, key);
}
}
return ThisOrNext(count - 2, key);
}
}
catch
{
opCount = 0;
throw;
}
finally
{
if (opCount > 0) OnPerformance(opCount);
}
}
// give an indication of how good/bad our search was...
public event EventHandler<CounterEventArgs> Performance;
protected virtual void OnPerformance(int opCount) {
if (Performance != null) Performance(this, new
CounterEventArgs(opCount));
}
}
public sealed class CounterEventArgs : EventArgs {
private readonly int counter;
public int Counter {get {return counter;}}
public CounterEventArgs(int counter) {
this.counter = counter;
}
}
