Fastest method of collection searching by DateTime

I have a Dictionary containing 10 keys, each with a list containing up to 30,000 values. The values contain a DateTime property.

I frequently need to extract a small subset of one of the keys, like a date range of 30 - 60 seconds.

Doing this is easy, but getting it t开发者_开发技巧o run fast is not so. What would be the most efficient way to query this in-memory data?

Thanks a lot.

---

Sort lists by date at the first, then find your required items by binary search (i.e k item) and return them, finding the searched item is O(log(n)) because you need find first and last index. returning them is O(K) in all It's O(K+log(n))

    IEnumerable<item> GetItems(int startIndex, int endIndex, List<item> input)
    {
        for (int i=startIndex;i<endIndex;i++)
           yield return input[i];
    }

---

1) Keep the dictionary, but use SortedList instead of a list for value of dictionaries, sorted by DateTime property

2) Implement a binary search to find the upper and lower edges in your range in the sorted list which gives you indexes.

3) Just select values in the range using Sortedlist.Values.Skip(lowerIndex).Take(upperIndex - lowerIndex)

---

In reply to Aliostad: I don't think bsearch will not work if the list of the collection is a linked list. It still takes O(n)

---

the fastest way will be to organize the data so it is indexed by the thing you want to search on. Currently you have it indexed by key, but you want to search by date. I think you would be best indexing it by date, if that is what you want to be able to search on.

I would keep 2 dictionaries, one indexed as you do now and one where the items are indexed by date. i would decide on a time frame (say 1 minute) and add each object to a list based on the minute it happens in and then add each list to the dictionary under the key of that minute. then when you want the data for a particular time frame, generate the relevant minute(s) and get the list(s) from the dictionary. This relies on you being able to know the key in the other dictionary from the objects though.