所以“新(旧)大事”是 C++ 中的“无原始循环”。我正在尝试以这种方式编写代码,但似乎效率很低。是的,有些 STL 算法可以做任何事情,但它们似乎效率不高。
例如,我有一种情况,我想要一个指向节点数组中得分最高的节点的指针。确定该分数是一项代价高昂的浮点运算。所以我实现了STL算法版本并将其与原始循环进行了比较:
#include <cfloat>
#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>
static int counter;
class Node {
public:
auto Score() const -> double {
std::cout << "complex calculation\n";
counter++;
return 1;
}
};
int main()
{
std::array<Node, 10> nodes;
counter = 0;
Node const* nodePtr = std::max_element(std::cbegin(nodes), std::cend(nodes),
[](Node const& node1, Node const& node2) {
return node1.Score() < node2.Score();
});
std::cout << "algorithm count " << counter << std::endl;
counter = 0;
double maxScore = -FLT_MAX;
for (const auto& node : nodes) {
auto score = node.Score();
if (score > maxScore) {
maxScore = score;
nodePtr = &node;
}
}
std::cout << "raw loop count " << counter << std::endl;
}
对此进行评估,对于 STL 版本,昂贵的 Score 函数被评估了 18 次,而原始循环仅使用了 10 次评估......
我做错了吗,还是原始循环并没有那么糟糕?
编辑:
经过建议后user58697
cout 和静态计数器会阻止编译器优化,我更改了代码:
#include <cfloat>
#include <cmath>
#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>
template <typename T>
class Random {
private:
std::default_random_engine generator;
std::uniform_real_distribution<T> distribution;
public:
Random()
: generator()
, distribution(0.0, 1.0)
{}
auto operator()() {
return distribution(generator);
};
};
static Random<double> myRandom;
class Timer {
private:
std::chrono::high_resolution_clock::time_point startTime{};
public:
void Start() noexcept {
startTime = std::chrono::high_resolution_clock::now();
}
[[nodiscard]] auto ElapsedMs() const noexcept {
return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - startTime).count();
}
};
static Timer timer;
class Node {
private:
double val;
public:
Node() noexcept : val(myRandom()) {}
[[nodiscard]] auto Score() const noexcept {
auto score = std::sqrt(std::log(10.0 / val));
score = std::sin(score) / std::cos(score);
score = std::sqrt(std::sqrt(std::sqrt(std::sqrt(std::sqrt(score)))));
score = std::pow(score, 1000);
return score;
}
};
int main()
{
std::array<Node, 100000> nodes; // yeah, yeah... overloading the stack, I know
for (auto i = 0; i < 2; i++) {
timer.Start();
Node const* nodePtr = &*std::max_element(std::cbegin(nodes), std::cend(nodes),
[](Node const& node1, Node const& node2) {
return node1.Score() < node2.Score();
});
std::cout << "algorithm elapsed time " << timer.ElapsedMs() << std::endl;
timer.Start();
double maxScore = -FLT_MAX;
for (const auto& node : nodes) {
auto score = node.Score();
if (score > maxScore) {
maxScore = score;
nodePtr = &node;
}
}
std::cout << "raw loop count " << timer.ElapsedMs() << std::endl;
}
}
我运行循环两次以消除启动行为...第二次循环的结果(用 g++ 9.1 -O3 编译):
algorithm elapsed time 16
raw loop count 8 (<== I see I forgot to change "count" to "time" :P)
所以不是这样的。
编辑:
看到这个问题得到了点赞,人们还在关注。
自从提出这个问题后,C++20就发布了。 C++20 的范围库有一个特殊功能,可以在这里提供帮助,称为投影 http://www.modernescpp.com/index.php/projections-with-ranges.
IE。在这种情况下你可以使用std::ranges::max_element https://en.cppreference.com/w/cpp/algorithm/ranges/max_element甚至std::ranges::max https://en.cppreference.com/w/cpp/algorithm/ranges/max(旧的标准算法中缺少这一点)就像
Node const* node = &*std::ranges::max_element(nodes, {}, &Node::Score);
...
Node const& node = std::ranges::max(nodes, {}, &Node::Score);
然而,由于实现选择不使用缓存,投影并不是这里的解决方案。这Proj
投影函数被一次又一次地调用every的论点Comp
比较器功能。
(内部函数调用看起来像
return std::invoke(__comp, std::invoke(__proj, __a), std::invoke(__proj, __b)) ? __b : __a;
)