我为大学班级编写了三种算法版本。
一个是蛮力,另一个是贪婪,最后一个是启发式。
我希望能够衡量每种算法需要花费多少时间。
我正在使用<chrono>
库来实现此目的
现在我的代码如下:
#include <iostream>
#include <chrono>
#include <sstream>
using namespace std;
string getTimeElapsed(long time1, const string &unit1, long time2 = 0, const string &unit2 = "") {
stringstream s;
s << time1 << " [" << unit1 << "]";
if (time2) s << " " << time2 << " [" << unit2 << "]";
return s.str();
}
int main() {
auto begin = chrono::system_clock::now();
// algorithm goes here
auto solution = /* can be anything */
auto end = chrono::system_clock::now();
auto diff = end - begin;
string timeElapsed;
auto hours = chrono::duration_cast<chrono::hours>(diff).count();
auto minutes = chrono::duration_cast<chrono::minutes>(diff).count();
if (hours) {
minutes %= 60;
timeElapsed = getTimeElapsed(hours, "h", minutes, "min");
} else {
auto seconds = chrono::duration_cast<chrono::seconds>(diff).count();
if (minutes) {
seconds %= 60;
timeElapsed = getTimeElapsed(minutes, "min", seconds, "s");
} else {
auto milliseconds = chrono::duration_cast<chrono::milliseconds>(diff).count();
if (seconds) {
milliseconds %= 1000;
timeElapsed = getTimeElapsed(seconds, "s", milliseconds, "ms");
} else {
auto microseconds = chrono::duration_cast<chrono::microseconds>(diff).count();
if (milliseconds) {
microseconds %= 1000;
timeElapsed = getTimeElapsed(milliseconds, "ms", microseconds, "μs");
} else {
auto nanoseconds = chrono::duration_cast<chrono::nanoseconds>(diff).count();
if (microseconds) {
nanoseconds %= 1000;
timeElapsed = timeElapsed = getTimeElapsed(microseconds, "μs", nanoseconds, "ns");
} else timeElapsed = getTimeElapsed(nanoseconds, "ns");
}
}
}
}
cout << "Solution [" << solution << "] found in " << timeElapsed << endl;
return 0;
}
您可以看到,堆积的if-else
子句看起来非常丑陋,您可以在此处看到一个模式:
if (timeUnit) {
timeElapsed = /* process current time units */
} else {
/* step down a level and do the same for smaller time units */
}
我想使该过程成为递归函数。
但是,我不知道该函数的参数是什么,因为chrono::duration
是模板结构(?)
此功能看起来像这样:
string prettyTimeElapsed(diff, timeUnit) {
// recursion bound condition
if (timeUnit is chrono::nanoseconds) return getTimeElapsed(timeUnit, "ns");
auto smallerTimeUnit = /* calculate smaller unit using current unit */
if (timeUnit) return getTimeElapsed(timeUnit, ???, smallerTimeUnit, ???);
else return prettyTimeElapsed(diff, smallerTimeUnit);
}
我正在考虑这样做:
auto timeUnits = {chrono::hours(), chrono::minutes(), ..., chrono::nanoseconds()};
然后,我可以将指针(甚至索引)带到时间单位,并将其传递给函数。
问题是我不知道如何概括这些结构。
CLion突出显示错误Deduced conflicting types (duration<[...], ratio<3600, [...]>> vs duration<[...], ratio<60, [...]>>) for initializer list element type
使用chrono
时,最好的一般建议是仅在绝对必要时才转义类型系统(使用.count()
)。这可能与C或某些不了解chrono的C ++库接口。在C ++ 20之前,这也意味着输出到流。
如果我们将自己保留在类型系统中,我们会得到很多不错的转换,这些转换总是]正确。
让我们更正问题中的代码以反映这一点:
#include <iostream> #include <chrono> #include <sstream> std::string getTimeElapsed(long time1, const std::string &unit1, long time2 = 0, const std::string &unit2 = "") { std::stringstream s; s << time1 << " [" << unit1 << "]"; if (time2) s << " " << time2 << " [" << unit2 << "]"; return s.str(); } int main() { auto begin = std::chrono::system_clock::now(); // algorithm goes here auto solution = "solution"; /* can be anything */ auto end = std::chrono::system_clock::now(); auto diff = end - begin; std::string timeElapsed{""}; // Let's make the typing and reading easier for us but requires C++14 using namespace std::chrono_literals; auto hours = std::chrono::duration_cast<std::chrono::hours>(diff); auto minutes = std::chrono::duration_cast<std::chrono::minutes>(diff % 1h); if (hours != 0h) { // We need to escape the type system to call getTimeElapsed timeElapsed = getTimeElapsed(hours.count(), "h", minutes.count(), "min"); } else { auto seconds = std::chrono::duration_cast<std::chrono::seconds>(diff % 1min); if (minutes != 0min) { timeElapsed = getTimeElapsed(minutes.count(), "min", seconds.count(), "s"); } else { auto milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(diff % 1s); if (seconds != 0s) { timeElapsed = getTimeElapsed(seconds.count(), "s", milliseconds.count(), "ms"); } else { auto microseconds = std::chrono::duration_cast<std::chrono::microseconds>(diff % 1ms); if (milliseconds != 0ms) { timeElapsed = getTimeElapsed(milliseconds.count(), "ms", microseconds.count(), "μs"); } else { auto nanoseconds = std::chrono::duration_cast<std::chrono::nanoseconds>(diff % 1us); if (microseconds != 0us) { timeElapsed = timeElapsed = getTimeElapsed(microseconds.count(), "μs", nanoseconds.count(), "ns"); } else timeElapsed = getTimeElapsed(nanoseconds.count(), "ns"); } } } } std::cout << "Solution [" << solution << "] found in " << timeElapsed << std::endl; return 0; }
现在我们会一直坚持[C0]。呼叫
chrono
尚不兼容getTimeElapsed
。
我并不完全满意,所以我们也支持chrono
中的duration
:
getTimeElapsed
我们需要
template <typename Duration1, typename Duration2> std::string getTimeElapsed(Duration1 time1, const std::string &unit1, Duration2 time2, const std::string &unit2) { std::stringstream s; s << time1.count() << " [" << unit1 << "]"; if (time2 != Duration2::zero()) s << " " << time2.count() << " [" << unit2 << "]"; return s.str(); } template <typename Duration1> std::string getTimeElapsed(Duration1 time1, const std::string &unit1) { std::stringstream s; s << time1.count() << " [" << unit1 << "]"; return s.str(); }
的两个版本,因为在最后一个getTimeElapsed
中,我们仅使用一个时间和单位参数对,这意味着我们不能满足两种else
类型的template
参数要求。现在代码看起来好多了(仅保留相关更改):
Duration
太好了!但是,我们仍然邀请用户将他们想要的任何内容发送到
... if (hours != 0h) { timeElapsed = getTimeElapsed(hours, "h", minutes, "min"); } else { auto seconds = std::chrono::duration_cast<std::chrono::seconds>(diff % 1min); if (minutes != 0min) { timeElapsed = getTimeElapsed(minutes, "min", seconds, "s"); } else { auto milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(diff % 1s); if (seconds != 0s) { timeElapsed = getTimeElapsed(seconds, "s", milliseconds, "ms"); } else { auto microseconds = std::chrono::duration_cast<std::chrono::microseconds>(diff % 1ms); if (milliseconds != 0ms) { timeElapsed = getTimeElapsed(milliseconds, "ms", microseconds, "μs"); } else { auto nanoseconds = std::chrono::duration_cast<std::chrono::nanoseconds>(diff % 1us); if (microseconds != 0us) { timeElapsed = timeElapsed = getTimeElapsed(microseconds, "μs", nanoseconds, "ns"); } else timeElapsed = getTimeElapsed(nanoseconds, "ns"); } } } } ...
,除非他们碰巧拥有getTimeElapsed
成员,否则将导致编译器错误。让我们限制一下.count()
:
template
我们不需要更改此代码。我相信这足以帮助您了解如何在更通用的上下文中使用
template <typename Rep1, typename Ratio1, typename Rep2, typename Ratio2> std::string getTimeElapsed(std::chrono::duration<Rep1, Ratio1> time1, const std::string &unit1, std::chrono::duration<Rep2, Ratio2> time2, const std::string &unit2) { std::stringstream s; s << time1.count() << " [" << unit1 << "]"; if (time2 != time2.zero()) s << " " << time2.count() << " [" << unit2 << "]"; return s.str(); } template <typename Rep, typename Ratio> std::string getTimeElapsed(std::chrono::duration<Rep, Ratio> time1, const std::string &unit1) { std::stringstream s; s << time1.count() << " [" << unit1 << "]"; return s.str(); }
,这是您遇到的子问题。
现在,我们可以开始解决您的问题,我认为(通过阅读注释)实际上是“我如何整理嵌套的std::chrono::duration
语句并仅打印出前两个非零单位。”
这并不像它第一次出现那样简单。我认为,递归很少是答案。将其视为单元类型的循环也是对其的过度设计,您将需要编写一些代码以从元组获取当前类型的索引,将其增加一个,然后使用该代码对相同的元组进行索引以获得更高分辨率的下一个单元。然后,当所有事情都说完之后,您[if
如下所示:getTimeElapsed
将总经过时间作为std::string getTimeElapsed(std::chrono::nanoseconds elapsed, size_t maxUnits = 2) { using namespace std::chrono_literals; std::ostringstream formatted(""); int usedUnits{}; auto hours = std::chrono::duration_cast<std::chrono::hours>(elapsed); if (hours != 0h) { formatted << hours.count() << " [h] "; ++usedUnits; } auto minutes = std::chrono::duration_cast<std::chrono::minutes>(elapsed % 1h); if (minutes != 0min) { formatted << minutes.count() << " [min] "; ++usedUnits; } auto seconds = std::chrono::duration_cast<std::chrono::seconds>(elapsed % 1min); if (seconds != 0min && usedUnits != maxUnits) { formatted << seconds.count() << " [s] "; ++usedUnits; } auto milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(elapsed % 1s); if (milliseconds != 0ms && usedUnits != maxUnits) { formatted << milliseconds.count() << " [ms] "; ++usedUnits; } auto microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed % 1ms); if (microseconds != 0us && usedUnits != maxUnits) { formatted << microseconds.count() << " [us] "; ++usedUnits; } auto nanoseconds = std::chrono::duration_cast<std::chrono::nanoseconds>(elapsed % 1us); if (nanoseconds != 0us && usedUnits != maxUnits) { formatted << nanoseconds.count() << " [us] "; ++usedUnits; } return formatted.str(); }
(您已经从std::chrono::nanoseconds
中获得),并将其传递到end - begin
。现在,我们进行与以前相同的计算以获得组件单位,但也跟踪我们已经计算了多少个单位。如果getTimeElapsed
为1'000'000'000ns,则结果为“ 1 [s]”;如果elapsed
为1'234'568ns,则结果为“ 1 [ms] 234 [us]”。有尾随空格,但我将留给您修复。
这也意味着我们不再需要以前重构的elapsed
,但我添加了它们以显示在整个重构过程中的思考过程。最终程序如下所示:
template
如果您想更进一步,并且永远不需要逃避类型系统,那么我建议您浏览#include <chrono> #include <iostream> #include <sstream> std::string getTimeElapsed(std::chrono::nanoseconds elapsed, size_t maxUnits = 2) { using namespace std::chrono_literals; std::ostringstream formatted(""); int usedUnits{}; auto hours = std::chrono::duration_cast<std::chrono::hours>(elapsed); if (hours != 0h) { formatted << hours.count() << " [h] "; ++usedUnits; } auto minutes = std::chrono::duration_cast<std::chrono::minutes>(elapsed % 1h); if (minutes != 0min) { formatted << minutes.count() << " [min] "; ++usedUnits; } auto seconds = std::chrono::duration_cast<std::chrono::seconds>(elapsed % 1min); if (seconds != 0min && usedUnits != maxUnits) { formatted << seconds.count() << " [s] "; ++usedUnits; } auto milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(elapsed % 1s); if (milliseconds != 0ms && usedUnits != maxUnits) { formatted << milliseconds.count() << " [ms] "; ++usedUnits; } auto microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed % 1ms); if (microseconds != 0us && usedUnits != maxUnits) { formatted << microseconds.count() << " [us] "; ++usedUnits; } auto nanoseconds = std::chrono::duration_cast<std::chrono::nanoseconds>(elapsed % 1us); if (nanoseconds != 0us && usedUnits != maxUnits) { formatted << nanoseconds.count() << " [us] "; ++usedUnits; } return formatted.str(); } int main() { auto begin = std::chrono::system_clock::now(); // algorithm goes here auto solution = "solution"; /* can be anything */ auto end = std::chrono::system_clock::now(); auto diff = end - begin; using namespace std::chrono_literals; std::cout << "Solution [" << solution << "] found in " << getTimeElapsed(1'234'567ns) << std::endl; return 0; }
库。该库是C ++ 20中新Howard Hinnant'sdate
功能的基础,并将字符串格式引入表中。只需以适合您的任何方式从库中包含date
,然后按如下所示修改chrono
:
date.h
使用与以前相同的值,结果将是:“ 1ms 234us”为1'234'567ns。