CODEWITHSUNDEEP
c#sorteddictionary
Thomas
Thomas

Reputation: 12107

get range of values from a sorted dictionary

I have a sorted dictionary with DateTime as the key:

myDictionary = new SortedDictionary<DateTime, float>();

I would like to implement the following function:

data[] GetRange(DateTime From, DateTime To)

The fastest way would be to get find the first / last index in the values and then get the data from a range of values

But to do this, I would need to find how I can get the index of 'From' and 'To'.

Is there a way to do this? or, is there a faster method to achieve this?

Right now I am looking at having an array for the values and having a dictionary to look up in the data array.

Upvotes: 3

Views: 2586

Answers (2)

Eric J.
Eric J.

Reputation: 150108

Given your need for high-performance, you might consider a data structure that allows a binary search for your min and max values. If SortedDictionary provided an indexer Item[int], you could use that but, alas, it does not.

You can consider something like

struct PriceAtTime
{
    public DateTime Timestamp { get; set; }
    public float Price { get; set; } // Or whatever your float represents
}

List<PriceAtTime> myData = GetTheData(); // Assumes the provided data is ordered
                                         // by timestamp.

To find the index that contains the first data point at or after your minimum timestamp:

  • Check myData[myData.Count/2]
  • Depending on the value of that element's timestamp, you either found it, or the middle element is newer than the minimum so check myData.Count/4, or it's higher so check 3*myData.Count/4. Repeat recursively until you find the right element.
  • Similar approach to find the index of the last element that doesn't exceed your max value.

SortedList<T> sounds like a promising type, but in reality, it behaves much like a sorted dictionary, especially for keyed lookups.

Note that I assume the elements in the list are magically sorted. A self-sorting data structure can be fairly expensive in a real-time performance environment. If you can obtain the data already sorted from wherever it resides, you eliminate another performance concern.

Upvotes: 1

Xipooo
Xipooo

Reputation: 1566

You could use LINQ to do this:

myDictionary.Where(d => d.Key >= from && d.Key <= to).Select(d => d.Value).ToArray();

Upvotes: 0

Related Questions