高效算法：确定日期是否处于夏令时

Question

我正在寻找一个比O(n)算法更好的算法来确定未来的一个日期是否会应用夏令时（以及应用的时间）。给定一年、月、日、小时、分钟和时区（以及Olson时区数据库的副本），如何有效地确定该日期是否处于DST？我需要的是算法，而不是调用库函数。

谢谢。

进一步解释：我使用的日期库在创建具有未来日期和时区的对象时非常缓慢。结果发现它在进行线性计算以计算日期是否处于夏令时。不仅如此，它也是在对象创建时执行这项工作的。显然，它可以等到被询问时再执行此操作，但它也应该更加高效。

当然，DST规则会发生变化，日期库无法预测未来，但另一种选择是对本地化日期设置任意上限。

- Schwern

---

在未来的10万年里，会产生相当多的闰秒，其数量可能无法预测。此外，我想知道时区是否仍然会被使用。 - Thilo

更不用说夏令时规则了。你不能信任它们超过未来大约2年，更别提1000年了。 - whybird

是的，国会对Y2K的过度反应总是让我感到好笑，然后毫不考虑影响（或选民对此变化的期望），轻松地改变夏令时规则，也没有提前通知。 - erickson

我痛苦地意识到时区是政治问题，并且随着时间的推移而改变。尽管如此，日期时间库仍然必须响应请求。如果有帮助，请将其视为更抽象的问题。 - Schwern

@Thilo 尽管时区系统很糟糕，但在我们都住在虚拟现实掩体中之前，您仍然需要一个近似太阳在天空中位置的系统。 - Schwern

Answer 1

大家已经谈论了始终变化的夏令时存在的问题。但我可以接受这样的前提，我们假装当前已知的规则将永远适用。

要获取您的夏令时信息，首先要做的是计算未来日期的年/月/日（如果它不是以该形式表示的）。然后查找您的时区并提取相对于UTC的变化、夏令时开/关规则和偏移量。根据您的“目标”年份可能会有几种不同的规则，要确保抓住正确的规则。由于下面解释的原因，也可能很方便了解前一年的规则。

开/关规则将具有类似于“Oct lastSun”这样奇怪的规格：这意味着在十月最后一个星期天的晚上切换发生。

您需要做的是收集所有这些简洁格式的“规则”，并为每个规则开发一些代码，以确定该规则指示的最后一个日期。现在是十二月，所以给定像“3月最后一个星期天”和“10月最后一个星期天”这样的规则，我的时区会有这些日期: 2009年3月29日和2009年10月25日。这些日期中哪个更近？十月。十月与“关闭”相关，因此我们目前没有夏令时。

无论目标日期是在夏令时开始或结束日期之前还是之后，您都可以计算当前（即目标）年份的夏令时开启/关闭日期；如果开启/关闭日期在目标日期的未来，则只需再次为上一年进行规则计算。请注意，规则可能在此期间发生了变化，因此请确保应用于您正在查看的年份的正确规则。

最坏情况下，您需要为上一年重复两次规则计算。但除此之外，没有其他搜索，因此它严格是O(1)。

我在这里找到了一个本地/夏令时/时区计算器：http://home-4.tiscali.nl/~t876506/WhatDay.html，由于它是JavaScript小程序，您应该能够轻松地借鉴代码。不过它并不能处理所有规则，因此您需要添加一些代码以处理剩余规则。

---

更新：我刚刚注意到你的时间中有小时和分钟。这会稍微复杂一些。如果你的日期不是在“切换”日期上，那么我上面给出的指示就可以了。否则，你需要考虑时间。我想最干净的做法是在确定“最近”的时候包括时间。也就是说，如果你的目标时间是00:30 UTC，而给定时区的切换时间是01:00，那么目标年份的切换时间仍然在未来，你必须使用前一年的切换时间。实际上，这意味着“其他”切换时间是最近的，它的开/关状态适用。

- Carl Smotricz

Answer 2

你最大的问题是由当地政府制定的夏令时规则。政府可以随时通过几乎任何法律，因此改变规则的方式是你无法预测的。

- sharptooth

---

谢谢，我知道并接受了。这是必须面对的。我想要高效地应用已知的规则。 - Schwern

Answer 3

据我所知，已知的夏令时更改每年都在固定的日期开始和结束（如四月第一个周末，十月最后一个周末等）。因此，您可以使用Doomsday Algorithm来查找给定年份的星期几，并从中计算转换日期。然后，您可以确定源和/或目标语言环境是否正在实行夏令时。转换本身只是添加和/或减去一小时以补偿夏令时，然后考虑时区差异的问题。

- jilles de wit

Answer 4

嗯，我认为问题的关键是确定一个未来很远的日期的星期几。

为此，我建议采用以下方法：

• 每隔400年，整个系统就会翻转一次，因此首先将年数除以400，取整数部分。在400年中，有99个闰年和301个普通年。如果任意一天是星期一，则400年后的同一天将是301+2x99 = 499（mod 7）---> 星期一+2 ---> 星期三。因此，您必须这样说：

wday = (ref_day + 2 *（int）（（target_year - ref_year）/ 400））mod 7

• 然后您可以进行进一步的优化，但我想您可以逐年进行计算，这样做就可以了。最多进行399个简单操作，如果（闰年）则++，否则+=2，mod 7。

在您获得该年1月1日的星期后，您可以像Carl Smotricz所写的那样计算夏令时切换日期。

- Dénes Tarján

---

努力不错，但你所展示解决的问题已经得到了优美的解决。看看 Zeller 的同余公式（一个方便的公式）：http://en.wikipedia.org/wiki/Zeller's_congruence。Jilles de wit 提到的末日算法也可以做到这一点，但它更多地是一个用于心算的算法，而非嵌入程序的公式。 - Carl Smotricz

对于未来的查找者，Zeller's wiki page 的链接无效。正确的链接是http://en.wikipedia.org/wiki/Zeller's_congruence。 - Joshua Dance