Быстрая структура времени от секунд

Question

Я ищу самый быстрый способ определить компоненты даты для вектора временных отметок NTP.

Входными данными в этом случае являются метки времени NTP или секунды, измеренные с 1900-01-01, переход к времени Unix и обратно является тривиальным путем сложения 2208988800 или вычитания, если происходит другой путь. Мне нужно разбить временные метки на компоненты даты для других API, которые принимают только даты в качестве своих компонентов, а именно год, месяц и день.

Использование методов ANSI C из time.h (glibcЯ могу легко получить компоненты, но это слишком медленно для больших векторов. Меньший вектор может содержать 172800 значений, но более реалистично, я бы хотел иметь возможность обработать вектор с 1314000 значениями как можно быстрее.

Я думал, что мог бы потратить время сам и устранить небольшое количество glibc накладные расходы путем итеративного вычитания метки времени, введенной вторыми делителями для каждого компонента даты, до тех пор, пока я не достигну даты, по существу, что glibc обходится без часовых поясов и дополнительных (небольших) накладных расходов.

Я быстро обнаруживаю, что до сих пор так медленно.

Я работаю с чем-то вроде этого:

typedef struct simple_time_ {
    int year;
    int month;
    int day;
} simple_time;

size_t time_cruncher(const time_t *ntp_vector, simple_time *out, size_t len)
{
    size_t i;
    time_t corrected;
    struct tm cal;
    for(i=0;i<len;i++) {
        corrected = ntp_vector[i] - 2208988800; /* NTP Offset */
        gmtime_r(&corrected, &cal);
        simple_time[i].year = cal.tm_year + 1900;
        simple_time[i].month = cal.tm_mon + 1;
        simple_time[i].day = cal.tm_mday;
    }
    return i;
}

Есть ли какой-нибудь алгоритм, который поможет мне быстрее вывести вычисления? Что-то вроде алгоритма Зеллера, но переходя от секунд к датам?

Спасибо!

Answer 1

Учитывая, что существует большая вероятность того, что многие из ваших последовательных меток времени будут в одном месяце, используйте это в своих интересах.

Pseudo code
1) Calculate the y,m,d for the given timestamp 't' as you have above.
2) now calculate the t0 = gmtime(y, m, 1) and t1 = gmtime(y, m+1, 1).  (Dec + 1 is OK)
3) As long as your timestamps are t0 <= t < t1, a simple add/divide is need to determine the day of the month.
4) Should 't' fall outside the range,  go to step 1.

Можно также определить время начала и окончания текущего дня, посмотреть, относится ли это к следующим временным меткам.

Answer 2

Если ваши временные метки находятся в диапазоне дат от 1901 до 2099 года, вы можете воспользоваться тем фактом, что каждый четвертый год является високосным (это может быть дополнительно расширено, чтобы включить даты в пределах 1900 года, поскольку это не високосный год).

Я получил этот код из библиотеки даты c, над которой я работаю, с разницей в этом коде я использую подход "сдвинутый месяц", как в соответствии с конгруэнтностью Зеллера.

#include <stdio.h>
#include <assert.h>
#include <stdint.h>

void
dt_to_ymd(unsigned int n, int *yp, int *mp, int *dp) {
    unsigned int z, c;
    int y, m, d;

    assert(n <= 73107); /* 2100-02-28 */

    z = n + 307;                    /* 1 + 306 (306 days between March 1 and December 31) */
    y = (4 * z) / 1461;
    c = z - (1461 * y - 1) / 4;     /* day of the year [1, 366]  */
    m = (5 * c + 456) / 153;        /* month of the year [1, 12] */
    d = c - (153 * m - 457) / 5;    /* day of the month [1, 31]  */

    if (m > 12)
        y++, m -= 12;

    if (yp) *yp = y + 1899;
    if (mp) *mp = m;
    if (dp) *dp = d;
}

const struct test {
    int year;
    int month;
    int day;
    uint64_t timestamp;
} tests[] =  {
    { 1900,  1,  1,          0 },
    { 1970,  1,  1, 2208988800 },
    { 1972,  1,  1, 2272060800 },
    { 1999, 12, 31, 3155587200 },
    { 2013,  7,  4, 3581884800 },
    { 2100,  2, 28, 6316444800 },
};

int 
main() {
    int i, ntests;

    ntests = sizeof(tests) / sizeof(*tests);
    for (i = 0; i < ntests; i++) {
        const struct test t = tests[i];

        {
            unsigned int n;
            int y, m, d;

            n = t.timestamp / 86400;
            dt_to_ymd(n, &y, &m, &d);
            if (t.year != y || t.month != m || t.day != d) {
                printf("dt_to_ymd(%u)\n", n);
                printf("  got: %.4d-%.2d-%.2d\n", y, m, d);
                printf("  exp: %.4d-%.2d-%.2d\n", t.year, t.month, t.day);
            }
        }
    }
    return 0;
}