1

假设我有一个由一堆日期范围（开始日期和结束日期）和每个日期范围的值组成的数据集。例如，我的数据可能如下所示

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因为我没有匹配项。

4

2 回答 2

1

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

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

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

于 2013-08-17T14:04:21.127 回答
0

查看http://en.wikipedia.org/wiki/Depth-first_search或http://en.wikipedia.org/wiki/Breadth-first_search搜索，其中日期是节点，值是成本边缘。

于 2013-08-17T14:06:07.460 回答