原来我从来都没有搞懂过历法

注:本文的所有引用,不使用本博客的CC授权,而使用与来源一致的许可证/许可条款/授权。请注意使用条件。

最近在写自己用的日历系统,才发现,原来我从来都没有搞懂过历法。
历法是很复杂的东西,抛开农历这种复杂的日历来说,就是实现一个普通的格里高利历就是一个痛苦。涉及到各种计算的方法。在这里我将会用流水账的方式记述我在写这个日历时遇到的历法问题,以及解决的方法。
相关的代码会在这里摘录一部分,但是全部代码需要到我的gist工程里的CalendarTest下查看。
我的日历目前的目标是在1970年-2100年这个区间内支持带有事件提醒功能的日历。由于是个人使用,考虑到自己也活不过2100年,这种限制反而能让开发省下一些功夫。日历是基于UNIX时间戳的,但我想在这里制作一个与UNIX时间戳近乎无关的计算系统,来计算一些相关的操作,也就是从公元元年到无限远的任意时间的计算。这可能会有些淡腾,但还是值得试一试。

主要涉及的内容有两点,一个是格里高利历的相关计算,例如闰年等。另一个是事件循环的计算的算法。

首要的一个分析

在之前我有一个愚蠢的想法。如果我给定一个年份,我想知道在它之前有多少闰年,如何计算,我的愚蠢方法是直接一年一年的循环,然后一个一个分析是不是闰年。我知道这绝对不是最佳算法,但是这是我一开始唯一能想到的方法。后来我看到了这个文章,里面有一段代码启发了我,但是因为它是有版权的,因此我不能在这里引用它(本文是CC授权),也不能直接对着它抄(我的gist代码也是开源许可证授权的,为了规避版权),因此我就在这里粘贴一下在它启示下(启示我用数学规律而不是循环来解决问题)我自己实现的代码:

def LeapYearCount(endYear, includeThis = False, baseYear = 1, includeBase = True):
    if not includeThis:
        endYear -= 1
    if includeBase:
        baseYear -= 1

    endly = int(endYear / 4)
    endly -= int(endYear / 100)
    endly += int(endYear / 400)

    basely = int(baseYear / 4)
    basely -= int(baseYear / 100)
    basely += int(baseYear / 400)

    return (endly - basely)

需要关注的代码只有endly那三行。第一行,计算与4的商,这是四年一闰的体现。第二行,去除掉符合100整数的年份数量,这是100年不闰的体现。第三行,再将400年一闰的个数再加回来。因此只需要一点简单的数学规律就可以将我以前傻乎乎的方法摆平了。

之后的一些分析

考虑到世界上各处有着多种多样的时间规则,进行了逐一分析。首先是夏令时,夏令时只是显示上的变快和变慢,并不影响UNIX时间戳的内部运行机里,在交付客户端进行显示的时候让客户端依据客户计算机的设置来进行显示即可。
然后是时区问题,由于使用UNIX时间戳,其定义了其是UTC时间,因此在服务器上,来自不同时区创建的事件均实际存储为UTC。实际在网络传输过程中的时间戳也是基于UNIX的,抹掉了各个客户端之间时区差异,不会造成混乱。
时区问题虽然不会对显示和存储上造成麻烦,但对于循环的计算却会有影响。因为循环规则中不显式包含循环日子的设定,需要解析事件开始事件来获得一部分循环规则,因此时区设定可能会造成一些问题。例如客户端在2月28日定义了一个每一个月循环一次的事件,且其不在UTC时区,那么在传输到服务端后,服务端拿到的UTC日期可能会变成2月29日(如果碰巧闰年)等,如果直接让服务端按2月29日带入分析就会出大问题。最后决定的处理方法是在数据中加入一个表征客户端时区Offset的字段。加入后就可以避免时区判断错误,但是这样做会导致夏令时出现问题,但,我现在也用不到夏令时,等做大再考虑吧。
最后是闰秒问题。我选用UNIX时间戳,最初的思虑是他比较熟悉,并且基本上都有库来支持。所以使用起来问题也不大。直到闰秒部分,我才开始仔细考虑选用UNIX时间戳是否合适。最终的判断是:合适。我参考了知乎上的这篇回答,里面有如下描述(原始来源):

The Unix time number is zero at the Unix epoch, and increases by exactly 86400 per day since the epoch.

因此,UNIX时间戳对于闰秒的处理方式,与我喜好的方式完全一致。即,正闰秒视为不存在,负闰秒对应的UNIX时间戳视为跳过。其实作为日历,只需要精确到分钟的事件即可。之所以考虑闰秒,是考虑万一UNIX时间戳是随着闰秒加减的,会导致一天不是正好的86400刻度的情况,给我后续的计算带来麻烦。

