I stumbled across this old question, and thought I might be able to add some new information to it. The single existing answer as I write this by Thomas Pornin is a good answer, and I've upvoted it. However I've taken it as a challenge to better it. What if we could produce the same answer twice as fast? Maybe even faster?
To test this effort, I've wrapped Thomas' answer up in a function:
#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};
}
And my attempt to better it is based off of:
chrono-compatible Low-Level Date Algorithms
The above article does not address this situation directly. However it does go into detailed descriptions of the algorithms involved with date manipulations, and even includes a "day of year" concept, though that concept is different than what is specified in this question:
In this question "day of year" is a 1-based count with Jan 01 being the start of the year (Jan 1 == day 1). chrono-compatible Low-Level Date Algorithms has a similar "day of year" concept in the algorithm civil_from_days but it is days past Mar 01 (Mar 1 == day 0).
My thought is that I could pick bits and pieces from civil_from_days and create a new ymd_from_ydoy which did not need to iterate over the 12 months to find the desired result. Here is what I came up with:
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};
}
There are still branches, but fewer of them. To test both the correctness and performance of this alternative I wrote the following:
#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";
}
There are three loops in this test:
- Test that the two algorithms produce the same results over a range of +/- a million years.
- Time the first algorithm.
- Time the second algorithm.
It turns out that both algorithms are wicked fast ... a handful of nanoseconds on the iMac Core i5 I'm testing on. And thus the introduction of picoseconds to get a first-order estimate of fractional nanoseconds.
typedef duration<long long, pico> picoseconds;
I'd like to point out two things:
- How cool is it that we are starting to use picoseconds as a unit of measurement?
- How cool is it that
std::chrono makes it so easy to interoperate with picoseconds?
For me this test prints out (approximately):
8660ps
2631ps
Indicating that ymd_from_ydoy2 is approximately 3.3 times faster than ymd_from_ydoy1.
Hope this helps. Important things to get from this answer:
- chrono-compatible Low-Level Date Algorithms has useful and efficient algorithms for date manipulation. They can be useful even if you have to pick the algorithms apart and reassemble them, as in this example. The explanations of the algorithms are there to enable you to pick them apart and reapply them in examples such as this.
<chrono> can be very flexible in measuring very fast functions. Three times faster than very fast is still a good win.
