Speeding up lookup of ranges of data from a collection

Question

Say I have a class

public class TimestampedTrackId
{
    private readonly int trackId;
    private readonly DateTime insertTime;
    public TimestampedTrackId(int trackId, DateTime insertTime)
    {
        this.trackId = trackId;
        this.insertTime = insertTime;
    }

    public int TrackId
    {
        get
        {
            return trackId;
        }
    }

    public DateTime InsertTime
    {
        get
        {
            return insertTime;
        }
    }
}

I have a large list of type List<TimestampedTrackId> and need to extract TimestampedTrackId instances from this list where the property InsertTime lies between a minimum and a maximum DateTime.

List<TimestampedTrackId> tracks; //Count=largeNumber
... 
tracks.Where(t=>t.InsertTime>min&&t.InsertTime<max)

A List<T> is obviously not the correct container for this task as it requires a search on every item to check if InsertTime lies between the min and max values.

So, I am assuming that part of speeding up this code would involve repackaging the list in a more suitable collection, but which collection?

Given the correct collection (which might be keyed), what query might I use to leverage maximum lookup speed?

Thanks in advance

Answer 1

Are you able to sort your list by InsertTime? If so, List<T>.BinarySearch is your friend - provide an IComparer<TimestampedTrackId> which compares by InsertTime, and BinarySearch for min and max. (You'll need to create "dummy" TimestampedTrackId objects with an InsertTime values of min and max in order to search for them.)

If BinarySearch returns a negative value, you should take the bitwise complement (using the ~ operator) to find out the index where the value would be inserted. Also remember that if multiple items can have the same InsertTime, you'll need to work backwards from the min index and forwards from the max index to make sure you get the full range. Anyway, it'll still be a lot more efficient than a linear search. It's a bit more fiddly, admittedly :)

Answer 2

A good solution might be to use a TreeMap, as that structure lends itself well to fetching a specific range of keys less than or greater than a given key.

.NET doesn't have one natively, but there's a good implementation of one here.