python - 如何计算非连续数据中的每周、每月和季节性开始和结束日期

Question

我有一系列日期可以追溯到几年前，但是，它们不是连续的，这意味着在某些星期有 7 个日期，在其他一些星期有 3 个日期，在某些极端情况下只有一个日期那一周。

我需要确定并标记每周有可用日期的开始和结束日期。例如，2015-06-23、2015-06-24、2015-06-25 和 2015-06- 27 记录了从 2015-06-22(星期一) 开始的一周，所以 2015-06-23 和 2015-06-27 应该分别是那一周的开始和结束。如果给定一周只有一个日期记录，那么该日期应该同时是该周的开始和结束。

将相同的概念扩展到月份，我需要识别并标记任何给定月份记录的开始和结束日期，无论给定月份有多少个日期。

同样，这同样适用于可以自定义四个季节的定义(根据开始和结束月份)的季节。也就是说，我可以将四个季节定义为: Spring (三月至五月)、夏季(六月至八月)、秋季(九月至十一月)、冬季(十二月至二月)，或者我可以改变月份以使用一些不同的定义.事实上，我们可以完全抛弃常规的季节概念，定义四个连续的时期，每个时期连续三个月。鉴于这样的定义，我需要确定每个给定时期/季节可用的开始和结束日期。

执行上述所有操作的高效算法是什么？

Answer 1

它是 Element Distinctness Problem 的变体，您需要在其中找到每个“不同”元素的 2 个特定实例。
(减少元素差异可以通过为第i元素添加i/epsilon时间来完成，然后找出是否有一周超过一次约会)。

元素的区别通常通过以下两种方法之一来解决，这里也可以应用:

1. 对数据进行排序，然后对其进行迭代。在排序的数据中，很容易找到每周/每月/每年/...的第一次和最后一次出现。
2. 填充从周数(整数)映射到列表的 HashMap ，包括本周的所有日期。找到第一个(最早的)数据很容易，然后您可以将本周定义为“第 1 周”，稍后，很容易计算每个日期与“第 1 周”的偏移量(以周为单位)。因此，首先找到这个“第 1 周”日期(单次迭代)，然后 - 创建所需的 map (在第二次迭代中，每次插入平均为 O(1))，最后 - 迭代 map 和每个日期 - 输出与本周相关的列表中的最小和最大日期。

请注意，如果您正在寻找可扩展的解决方案，第二种方法可以转换为 map-reduce很容易。