Я наткнулся на этот старый вопрос и подумал, что смогу добавить к нему новую информацию. Единственный существующий ответ, когда я пишу это Томас Порнин , является хорошим ответом, и я проголосовал за него. Однако я принял это как вызов, чтобы улучшить это. Что если бы мы могли выдать один и тот же ответ в два раза быстрее? Может быть, даже быстрее?
Чтобы проверить это, я завернул ответ Томаса в функцию:
#include <tuple>
std::tuple<int, int, int>
ymd_from_ydoy1(int year, int day_of_year)
{
static const int month_len[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int leap = (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0);
int day_of_month = day_of_year;
int month;
for (month = 0; month < 12; month ++) {
int mlen = month_len[month];
if (leap && month == 1)
mlen ++;
if (day_of_month <= mlen)
break;
day_of_month -= mlen;
}
return {year, month, day_of_month};
}
И моя попытка улучшить это основана на:
хроносовместимые алгоритмы дат низкого уровня
Приведенная выше статья не касается этой ситуации напрямую. Однако в нем подробно рассматриваются алгоритмы, связанные с манипуляциями с датами, и даже содержится понятие «день года», хотя это понятие отличается от того, что указано в этом вопросе:
В этом вопросе "день года" - это подсчет, основанный на 1, где 01 января - начало года (1 января == день 1). хроносовместимые алгоритмы дат низкого уровня имеет аналогичную концепцию "день года" в алгоритме civil_from_days, но это дни после 01 марта (1 марта == день 0) .
Я думал, что я могу выбрать биты и кусочки из civil_from_days и создать новый ymd_from_ydoy, который не нужно повторять в течение 12 месяцев, чтобы найти желаемый результат. Вот что я придумал:
std::tuple<int, int, int>
ymd_from_ydoy2(int year, int day_of_year)
{
int leap = (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0);
if (day_of_year < 60 + leap)
return {year, day_of_year/32, day_of_year - (day_of_year/32)*31};
day_of_year -= 60 + leap;
int mp = (5*day_of_year + 2)/153;
int day_of_month = day_of_year - (153*mp+2)/5 + 1;
return {year, mp + 2, day_of_month};
}
Есть еще ветви, но их меньше. Чтобы проверить правильность и производительность этой альтернативы, я написал следующее:
#include <iostream>
#include <chrono>
#include <cassert>
template <class Int>
constexpr
bool
is_leap(Int y) noexcept
{
return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
constexpr
unsigned
last_day_of_month_common_year(unsigned m) noexcept
{
constexpr unsigned char a[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
return a[m-1];
}
template <class Int>
constexpr
unsigned
last_day_of_month(Int y, unsigned m) noexcept
{
return m != 2 || !is_leap(y) ? last_day_of_month_common_year(m) : 29u;
}
int
main()
{
using namespace std;
using namespace std::chrono;
typedef duration<long long, pico> picoseconds;
picoseconds ps1{0};
picoseconds ps2{0};
int count = 0;
const int ymax = 1000000;
for (int y = -ymax; y <= ymax; ++y)
{
bool leap = is_leap(y);
for (int doy = 1; doy <= 365 + leap; ++doy, ++count)
{
auto d1 = ymd_from_ydoy1(y, doy);
auto d2 = ymd_from_ydoy2(y, doy);
assert(d1 == d2);
}
}
auto t0 = high_resolution_clock::now();
for (int y = -ymax; y <= ymax; ++y)
{
bool leap = is_leap(y);
for (int doy = 1; doy <= 365 + leap; ++doy)
{
auto d1 = ymd_from_ydoy1(y, doy);
auto d2 = ymd_from_ydoy1(y, doy);
assert(d1 == d2);
}
}
auto t1 = high_resolution_clock::now();
for (int y = -ymax; y <= ymax; ++y)
{
bool leap = is_leap(y);
for (int doy = 1; doy <= 365 + leap; ++doy)
{
auto d1 = ymd_from_ydoy2(y, doy);
auto d2 = ymd_from_ydoy2(y, doy);
assert(d1 == d2);
}
}
auto t2 = high_resolution_clock::now();
ps1 = picoseconds(t1-t0)/(count*2);
ps2 = picoseconds(t2-t1)/(count*2);
cout << ps1.count() << "ps\n";
cout << ps2.count() << "ps\n";
}
В этом тесте три цикла:
- Проверьте, что два алгоритма дают одинаковые результаты в диапазоне +/- миллиона лет.
- Время первого алгоритма.
- Время второй алгоритм.
Оказывается, оба алгоритма работают быстро ... несколько наносекунд на iMac Core i5, на котором я тестирую. И, следовательно, введение пикосекунд для получения оценки первого порядка дробных наносекунд.
typedef duration<long long, pico> picoseconds;
Я бы хотел отметить две вещи:
- Как здорово, что мы начинаем использовать пикосекунды в качестве единицы измерения?
- Как здорово, что
std::chrono позволяет так легко взаимодействовать с пикосекундами?
Для меня этот тест распечатывает (приблизительно):
8660ps
2631ps
Указывает, что ymd_from_ydoy2 примерно в 3,3 раза быстрее, чем ymd_from_ydoy1.
Надеюсь, это поможет. Важные вещи, которые можно получить из этого ответа:
- хроносовместимые низкоуровневые алгоритмы даты имеет полезные и эффективные алгоритмы для манипуляции датами. Они могут быть полезны, даже если вам нужно выделить алгоритмы и собрать их, как в этом примере. Объяснение алгоритмов приведено здесь, чтобы позволил вам выделить их и повторно применить в примерах, подобных этому.
<chrono> может быть очень гибким в измерении очень быстрых функций. В три раза быстрее, чем очень быстро, все еще хорошая победа.