CODEWITHSUNDEEP
javaperformancesearch
TomVW
TomVW

Reputation: 1580

Efficiently search a list of consecutive date periods

I have a structure which contains consecutive time periods (without overlap) and a certain value. 

class Record {
    private TimeWindow timeWindow;
    private String value;
}

interface TimeWindow {
    LocalDate getBeginDate();

    LocalDate getEndDate(); //Can be null
}

My goal is to implement a function which takes a date and figures out the value. A naive implementation could be to loop through all records until the date matches the window.

class RecordHistory {
    private List<Record> history;

    public String getValueForDate(LocalDate date) {
        for (Record record : history) {
            if (record.dateMatchesWindow(date)){
                return record.getValue();
            }
        }

        return null; //or something similar
    }
}

class Record {

    private TimeWindow timeWindow;
    private String value;

    public boolean dateMatchesWindow(LocalDate subject) {
        return !subject.isBefore(timeWindow.getBeginDate()) && (timeWindow.getEndDate() == null || !subject.isAfter(timeWindow.getEndDate()));
    }

    public String getValue(){
        return value;
    }
}

The origin of these values are from database queries (no chance to change the structure of the tables). The list of Records could be small or huge, and the dates vary from the start of the history until the end. However, the same date will not be calculated twice for the same RecordHistory. There will be multiple RecordHistory objects, the values represent different attributes.

Is there an efficient way to search this structure?

Upvotes: 3

Views: 176

Answers (1)

tobias_k
tobias_k

Reputation: 82929

You can use binary search to get the matching Record (if such a record exists) in O(logn) time.

Java already has data structure that do that for you, e.g. the TreeMap. You can map every Record to its starting time, then get the floorEntry for a given time, and see whether it's a match.

// create map (done only once, of course)
TreeMap<LocalDate, Record> records = new TreeMap<>();
for (Record r : recordList) {
    records.put(r.getTimeWindow().getBeginDate(), r);
}

// find record for a given date
public String getValueForDate(LocalDate date) {
    Record floor = records.floorEntry(date).getValue();
    if (floor.dateMatchesWindow(date)) {
        return r;
    }
    return null;
}

If the entries are non-overlapping, and if the floor entry is not a match, than no other entry will be.

Upvotes: 1

Related Questions