还有一点,正如上面所说,日历只需要精确到分钟,因此我程序中记录事件时用的并不是原始的UNIX时间戳,而是将其除以60,获得粒度为分钟的时间戳。无意中延长了2038问题,同时也简化了我的一部分计算。

循环事件结束时间算法

循环事件算法最主要集中于循环次数定义的循环。因为无限循环和截止时间循环都非常简单,相当于直接给定了终止时间。而基于循环次数的循环事件,计算循环次数是一个头疼问题。下面按照个人梳理的方式把4种事件循环方法的按次计算过一遍。
这部分是由服务器来进行计算的,代码可以从我个人的实现里找(在dt.py里)

按年

按年的计算方法也比较简便,由于支持每x年,因此只需要知道循环次数y,则结果为:起始时间戳+1年时间戳长度*x*y
但棘手的问题在于闰年的循环。例如,我在某个闰年的2月29日,设置了一个每隔3年循环一次的事件。如果不考虑400年闰和100年不润,那么它将会12年循环一次,也就是定义的3和默认循环年度4的最小公倍数。而考虑100年和400年的逻辑后,情况会更复杂。
权衡之后,决定对闰年且设定29日的情况使用非常低效的每一年判断一次,直到算完的算法。

按月

按月有4种算法。每年第X日,每年倒数第X日,每年第X个星期Y,每年倒数第X个星期Y。算法上遵循较为低效的一个月判断一次,直到判断完毕。处理方法种每个月都调用MonthDayCount函数来给出数据。一个函数给出了一个月4种算法的极限数据。之后如果是前两种算法,就可以直接根据月份中日子的数目来判断是不是可以安排。后两种则要调用GetMonthWeekStatistics来对本月每个星期有多少个进行获取。由于根据计算,一个月的某个星期最少有4个,最多有5个,因此对于4个和4个以下,可以直接给出肯定回答,5个以上可以给出否定回答。

按周和按日

按周和按日是最简单的。按周和按日均支持每x周,每x日的特性,因此只需要知道循环次数y和起使时间戳就可以算出来终止时间戳。
其中按周比较特殊,因为其每周还可以指定7天,因此其循环次数需要提前进行y/每周次数获得实际意义上的y,然后计算y%每周次数,获得之后还需要续多少次。

按周:起使时间戳+7天时间戳长度*x*y+余下次数时间戳长度 按日:起始时间戳+1天时间戳长度*x*y

这样算会比较宽泛,不过问题不大,只要把控好不要超出范围就是可接受的。尤其需要注意7天时间戳长度和1天时间戳长度的数值,需要保证加上去之后不要越过23点59分,一旦越过会进入下一个可识别范围,会导致产生不必要的错误。

问题回到按周的y%每周次数上来。会获得一个余数,然后先确定起使日子是星期几,然后根据按周的星期启用表,从获得的星期开始循环遍历(指遍历到尾部则回到头部),每次遍历到一个,就将之前的余数-1,直到余数为0,计算遍历过多少日子,就可以知道余下次数的时间戳长度

循环事件具体发生时间算法

上面梳理了循环事件结束时间算法,知道了循环事件的开始和结束时间,我们就可以放心大胆去计算了,因为只要开始时间落在循环区间内的,都是有效事件,不需要再做过多的判断。
这部分是由客户端来进行计算的,代码可以从我个人的实现里找(在datetime.js里)

一开始是分别对每种循环单独写的,但是写完后发现还是有共通的地方的。基本操作就是获取开始时间,然后找到离判断时间段最近的一次循环事件然后从那里开始判断。

最后的一些事情

在关于循环结束时间的计算的时候,因为本身算法拉跨就只能去询问群友的意见,有没有什么统一的公式可以计算。反倒是被群友反问了一番为什么要有那么奇怪的设定。最后在参考Google日历和Outlook日历之后,为按月和按年的循环增加了所谓严格模式和宽松模式,严格模式就是我之前的设计,例如2月29日的一年一次循环实际是四年一次循环。而宽松模式则允许将日子安排在最近的一天,如果日子不存在的话,例如2月29日一年一次循环,不存在的会安排在28日。这也可以给用户更加宽泛的选择,毕竟这两种模式都有应用情景。

目前,我的日历工程大部分已经完成,按月和按日的循环已经调试完毕,而按年和按月的调试仍然有问题,还需要解决。上面所述的代码你也可以在我的工程里查阅。