今日から1万日後の日付けは何日か ?というような日付計算を1から考えました。C#なんかだとライブラリがありますが、あえてC言語でアルゴリズムを自分で考えてみます。最初はシンプルに実現し、完成系は足す値に寄らない高速演算をします。日付計算は簡単なようで複雑です。久しぶりに本気でアルゴリズムと格闘しました。 プログラマーには当たり前ですが、1年の日数は閏年により変動があります。 というルールです。 最初から最適解を求めると難航するので、シンプルで確実に動くものを実現し、そこからどう最適化していくかを考えていきます。 どうでしょうか。明日と昨日の日付計算は日常でも頭の中でやっている事なのでイメージがつきやすいと思います。 シンプル案はシンプルでバグの混入の可能性が低く、確実性としては良いアルゴリズムです。しかし、日数の値の数分ループ回数が増えるのは何とかしたい。仕事であれば、要求仕様を満たせればよいので、実行時間の制約が無ければシンプル案がベストです。 与えられた日付けを起点とすると、年月日が任意になるので月またぎ、年またぎ、閏年などの計算が固定しずらい。そこで・・・ 1. 年月日を日数に変換 まず起点となる0を定義します。
本来の西暦は1年1月1日からスタートするのですが、プログラム上は0からスタートしていたほうが計算しやすいため、0年1月1日を0として、そこからの経過日数を求めます。
変換は年、月、日をそれぞれ日数に変換して足すだけです。唯一年だけは閏年がありますが、簡単に求めることができます。 基本365日で、あとは閏年の発生した回数を足してあげればよいです。今回は、紀元前のマイナス計算は省いてます。 ここは書くまでもないです。Step1で日数に変換してあるので、単純に足すだけです。最終系のトップ関数をご覧ください。Step1から3までを順番にコールしています。 ここがとんでもなく苦労しました。2週間くらい悩みました… 考え方は周期を利用して、商と余りをもとめて一発計算です。閏年の周期性を考えたときに、400年が最大周期になります。 0年1月1日から399年12月31日までが最初の400年 この400年の日数は決まっていて、計算すると146097日です。日数をこの値で割った商を400倍するとこの周期での年数が求められます。 次に100年周期です。100年周期も同様の考えたで計算します。余りは、100年未満の日数になります。ただし、落とし穴があって、最初の100年の最初の年は400年周期でもあるので閏年ですが、以降の100年周期の最初の年は閏年ではありません。ここに気がつくのに時間を要しました。 次は4年周期です。これも同じ考え方で、残るは4年未満の日数です。ここにも大きな落とし穴があって、最初の年の閏年は400年周期と100年周期のいずれかで変動します。 次は1年周期です。これも同じ考え方で、残るは366日以下の日数です。 最後は月ごとに分解してやります。 周期的な部分はアルゴリズムを共通化できます。完成系はこちら。 極限まで最適化したので読解が難しいかも。 完成系はこちらになります。 効果を確認するために、大きめの日数計算をさせて、シンプル版と最適化案でのパフォーマンス確認を行いました。 満足がいくものが出来ました。今回はヘビーでした。 もっと簡単・高速にできる方法があったら教えてください。
1. 日付けの基本的なルール
2. シンプル案
1日前と1日後の日付を求める関数をそれぞれ作り、あとは足し引きする日数分ループします。#include <stdint.h>
// 月テーブル
const uint8_t month[2][12] = {
// 1 2 3 4 5 6 7 8 9 10 11 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
};
typedef struct _YMD {
uint32_t year;
uint8_t month;
uint8_t day;
} YMD;
// 閏年判定
bool isUru(uint32_t y)
{
if ((y % 400) == 0) {
return true;
}
if ((y % 100) == 0) {
return false;
}
if ((y % 4) == 0) {
return true;
}
return false;
}
// 1日足す
void ymd_calc_plus(YMD* p)
{
bool isuru = isUru(p->year);
int daymax = month[isuru][p->month - 1];
if (p->day < daymax) {
p->day++;
}
else {
p->day = 1;
if (p->month < 12) {
p->month++;
}
else {
p->month = 1;
p->year++;
}
}
}
// 1日引く
void ymd_calc_minus(YMD* p)
{
if (p->day > 1) {
p->day--;
}
else {
if (p->month > 1) {
p->month--;
bool isuru = isUru(p->year);
p->day = month[isuru][p->month - 1];
}
else {
p->year--;
p->month = 12;
p->day = 31;
}
}
}
void ymd_calc_basic(YMD* p, int32_t day)
{
int i;
if (day == 0) return;
if (day > 0 ) {
for (i = 0; i < day; i++) {
ymd_calc_plus(p);
}
}
else {
for (i = 0; i < -day; i++) {
ymd_calc_minus(p);
}
}
}
3. 最適化を検討する
今回は、趣味だからこそ極めたいという欲求からどんな日数でも同じ処理速度でバシッと結果を出すアルゴリズムを目指します。3.1 方針
2. 日数での加減算
3. 日数から年月日変換
という3ステップを踏むことにします。3.2 Step1. 年月日を日数に変換
// 年単位の日付取得. カウントは 西暦0年1月1日を0とする
static uint32_t y2d(const uint32_t y)
{
uint32_t n = y * 365;
if (y > 0) {
uint32_t n4 = (y-1) / 4;
uint32_t n100 = (y-1) / 100;
uint32_t n400 = (y-1) / 400;
n += (n4 - n100 + n400) + 1;
}
return n;
}
3.3 Step 2. 日数での加減算
void ymd_calc(YMD* p, int32_t day)
{
uint32_t n = ymd2day(p); // Step1
n += day; // Step2
day2ymd(p, n); // Step3
}
3.4 Step 3. 日数から年月日変換
400年1月1日から799年12月31日までが次の400年
そして余りは、400年未満の日数になります。static void _cycle_core(
uint32_t* const pyear,
uint32_t* const pday,
const uint32_t cycleYear,
const uint32_t cycleDay
)
{
if( *pday >= cycleDay ) {
*pyear += ((*pday / cycleDay) * cycleYear);
*pday %= cycleDay;
}
}
static void _cycle_calc(
uint32_t* const pyear,
uint32_t* const pday,
const uint32_t cycleYear,
const uint32_t cycleDay0,
const uint32_t cycleDay1,
const bool judge
)
{
if(judge) {
if( *pday >= cycleDay0 ) {
*pday -= cycleDay0; // cycle0
*pyear += cycleYear;
} else {
return;
}
}
_cycle_core( pyear, pday, cycleYear, cycleDay1); // cycle1
}
4. 最適化案
#include <stdint.h>
const uint8_t month[2][12] = {
// 1 2 3 4 5 6 7 8 9 10 11 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
};
typedef struct _YMD {
uint32_t year;
uint8_t month;
uint8_t day;
} YMD;
int isEqualYmd(const YMD* const p1, const YMD* const p2)
{
if (p1->year != p2->year) return 0;
if (p1->month != p2->month) return 0;
if (p1->day != p2->day) return 0;
return 1;
}
// 閏年判定
uint32_t isUru(uint32_t y)
{
if ((y % 400) == 0) {
return 1;
}
if ((y % 100) == 0) {
return 0;
}
if ((y % 4) == 0) {
return 1;
}
return 0;
}
/*
0 1 2 3 4
y = 0 0 1年未満
y = 1 366 0.1.1 - 0.12.31
y = 2 366 + 365 0.1.1 - 1.12.31
y = 3 366 + 365 + 365 0.1.1 - 2.12.31
y = 4 366 + 365 + 365 + 365 0.1.1 - 3.12.31
y = 5 366 + 365 + 365 + 365 + 366 0.1.1 - 3.12.31
*/
// 年単位の日付取得. カウントは 西暦0年1月1日を0とする
static uint32_t y2d(const uint32_t y)
{
uint32_t n = y * 365;
if (y > 0) {
uint32_t n4 = (y-1) / 4;
uint32_t n100 = (y-1) / 100;
uint32_t n400 = (y-1) / 400;
n += (n4 - n100 + n400) + 1;
}
return n;
}
// m月の月末までの年初からの総和 0 <= m <= 12
static uint32_t m2d(uint8_t m, int uru)
{
uint32_t n = 0;
for (int i = 0; i < m; i++) {
n += month[uru][i];
}
return n;
}
#define CYCLE400 146097 // 400年の日数 (最大周期なので1種類のみ) y2d(400)の結果
#define CYCLE100_0 36525 // 100年の日数 (400年周期の閏年あり) y2d(100)の結果
#define CYCLE100_1 (CYCLE100_0 - 1) // 100年の日数 (400年周期の閏年なし)
#define CYCLE4_1 1461 // 4年の日数 (400年周期の閏年あり) y2d(4)の結果
#define CYCLE4_0 (CYCLE4_1 - 1) // 4年の日数 (400年周期の閏年なし)
#define CYCLE1_0 366 // 1年の日数 (閏年あり)
#define CYCLE1_1 365 // 1年の日数 (閏年なし)
static void _cycle_core(
uint32_t* const pyear,
uint32_t* const pday,
const uint32_t cycleYear,
const uint32_t cycleDay
)
{
if( *pday >= cycleDay ) {
*pyear += ((*pday / cycleDay) * cycleYear);
*pday %= cycleDay;
}
}
static void _cycle_calc(
uint32_t* const pyear,
uint32_t* const pday,
const uint32_t cycleYear,
const uint32_t cycleDay0,
const uint32_t cycleDay1,
const bool judge
)
{
if(judge) {
if( *pday >= cycleDay0 ) {
*pday -= cycleDay0; // cycle0
*pyear += cycleYear;
} else {
return;
}
}
_cycle_core( pyear, pday, cycleYear, cycleDay1); // cycle1
}
// public functions
// 日付 --> 日数変換
uint32_t ymd2day(const YMD* const p)
{
int uru = isUru(p->year);
int n = y2d(p->year); // 前年の年末までの日数
n += m2d(p->month - 1, uru); // 前月の月末までの年初からの日数
n += p->day - 1; // 日付は 0 スタートでカウントする
return n;
}
// 日数 --> 日付変換
void day2ymd(YMD* const p, const uint32_t day)
{
uint32_t n = day;
uint32_t yy = 0;
uint8_t mm = 0;
uint8_t dd = 0;
//------------------------------------------------------
// 1. 400 years cycle
_cycle_core(&yy, &n, 400, CYCLE400);
//------------------------------------------------------
// 2. 100 years cycle
_cycle_calc(&yy, &n, 100, CYCLE100_0, CYCLE100_1, 1);
//------------------------------------------------------
// 3. 4 years cycle
_cycle_calc(&yy, &n, 4, CYCLE4_0, CYCLE4_1, yy % 400);
//------------------------------------------------------
// 4. 1 year cycle
_cycle_calc(&yy, &n, 1, CYCLE1_0, CYCLE1_1, isUru(yy));
// fixed year
//------------------------------------------------------
// 5. 1 month cycle
const int uru = isUru(yy);
for (int i = 0; i < 12; i++) {
const uint8_t c = month[uru][i];
if (n < c) {
mm = i + 1; // fix month
dd = n + 1; // fix day
break;
}
n -= c;
}
p->year = yy;
p->month = mm;
p->day = dd;
}
void ymd_calc(YMD* p, int32_t day)
{
uint32_t n = ymd2day(p);
n += day;
day2ymd(p, n);
}
5. 効果確認
basic がシンプル案。opt が最適化案で、単位はmsです。
最適化案の圧倒的な速度が達成できてます。basic = 4657
opt = 0
basic = 5922
opt = 0
basic = 8625
opt = 0
basic = 11656
opt = 0
basic = 14734
opt = 16
basic = 18047
opt = 0
basic = 20609
opt = 0
basic = 23703
opt = 0
basic = 26735
opt = 0
basic = 29625
opt = 0