Reputation: 120450
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
Upvotes: 2
Views: 200
Reputation: 144112
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.
Upvotes: 4
Reputation: 1500465
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 :)
Upvotes: 3