Fast Time Struct от секунд

Я ищу самый быстрый способ определить компоненты даты для вектора временных меток 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;
}

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

Спасибо!


c date time vector ntp
person lukecampbell    schedule 27.06.2013    source источник
comment
Рассматривали ли вы распараллеливание цикла? Я просто выдвигаю гипотезу, но я думаю, что gmtime_r уже настолько быстр, насколько это возможно, оставаясь при этом безошибочным.   -  person Taylor Brandstetter    schedule 28.06.2013
comment
@TaylorBrandstetter Это то, что я сейчас пытаюсь сделать, когда пишу это. Я просто хочу посмотреть, знает ли кто-нибудь об элегантном алгоритме для этого. Распараллеливание — это следующий логический шаг с того места, где я сижу.   -  person lukecampbell    schedule 28.06.2013

Ответы (2)


arrow_upward
1
arrow_downward

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

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.

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

person chux - Reinstate Monica    schedule 27.06.2013

arrow_upward
1
arrow_downward

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

Я получил этот код из библиотеки date 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;
}
person chansen    schedule 04.07.2013