Better data structure for retrieving data in between dates

Question

I have a class which stores a date as the key and a price as the value. My data structures stores about 5M entries. When I want to retrieve the data which are in a certain date range, I will loop through the data structure and check if the current data is within the date range.

e.g.

if (startDate >= data.date && data.date <= endDate)
   //do something

However, this is extremely inefficient. Is there a better way to do this?

Answer 1

If memory/performance is not a constraint*, you could simply use a TreeMap, which has a subMap method that allows you to filter on a time window:

TreeMap<Date, Double> data = ...;
for (Double price : data.subMap(startDate, true, endDate, true).values()) {
    //do something with price
}

*i.e. if you don't need to keep the prices as primitive doubles for example

Answer 2

• Make sure that the data is ordered by the key (i.e. by the date).
• Use binary search to find the start date
• Enumerate as long as you haven't reached the end date
• Voila

Edit: Yup, using a TreeMap automates the job pretty well. Don't know if you are allowed to change your data structure.