java - 有效地搜索连续日期段的列表

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

您可以使用 binary search在 O(logn) 时间内获得匹配的 Record(如果存在这样的记录)。

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

如果条目不重叠，并且楼层条目不匹配，则其他条目都不会匹配。