今日から1万日後の日付けは何日か ?というような日付計算を1から考えました。C#なんかだとライブラリがありますが、あえてC言語でアルゴリズムを考えてみます。最初はシンプルに実現し、完成系は足す値に寄らない高速演算を目指します。日付計算は簡単なようで複雑です。久しぶりに本気でアルゴリズムと格闘しました。
- 1. 日付けの基本的なルール
- 2. シンプル案
- 3. 最適化を検討する
- 3.1 方針
- 3.2 Step1. 年月日を日数に変換
- 3.3 Step 2. 日数での加減算
- 3.4 Step 3. 日数から年月日変換
- 4. 最適化案
- 5. 効果確認
1. 日付けの基本的なルール
プログラマーには当たり前ですが、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 方針
与えられた日付けを起点とすると、年月日が任意になるので月またぎ、年またぎ、閏年などの計算が固定しずらい。そこで・・・
1. 年月日を日数に変換
2. 日数での加減算
3. 日数から年月日変換
という3ステップを踏むことにします。
3.2 Step1. 年月日を日数に変換
まず起点となる0を定義します。 本来の西暦は1年1月1日からスタートするのですが、プログラム上は0からスタートしていたほうが計算しやすいため、0年1月1日を0として、そこからの経過日数を求めます。 変換は年、月、日をそれぞれ日数に変換して足すだけです。唯一年だけは閏年がありますが、簡単に求めることができます。
// 年単位の日付取得. カウントは 西暦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; }
基本365日で、あとは閏年の発生した回数を足してあげればよいです。今回は、紀元前のマイナス計算は省いてます。
3.3 Step 2. 日数での加減算
ここは書くまでもないです。Step1で日数に変換してあるので、単純に足すだけです。最終系のトップ関数をご覧ください。Step1から3までを順番にコールしています。
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. 日数から年月日変換
ここがとんでもなく苦労しました。2週間くらい悩みました…
考え方は周期を利用して、商と余りをもとめて一発計算です。閏年の周期性を考えたときに、400年が最大周期になります。
0年1月1日から399年12月31日までが最初の400年
400年1月1日から799年12月31日までが次の400年
この400年の日数は決まっていて、計算すると146097日です。日数をこの値で割った商を400倍するとこの周期での年数が求められます。
そして余りは、400年未満の日数になります。
次に100年周期です。100年周期も同様の考えたで計算します。余りは、100年未満の日数になります。ただし、落とし穴があって、最初の100年の最初の年は400年周期でもあるので閏年ですが、以降の100年周期の最初の年は閏年ではありません。ここに気がつくのに時間を要しました。
次は4年周期です。これも同じ考え方で、残るは4年未満の日数です。ここにも大きな落とし穴があって、最初の年の閏年は400年周期と100年周期のいずれかで変動します。
次は1年周期です。これも同じ考え方で、残るは366日以下の日数です。
最後は月ごとに分解してやります。
周期的な部分はアルゴリズムを共通化できます。完成系はこちら。
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
満足がいくものが出来ました。今回はヘビーでした。
もっと簡単・高速にできる方法があったら教えてください。
