我偶然发现了这个老问题,并认为我可以向其中添加一些新信息。托马斯·波宁( Thomas Pornin )写的唯一现有答案是一个很好的答案,我对此表示赞同。但是,我将其视为改进它的挑战。如果我们能以两倍的速度产生相同的答案会怎样?也许更快?
为了测试这项工作,我将 Thomas 的答案封装在一个函数中:
#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};
}
我试图改进它的基础是:
chrono 兼容的低级日期算法
上面的文章没有直接解决这种情况。但是,它确实详细描述了涉及日期操作的算法,甚至包括“一年中的一天”概念,尽管该概念与此问题中指定的概念不同:
在这个问题中,“一年中的一天”是基于 1 的计数,其中 1 月 1 日是一年的开始(1 月 1 日 == 第 1 天)。 chrono-compatible Low-Level Date Algorithms在算法中具有类似的“一年中的一天”概念,civil_from_days
但它是在 3 月 1 日之后的天数(3 月 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-compatible Low-Level Date Algorithms具有用于日期操作的有用且高效的算法。即使您必须将算法分开并重新组合它们,它们也很有用,如本例所示。这些算法的解释是为了让您能够将它们分开并在诸如此类的示例中重新应用它们。
<chrono>
可以非常灵活地测量非常快速的函数。比非常快快三倍仍然是一个不错的胜利。