高效搜索连续无重叠日期时段：实现按日期匹配Record值的方案

嘿，这个场景我太熟悉了！如果你的history列表数据量不小，而且getValueByDate调用很频繁的话，朴素的遍历（O(n)时间复杂度）确实会成为性能瓶颈。结合你提到的连续无重叠时段这个关键特性，我们可以用几种更高效的方案把查询复杂度降到O(log n)。

方案一：预处理排序 + 二分查找 #

因为时段是连续且无重叠的，我们可以先把history列表按TimeWindow.getBeginDate()升序排序（只需要在初始化或者history更新时做一次，时间复杂度O(n log n)），之后每次查询用二分查找快速定位目标日期对应的Record。

实现步骤： #

public class RecordHistory {
    private List<Record> history;
    // 预处理排序后的列表，只在history变更时更新
    private List<Record> sortedHistory;

    // 假设提供一个设置history的方法，或者在构造函数中处理
    public void setHistory(List<Record> history) {
        this.history = history;
        // 按beginDate升序排序
        this.sortedHistory = new ArrayList<>(history);
        sortedHistory.sort(Comparator.comparing(r -> r.getTimeWindow().getBeginDate()));
    }

    public String getValueByDate(LocalDate date) {
        if (sortedHistory == null || sortedHistory.isEmpty()) {
            return null; // 或者根据业务返回默认值
        }

        // 二分查找：找到最后一个beginDate <= date的Record
        int left = 0;
        int right = sortedHistory.size() - 1;
        int candidateIndex = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            Record midRecord = sortedHistory.get(mid);
            LocalDate beginDate = midRecord.getTimeWindow().getBeginDate();
            if (beginDate.isBefore(date) || beginDate.isEqual(date)) {
                candidateIndex = mid;
                left = mid + 1; // 继续找更晚的可能匹配项
            } else {
                right = mid - 1;
            }
        }

        if (candidateIndex == -1) {
            return null; // 日期早于所有Record的beginDate
        }

        Record candidate = sortedHistory.get(candidateIndex);
        TimeWindow window = candidate.getTimeWindow();
        LocalDate endDate = window.getEndDate();
        // 检查日期是否在当前Record的时段内：endDate为null代表无限期
        if (endDate == null || date.isBefore(endDate) || date.isEqual(endDate)) {
            return candidate.getValue();
        } else {
            return null; // 理论上连续无重叠的话，这里不会走到？除非数据有问题
        }
    }
}

方案二：用TreeMap维护索引（更简洁） #

Java的TreeMap本身是基于红黑树实现的有序映射，支持O(log n)的查找操作。我们可以把每个Record的beginDate作为key，Record作为value，利用TreeMap.floorKey()方法快速找到小于等于目标日期的最大beginDate，再验证时段是否匹配。

实现步骤： #

public class RecordHistory {
    private List<Record> history;
    // 用TreeMap维护beginDate到Record的映射，自动排序
    private TreeMap<LocalDate, Record> dateToRecordMap;

    public void setHistory(List<Record> history) {
        this.history = history;
        dateToRecordMap = new TreeMap<>();
        for (Record record : history) {
            LocalDate beginDate = record.getTimeWindow().getBeginDate();
            dateToRecordMap.put(beginDate, record);
        }
    }

    public String getValueByDate(LocalDate date) {
        if (dateToRecordMap == null || dateToRecordMap.isEmpty()) {
            return null;
        }

        // 找到小于等于date的最大beginDate对应的Entry
        Map.Entry<LocalDate, Record> entry = dateToRecordMap.floorEntry(date);
        if (entry == null) {
            return null; // 日期早于所有Record的beginDate
        }

        Record candidate = entry.getValue();
        TimeWindow window = candidate.getTimeWindow();
        LocalDate endDate = window.getEndDate();
        if (endDate == null || !date.isAfter(endDate)) {
            return candidate.getValue();
        } else {
            return null; // 数据不符合连续无重叠的约定时可能出现
        }
    }
}

关键注意事项 #

• 两种方案都依赖时段连续无重叠的特性，这样我们找到的最后一个beginDate<=目标日期的Record，必然是包含该日期的那个（只要数据符合约定）。
• 如果history列表会频繁修改，那么每次修改都需要重新排序/更新TreeMap，这时候要权衡修改成本和查询成本。如果查询远多于修改，这两个方案都非常合适；如果修改很频繁，可能需要考虑其他结构，或者接受O(n)的查询。
• 处理endDate为null的情况时，要注意它代表“从beginDate开始一直有效”，所以只要目标日期>=beginDate就匹配。

内容的提问来源于stack exchange，提问作者TomVW