PMPの流儀

PMPの流儀

エンジニアのページ

MENU

【日付計算】何日後、何日前の日付計算を極める by C言語

今日から1万日後の日付けは何日か ?というような日付計算を1から考えました。C#なんかだとライブラリがありますが、あえてC言語アルゴリズムを自分で考えてみます。最初はシンプルに実現し、完成系は足す値に寄らない高速演算をします。日付計算は簡単なようで複雑です。久しぶりに本気でアルゴリズムと格闘しました。
f:id:ruruucky:20211013234609j:plainf:id:ruruucky:20211013235141j:plain

1. 日付けの基本的なルール

当たり前の話ですが1年の日数は閏年により変動があります。

  • 4で割れたら閏年
  • でも、100で割れたら閏年ではない
  • でもでも、400で割れたらやっぱり閏年

というルールです。

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

満足がいくものが出来ました。あとは負の数まで拡張して紀元前まで対応すれば真の完成系になりますが、しばし休養をとります。