How to find point between two keys in sorted dictionary

Question

I have a sorted dictionary that contains measured data points as key/value pairs. To determine the value for a non-measured data point I want to extrapolate the value between two known keys using a linear interpolation of their corresponding values. I understand how to calculate the non-measured data point once I have the two key/value pairs it lies between. What I don't know is how to find out which keys it lies between. Is there a more elegant way than a "for" loop (I'm thinking function/LINQ query) to figure out which two keys my data point lies between?

Answer 1

Something like this would work:

 dic.Keys.Zip(dic.Keys.Skip(1), 
              (a, b) => new { a, b })
         .Where(x => x.a <= datapoint && x.b >= datapoint)
         .FirstOrDefault();

This traverses they keys using the fact that they are ordered and compares all two keys following each other in order - since LINQ is lazy once you find the first match the traversal will stop.

Answer 2

The standard C# answers are all O(N) complexity. Sometimes you just need a small subset in a rather large sorted collection. (so you're not iterating all the keys) The standard C# collections won't help you here. And a solution is as followed: http://www.itu.dk/research/c5/ Use the IntervalHeap in the C5 collections library. This class supports a GetRange() method and will lookup the startkey with O(log N) complexity and iterate the range with O(N) complexity. Which will be definately useful for big datasets if performance is critical. e.g. Spatial Partitioning in gaming

Answer 3

Possible you're asking about following:

myDictionary.Keys.Where(w => w > start && w < end)

Answer 4

regular loop should be ok here:

IEnumerable<double> keys = ...; //ordered sequence of keys
double interpolatedKey = ...;

// I'm considering here that keys collection doesn't contain interpolatedKey

double? lowerFoundKey = null;
double? upperFoundKey = null;

foreach (double key in keys)
{
    if (key > interpolatedKey)
    {
        upperFoundKey = key;
        break;
    }
    else
        lowerFoundKey = key;
}

You can do it in C# with LINQ with shorter but less effective code:

double lowerFoundKey = key.LastOrDefault(k => k < interpolatedKey);
double upperFoundKey = key.FirstOrDefault(k => k > interpolatedKey);

In order to it efficiently with LINQ it should have a method which is called windowed in F# with parameter 2. It will return an IEnumerable of adjacent pairs in keys collection. While this function is missing in LINQ regular foreach loop should be ok.

Answer 5

I don't think there is a function on SortedDictionary that lets you find elements around the one you need faster than iterating elements. (+1 to BrokenGlass solution)

To be able to find items faster you need to switch to some other structure. I.e. SortedList provides similar functionality but allows to index its Key collection and hence you can use binary serach to find the range.