日期间隔计算的探索
高效
如题，高效精确的计算时间间隔（包含起始日，不含截止日）看似一个很简单的命题，实则不然，首先谈谈高效，也许大家首先想到的是循环判断每一年是否闰年，然后加上365天或者366天，最后减去起始日期的当年天数加上结束日期的当年天数。实现如下：
计算起止年所含天数，包含起始年不含结束年。
int CalDaysBetween(int yStart,int yEnd){
int days=0;int i;
for(i=yStart;i<yEnd;i++) days+=(i%400==0||(i%100!=0&&i%4==0))?366:365;
return days;
}
计算截止某日期当年天数
int CalDaysOfYear(int year,int month,int day){
int monthLen[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
int yearStyle= year%400==0||(year%100!=0&&year%4==0) ?1:0;
//this two line below will support overflows params
month = (month-1)%12;
//day = day%monthLen[yearStyle][month];
int ret=0;
int i=0;
for(i=0;i<month;i++) ret+=monthLen[yearStyle][i];
ret+=day;
return ret;
}
计算起止时间间隔
int CalDaysInterval(int yStart,int mStart, int dStart,int yEnd, int mEnd,int dEnd){
int daysStart = CalDaysOfYear(yStart,mStart,dStart);
int daysEnd = CalDaysOfYear(yEnd,mEnd,dEnd);
int daysBetween = CalDaysBetween(yStart,yEnd);
return daysBetween - daysStart + daysEnd;
}
试验结果和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的倍数的个数
int MultiplesBetween(int start,int end,int div){
//if(start > end ) return 0; //can be remarked because of usage
int modstart,modend;
modstart=start%div==0?1:0;
modend=end%div==0?1:0;
//printf("floor: %d --", floor((end-1)/div)-floor((start+1)/div));
return modend + modstart + floor((end-0.5)/div)-floor((start+0.5)/div); //floor
}
计算年份间的日期数
int CalDaysBetween2(int yStart,int yEnd){
yEnd-=1;
if (yStart>yEnd){ return 0; }
int num4,num100,num400;
num4=MultiplesBetween(yStart,yEnd,4);
num100=MultiplesBetween(yStart,yEnd,100);
num400=MultiplesBetween(yStart,yEnd,400);
int count_grandyear=num4-num100+num400;
return (365*(yEnd-yStart+1)+count_grandyear);
}
这个其实效率不高，计算两个数之间的某数的整数倍数的个数的方法，先计算闭区间首尾是否是倍数，然后计算开区间所含的倍数个数，里面涉及到浮点数的加减和除法操作，可以优化：
int inline yearType(int year){
return year%400==0||(year%100!=0&&year%4==0) ?1:0;
}
int CalDaysBetween3(int yStart,int yEnd){
return 365*yEnd + yEnd/4-yEnd/100+yEnd/400 - (365*yStart + yStart/4-yStart/100+yStart/400) + yearType(yStart) - yearType(yEnd);
}
由于内联函数并不被编译器认可，并且有两个乘法可以合并，注意这里的整数除法不能合并，否则出错，所以进一步优化为：
int CalDaysBetween3(int yStart,int yEnd){
return 365*(yEnd-yStart) + yEnd/4-yEnd/100+yEnd/400 - (yStart/4-yStart/100+yStart/400) + (yStart%400==0||(yStart%100!=0&&yStart%4==0) ?1:0) - (yEnd%400==0||(yEnd%100!=0&&yEnd%4==0) ?1:0);
}
大家可以自己写函数计时验证各种方法是速度，下图是三种方法速度对比。单位是毫秒。注意到方法2在日期年份间隔比较少的时候要慢，显然，日期年份间隔少，循环次数少，非循环方法带来的函数出入栈、乘除法开销劣势凸显。
不能优化了么？并不是，计算当年的日期里面也涉及到了循环，其实月份最多12个，可以用空间换时间的方法，将月份对应天数放到数组里查表快速得到，于是如下：
int CalDaysOfYear2(int year,int month,int day){
int daysSum[2][12]={{0,31,59,90,120,151,181,212,243,273,304,334},{0,31,60,91,121,152,182,213,244,274,305,335}};
int yearT= yearType(year);
return daysSum[yearT][month-1] + day;
}
注意到这里又对起止年份是否闰年进行了一次判断，那么判断就可以合并，并且略去函数调用
int CalDaysInterval2(int yStart,int mStart, int dStart,int yEnd, int mEnd,int dEnd){
int startT = yStart%400==0||(yStart%100!=0&&yStart%4==0) ?1:0;
int endT = yEnd%400==0||(yEnd%100!=0&&yEnd%4==0) ?1:0;
int daysSum[2][12]={{0,31,59,90,120,151,181,212,243,273,304,334},{0,31,60,91,121,152,182,213,244,274,305,335}};
return 365*(yEnd-yStart) + yEnd/4-yEnd/100+yEnd/400 - (yStart/4-yStart/100+yStart/400) + startT - endT - (daysSum[startT][mStart-1] + dStart) + daysSum[endT][mEnd-1] + dEnd;
}
但其实这仍然不是最优解，翻看网上资料的时候找到了一种解法，具体可以参考https://www.linuxidc.com/Linux/2015-02/114053.htm，代码我直接贴出来
int CalDaysInterval4(int yStart,int mStart, int dStart,int yEnd, int mEnd,int dEnd){
int m1,y1,m2,y2;
m1 = (mStart + 9)%12;
y1 = yStart-m1/10;
m2 = (mEnd + 9)%12;
y2 = yEnd-m2/10;
return 365*(y2-y1) + y2/4 - y2/100 + y2/400 + (m2*306 + 5)/10 + dEnd - ( y1/4 - y1/100 + y1/400 + (m1*306 + 5)/10 + dStart);
}
这种速度比上述优化后的还快，具体原理是将月份计算偏移，将2月作为最后一个月，就可以用(m*306+5)/10得到该月份前到上年3月1日的累计天数，避免了查表和闰年的判断。通过计算从公元元年3月1日到起止日期的天数得到天数差，再快20%。
准确
到这为止，算法的优化差不多了，上面的算法足够应付通常的使用了，但是有没有人好奇为啥闰年的计算方式是4年一闰，每四百年少3次？深入了解就会发现，上面的算法其实应用受限的，只能计算较少的年份范围，大概一两千年的范围，具体原因这里不详细阐述，直接贴链接：https://www.zhihu.com/question/25388501/answer/330669344
所以后面需要用代码改进。
简单的说就是再加两个闰年的判断，一个是每3200年不闰，每172800再闰一次，所以有代码：
int CalDaysInterval5(int yStart,int mStart, int dStart,int yEnd, int mEnd,int dEnd){
int startT = ((yStart%4==0&&yStart%100!=0)||(yStart%400==0&&yStart%3200!=0)||yStart%172800==0)?1:0;
int endT = ((yEnd%4==0&&yEnd%100!=0)||(yEnd%400==0&&yEnd%3200!=0)||yEnd%172800==0)?1:0;
int daysSum[2][12]={{0,31,59,90,120,151,181,212,243,273,304,334},{0,31,60,91,121,152,182,213,244,274,305,335}};
return 365*(yEnd-yStart) + yEnd/4-yEnd/100+yEnd/400-yEnd/3200+yEnd/172800 - (yStart/4-yStart/100+yStart/400-yStart/3200+yStart/172800) + startT - endT - (daysSum[startT][mStart-1] + dStart) + daysSum[endT][mEnd-1] + dEnd;
}
int CalDaysInterval6(int yStart,int mStart, int dStart,int yEnd, int mEnd,int dEnd){
int m1,y1,m2,y2;
m1 = (mStart + 9)%12;
y1 = yStart-m1/10;
m2 = (mEnd + 9)%12;
y2 = yEnd-m2/10;
return 365*(y2-y1) + y2/4 - y2/100 + y2/400 - y2/3200 + y2/172800 + (m2*306 + 5)/10 + dEnd - ( y1/4 - y1/100 + y1/400- y1/3200 + y1/172800 + (m1*306 + 5)/10 + dStart);
}
其实这里可以对为什么这么闰法的简单解释：
一年的时间，精确到秒是：
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:
要注意的是，最后介绍的方法仍然不是无限范围的日期计算，毕竟当年份上万后，影响公转周期的因素很多，单纯的这种闰年制是有误差的，要以天文观测为准。
原文链接：http://www.straka.cn/blog/exploration-of-date-interval-calculation/