Exploration of date interval calculation

日期间隔计算的探索

Abstract: Most of us may think the date interval calculation is easy, but in different ways, the efficiency varies, In this blog, I compared several methods, and tried to impore their performance.

高效

如题,高效精确的计算时间间隔(包含起始日,不含截止日)看似一个很简单的命题,实则不然,首先谈谈高效,也许大家首先想到的是循环判断每一年是否闰年,然后加上365天或者366天,最后减去起始日期的当年天数加上结束日期的当年天数。实现如下:

计算起止年所含天数,包含起始年不含结束年。

计算截止某日期当年天数

计算起止时间间隔

试验结果和windows自带的日期计算工具比较,一个是excel,一个是计算器

oops, excel将1900年识别为闰年,好吧,这是个问题,计算器倒是准确计算了。此外,测试了下excel的日期计算范围是1900-1-1~9999~12-31,计算器的计算时间范围从1601-1-1~9999-12-31。后面再详细讨论这里面的问题。

上述方法显然满足了要求,并且能计算超过windows自带工具的计算范围,但效率太低,如果计算年份跨度上千,就需要上千次的循环次数,而显然根据闰年的计算方法,应该可以想办法把循环去掉。方法是计算起止年份中4、100、400的整数倍数,用365乘以年数,加上4、400的倍数的个数减去100 的倍数的个数即得到起止日期间整年的天数,再同上减去起始日期的当年天数加上结束日期的当年天数,如下

计算start、end之间(含start,end,即[start,end])div的倍数的个数

计算年份间的日期数

这个其实效率不高,计算两个数之间的某数的整数倍数的个数的方法,先计算闭区间首尾是否是倍数,然后计算开区间所含的倍数个数,里面涉及到浮点数的加减和除法操作,可以优化:

由于内联函数并不被编译器认可,并且有两个乘法可以合并,注意这里的整数除法不能合并,否则出错,所以进一步优化为:

大家可以自己写函数计时验证各种方法是速度,下图是三种方法速度对比。单位是毫秒。注意到方法2在日期年份间隔比较少的时候要慢,显然,日期年份间隔少,循环次数少,非循环方法带来的函数出入栈、乘除法开销劣势凸显。

不能优化了么?并不是,计算当年的日期里面也涉及到了循环,其实月份最多12个,可以用空间换时间的方法,将月份对应天数放到数组里查表快速得到,于是如下:

注意到这里又对起止年份是否闰年进行了一次判断,那么判断就可以合并,并且略去函数调用

但其实这仍然不是最优解,翻看网上资料的时候找到了一种解法,具体可以参考

https://www.linuxidc.com/Linux/2015-02/114053.htm

https://blog.csdn.net/solstice/article/details/5814486,

代码我直接贴出来

这种速度比上述优化后的还快,具体原理是将月份计算偏移,将2月作为最后一个月,就可以用(m*306+5)/10得到该月份前到上年3月1日的累计天数,避免了查表和闰年的判断。通过计算从公元元年3月1日到起止日期的天数得到天数差,再快20%。

准确

到这为止,算法的优化差不多了,上面的算法足够应付通常的使用了,但是有没有人好奇为啥闰年的计算方式是4年一闰,每四百年少3次?深入了解就会发现,上面的算法其实应用受限的,只能计算较少的年份范围,大概一两千年的范围,具体原因这里不详细阐述,直接贴链接:https://www.zhihu.com/question/25388501/answer/330669344

所以后面需要用代码改进。

简单的说就是再加两个闰年的判断,一个是每3200年不闰,每172800再闰一次,所以有代码:

其实这里可以对为什么这么闰法的简单解释:

一年的时间,精确到秒是:

365天5小时48分45.5秒 = 365.24219328703703704…天

如果四年一闰就是   365+1/4=365.25天

再每一百年不闰       365+1/4-1/100 =365.24天

再每400年一闰       365+1/4-1/100+1/400 =365.2425天

再每3200年不闰     365+1/4-1/100+1/400-1/3200 =365.2421875天

再每172800年闰     365+1/4-1/100+1/400-1/3200+1/172800 =365.24219328703703704…天

此外我们注意到excel和windows自带附件计算器对于3200年的判断都是错误的,oops,不过微软对此有部分解释:

https://support.microsoft.com/en-us/help/214326/excel-incorrectly-assumes-that-the-year-1900-is-a-leap-year

PS:

要注意的是,最后介绍的方法仍然不是无限范围的日期计算,毕竟当年份上万后,影响公转周期的因素很多,单纯的这种闰年制是有误差的,要以天文观测为准。

Code link:   https://github.com/atp798/BlogStraka/tree/master/CalcDateInterval

发表评论