How to fast filter objects that satisfy date range condition

Question

I have a large collection of objects

public class Restriction
{
    // which days this restriction applies to
    public DateTime From { get; set; }
    public DateTime To { get; set; }

    // valid applicable restriction range
    public int Minimum { get; set; }
    public int Maximum { get; set; }
}

I could then have

IList<Restricton> restrictions;

and then searching for restrictions that are applied on a particular day

restrictions.Where(r => day >= r.From && day <= r.To);

Issue

I suppose using IList<T> isn't the best option because I will be doing a lot of searches over these restrictions and every time I would call LINQ method .Where the whole collection would be enumerated and filtered.

From the SQL knowledge I have I know that table scan is always worse than an index scan so I would like to apply a similar logic here. Instead of enumerating the whole collection every time I would rather filter in a more intelligent way.

Question

What would be a better (faster) way to enumerate my restrictions so my algorithm wouldn't be enumerating over them every time I'd want to filter out a few?

I was thinking of IDictionary<K,V> but it would still need to scan them all because my restrictions are not set per day, but rather per day range.

What would you suggest?

Answer 1

Consider ordering the list by From - then you can quickly perform a binary search to find the subset of restrictions which might be applicable in terms of From.

You might also want to have a second copy of the list ordered by To - then again, you can perform a binary search to find the subset of restrictions which my be applicable in terms of To. With both lists, you could perform both binary searches, and work out which set is smaller, and only consider that set.

There may well be a much better alternative, but that's a good start, and I don't quite have the mental energy to work out anything better right now :(

Answer 2

What you need are two sorted lists to simulate what databases do with indexes, because it is very fast to search something in a sorted list.

The first list should be sorted the From property, and the hash into the second list, sorted by the To property. This would be similar to what a database does.

Sorted Lists in .Net

.Net has a class to make both keyed and positional access called SortedList, that you can use to achieve what you want.

You can use the constructor that takes an IComparer that you can use to indicate how the SortedList should compare your Restriction class. You will need to code two IComparers, one that compares the From property, and another one that compares the To property.