How to quickly filter objects that match the date range

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; } } 

Then i could

 IList<Restricton> restrictions; 

and then search for restrictions applied on a specific day

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

Problem

I believe that using IList<T> not the best option, because I will fulfill many requests for these restrictions, and every time I call the LINQ .Where method, the whole collection will be enumerated and filtered.

From SQL knowledge, I know that table scans are always worse than index scans, so I would like to apply the same logic here. Instead of listing the entire collection every time I prefer to filter in a more reasonable way.

Question

What would be better ( faster ) to list my limitations so that my algorithm does not re-read them every time I would like to filter out a few?

I was thinking about IDictionary<K,V> , but still it was necessary to scan them all, because my restrictions were not set per day, but rather in the daily range.

What would you suggest?

Answer 1

Consider ordering the list on From - then you can quickly perform a binary search to find a subset of the restrictions that can be applied in terms of From .

You may also need a second copy of the list, ordered by To - and again you can perform a binary search to find a subset of the restrictions that may apply in terms of To . In both lists, you can perform both binary searches and work, which set is smaller, and consider only this set.

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

Answer 2

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

In the first list, the From property should be sorted, and the hash in the second list, sorted by the To property. This will be similar to what the database does.

Sorted Lists in .Net

.Net has a class that allows you to use both the key and SortedList positional access, which you can use to achieve what you want.

You can use a constructor that accepts IComparer , which you can use to specify how the SortedList should compare your Restriction class. You will need to encode two IComparers comparing the From property and another comparing the To property.

Answer 3

If you have a lot of queries and not many inserts, you can do the following: Create two sorted lists of your objects, one of which is sorted by fromDate other by toDate . Then you can quickly search the sorted lists to search for each list, a set of valid results (in the first list, you request records with fromDate <= searchDate , and in the second list, you request toDate >= searchDate ). Then attach the results to the results to get the results.

Answer 4

A common solution to this problem is to implement separation; it is implemented in database environments to reduce search space. The only caveat is that your collection cannot be filtered by other criteria, or you will need to create an index.

In an exemplary implementation, a set of lists may be used that contain specific date ranges (by month, year, etc.). When you perform the insertions, you define the correct list and place your item in this list. When you do a search, you can easily identify the correct list or set of lists, and then only scan on those lists.

However, you should also consider this - how many elements will you deal with? Scanning the entire list becomes a serious problem when the number of items is very large. Optimizing this problem would be premature if you were not dealing with excessive amounts of data.