python - 使用 Python 在给定日期间隔列表的情况下查找日期子间隔的值

Question

假设我有一个数据集，其中包含一堆日期范围(开始日期和结束日期)和每个日期范围的值。例如，我的数据可能如下所示

Start         End           Value
2005-01-01    2005-01-31    6.54
2005-02-01    2005-02-28    5.55
2005-03-01    2005-03-31    3.67
2005-04-01    2005-04-30    2.91

这将作为元组列表存储在 Python 中:

mydata = [(datetime.date(2005, 1, 1), datetime.date(2005, 1, 31), 6.54), 
          (datetime.date(2005, 2, 1), datetime.date(2005, 2, 28), 5.55),
          (datetime.date(2005, 3, 1), datetime.date(2005, 3, 31), 3.67),
          (datetime.date(2005, 4, 1), datetime.date(2005, 4, 30), 2.91)]

我想要一个可以将任何日期间隔作为输入并输出值总和的函数。例如，如果我的输入是 [datetime.date(2005, 2, 1), datetime.date(2005, 3, 31)] 那么我的输出将是 9.22(等于 5.55 + 3.67) .

但是，如果我的输入是 [datetime.date(2005, 2, 1), datetime.date(2005, 3, 15)] 那么我的输出将是 None 因为我找不到匹配项。

Answer 1

一个可能的解决方案是将所有日期(包括开始和结束类型)存储到一个排序列表中。将有另一种数据结构(可能是字典)维护开始日期和结束日期之间的映射以及值。

您的搜索将包括获取指定范围内排序列表中的所有值，这可以通过二分搜索高效地完成。对于返回值中的每个开始/结束日期，还必须找到相应的开始/结束日期。如果找到没有结束日期的开始日期，或者找到没有开始日期的结束日期，则该日期范围不在您的搜索范围内，不应包含在您的结果中。这一步可以用字典有效地实现。

对于第二步，我会使用双映射，因此从给定日期查找开始/结束日期很容易。在处理使用二分查找找到的日期时，您可以在列表中查找您希望找到的元素并维护一个预期列表。如果稍后在搜索中找到该元素，请将其从预期列表中删除。