Дата, Время - Секунды Разница


По тривиальным причинам, я решил пойти на дифференциации времени. Низкий, и вот, не имея никакого понятия, сколько нетривиальной задачей было стать.

Он был первоначально небольшой отклониться от проекта, который я делаю.

И, хотя производительность не является огромной проблемой вот код, который я разместил ниже, выполняет очень оптимально в сравнении с его альтернативой (как показано ниже). Это является предпочтительным, так как изначально это было использовано в в реальном времени программа, и без других изменений на высоком уровне алгоритма, стоимость повторного расчета длительности каждого кадра (до 60 кадров в секунду) создает значительное время выполнения пенальти.

Но то, что я ищу в моем решении, являются алгоритмические усовершенствования, не оптимизации (она работает более чем достаточно быстро). Например, удаление цикла for для расчета какие годы являются високосными (возможно, используя 365.242199 постоянная?).

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

long calculate_seconds_between(
    uint Y1, uint M1, uint D1, uint H1, uint m1, uint S1,
    uint Y2, uint M2, uint D2, uint H2, uint m2, uint S2
)
{
    bool invert = false;
    if (Y1 > Y2) {
        invert = true;
    } else if (Y1 == Y2) {
        if (M1 > M2) {
            invert = true;
        } else if (M1 == M2) {
            if (D1 > D2) {
                invert = true;
            } else if (D1 == D2) {
                if (H1 > H2) {
                    invert = true;
                } else if (H1 == H2) {
                    if (m1 > m2) {
                        invert = true;
                    } else if (m1 == m2 && S1 > S2) {
                        invert = true;
                    }
                }
            }
        }
    }

    if (invert) {
        std::swap(Y1, Y2);
        std::swap(M1, M2);
        std::swap(D1, D2);
        std::swap(H1, H2);
        std::swap(m1, m2);
        std::swap(S1, S2);
    }

    static const int month_days_sum[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
    const uint Y1_days = month_days_sum[M1 - 1];
    const uint Y2_days = month_days_sum[M2 - 1];
    int years_days = (Y2 - Y1) * 365;

    // Leap Years
    for (uint i = Y1 + 1; i < Y2;) {
        if (is_leap_year(i)) {
            ++years_days;
            i += 4;
        } else {
            ++i;
        }
    }

    const bool lY1 = is_leap_year(Y1) && (M1 < 2 || (M1 == 2 && D1 < 29));
    const bool lY2 = is_leap_year(Y2) && (M2 > 2 || (M2 == 2 && D2 > 28));

    if (Y1 == Y2) {
        if (lY1 && lY2) ++years_days;
    } else {
        if (lY1) ++years_days;
        if (lY2) ++years_days;
    }

    // Convert years to seconds
    const long years_seconds = years_days * 86400;

    // Time difference in seconds
    const long S1s = ((Y1_days + D1) * 86400) + (H1 * 3600) + (m1 * 60) + S1;
    const long S2s = ((Y2_days + D2) * 86400) + (H2 * 3600) + (m2 * 60) + S2;

    const long total = years_seconds + (S2s - S1s);

    if (invert) return -total;
    else return total;
}

Стандарт C++ Альтернатива Примечание: очень медленно, до (8000 / 35) 228x медленнее, чем выше.

time_t calculate_seconds_between2(
    const uint Y1, const uint M1, const uint D1, const uint H1, const uint m1, const uint S1, // YY/MM/DD HH:mm:SS
    const uint Y2, const uint M2, const uint D2, const uint H2, const uint m2, const uint S2
)
{
    time_t raw;
    time(&raw);

    struct tm t1, t2;

    gmtime_r(&raw, &t1);
    t2 = t1;

    t1.tm_year = Y1 - 1900;
    t1.tm_mon = M1 - 1;
    t1.tm_mday = D1;
    t1.tm_hour = H1;
    t1.tm_min = m1;
    t1.tm_sec = S1;

    t2.tm_year = Y2 - 1900;
    t2.tm_mon = M2 - 1;
    t2.tm_mday = D2;
    t2.tm_hour = H2;
    t2.tm_min = m2;
    t2.tm_sec = S2;

    time_t tt1, tt2;
    tt1 = mktime(&t1);
    tt2 = mktime(&t2);

    return (tt2 - tt1);
}

Как показано на блок тестирования, каждый день (кроме тестов на время) с 1990 до 2020 года была испытана против каждой даты от 1990 до 2020 года (Н^2) без сбоев, поэтому алгоритм оказывается корректным с точки зрения точности против ГНУ реализации на моей платформе.

Модульное тестирование кода: http://pastie.org/2933904

Эталонный код: http://pastie.org/2933893

С тегами с, как это едва ли далеко не полностью перенесены.



Комментарии
1 ответ

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

unsigned calculate_seconds_between2(unsigned Y1, unsigned M1, unsigned D1, unsigned H1, unsigned m1, unsigned S1,
unsigned Y2, unsigned M2, unsigned D2, unsigned H2, unsigned m2, unsigned S2)
{
// JSN = seconds since some epoch:
unsigned T1 = JSN(Y1, M1, D1, H1, m1, S1);
unsigned T2 = JSN(Y2, M2, D2, H2, m2, S2);
return T1>T2 ? T1-T2 : T2-T1;
}

Для секунд с начала эпохи, я бы, вероятно, использовать что-нибудь вроде нормальный номер дня по юлианскому календарю, но с более поздней эпохой (для уменьшения величин, а с ними и возможность переполнения), затем рассчитайте секунд в день, что-то вроде этого:

unsigned JSN(unsigned Y, unsigned M, unsigned D, unsigned H, unsigned m, unsigned S) {
static const int unsigned secs_per_day = 24 * 60 * 60;
return mJDN(Y-1900, M, D) * secs_per_day + H * 3600 + m * 60 + S;
}

Таким образом, остается только расчет изменен на jdn. Это не совсем прозрачный, но:

unsigned mJDN(unsigned Y, unsigned M, unsigned D) { 
return 367*Y - 7*(Y+(M+9)/12)/4 + 275*M/9 + D;
}

Эта формула с 1991 года Киев Пост Тома Ван Фландерна, с еще более изменен на jdn (т. е. даже более поздние эпохи).

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

unsigned time_diff(/* ...*/) { 
unsigned D1 = JDN(Y1, M1, D1);
unsigned D2 = JDN(Y2, M2, D2);

unsigned T1 = H1 * 3600 + m1 * 60 + S1;
unsigned T2 = H2 * 3600 + m2 * 60 + S1;

if (D1 == D2)
return T1>T2 ? T1-T2 : T2-T1;
return D1>D2 ? (D1-D2)*secs_per_day + T1-T2 : (D2-D1)*secs_per_day + T2-T1;
}

В частности, это позволит сделать его легче, чтобы избежать переполнения, при этом используя стандартный Юлианский день цифры. Это было бы полезно, если (например) вы используете стандартный Юлианский день цифры для других целей, так что вы хотели, чтобы повторно использовать эти стандартные процедуры.

Я не полный регрессионных тестов на точность (с точки больше об общей структуре, чем фактический код, реализующий его), но я достаточно уверен, что этот подход может привести к точным результатам. Быстрый тест скорости показывает, что она должна быть достаточно конкурентоспособными в этой области-по крайней мере, с компиляторами у меня удобный, это достаточно последовательно несколько быстрее. Даже если (например) я что-то напутала в расшифровке формулы Тома на C++, я сомневаюсь, что ремонт будет иметь существенного влияния на скорость.

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

Редактировать: как написано, это производит абсолютное значение разности. Исключения, что упрощает код что-то вроде этого:

int mJDN(int Y, int M, int D) { 
return 367*Y - 7*(Y+(M+9)/12)/4 + 275*M/9 + D;
}

int JSN(ull Y, ull M, ull D, ull H, ull m, ull S) {
static const int secs_per_day = 24 * 60 * 60;
return mJDN(Y-1900, M, D) * secs_per_day + H * 3600 + m * 60 + S;
}

int calculate_seconds_between3(int Y1, int M1, int D1, int H1, int m1, int S1,
int Y2, int M2, int D2, int H2, int m2, int S2)
{
int T1 = JSN(Y1, M1, D1, H1, m1, S1);
int T2 = JSN(Y2, M2, D2, H2, m2, S2);
return T2-T1;
}

5
ответ дан 28 ноября 2011 в 05:11 Источник Поделиться