Эффективно искать список последовательных периодов дат

Question

У меня есть структура, которая содержит последовательные периоды времени (без перекрытия) и определенное значение.

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

interface TimeWindow {
    LocalDate getBeginDate();

    LocalDate getEndDate(); //Can be null
}

Моя цель - реализовать функцию, которая берет дату и вычисляет значение. Наивной реализацией может быть цикл всех записей, пока дата не совпадет с окном.

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

Источником этих значений являются запросы к базе данных (нет возможности изменить структуру таблиц). Список записей может быть небольшим или огромным, а даты варьируются от начала истории до конца. Однако одна и та же дата не будет рассчитываться дважды для одной и той же RecordHistory. Будет несколько объектов RecordHistory, значения представляют разные атрибуты.

Есть ли эффективный способ поиска этой структуры?

Answer 1

Вы можете использовать двоичный поиск , чтобы получить соответствующий Record (если такая запись существует) за время O (logn).

В Java уже есть структура данных, которая сделает это за вас, например. TreeMap. Вы можете сопоставить каждый Record с его начальным временем, затем получить floorEntry за заданное время и посмотреть, соответствует ли это.

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

Если записи не перекрываются, и если запись на этаже не соответствует, то никакая другая запись не будет.