std::minmax_element :返回一对由迭代器组成的对,作为第一个元素的最小元素和作为第二个元素的最大元素的迭代器.
std::min_element :将迭代器返回到[first,last]范围内的最小元素.
std::max_element :将迭代器返回到[first,last]范围内的最大元素.
是否std::minmax_element使用完整列表的排序来实现这一目标？
被处理的开销恢复对来自std::minmax_element足够值得？
Nat*_*ica 13
您不必担心std::minmax_element进行任何排序.它以精确的方式离开范围.它更有效的原因是它可以在单个通道中找到最大值和最小值,而当分别查找最大值和最小值时,您必须执行两次完整遍历.
std::minmax_element具有复杂性的max(floor(3/2(N?1)), 0)地方std::max_element和std::min_element每个都是max(N-1,0)如此,它使用的操作减少了约25%std::minmax_element
std::minmax_element找到最大的元素同时std::max_element找到第一个最大的元素也有区别.
因此,如果您需要找到范围的最小值和最大值,那么您应该使用std::minmax_element.如果您只需要最小值或最大值,则应使用专用版本.使用std::minmax_element即将推出的C++ 17标准和结构化绑定,处理返回将变得更加容易.你将能够写作
auto [min, max] = std::minmax_element(...);
现在该对的第一个元素存储在其中min,第二个元素存储在其中max.
其他答案都很好.我想补充一点关于minmax_element必然如何工作,但这也有助于解释为什么它(通常)比运行min_element和max_element单独工作更好,并讨论一些不能更好的特定情况.
如果我们考虑一个简单的实现,你将保持最大值和最小值(及其相应的迭代器)并简单地遍历范围,将每个值与最小值和最大值进行比较并根据需要进行调整.但是,这将为您提供总共2N的比较; 虽然它可能比在列表中迭代两次(由于更好地使用局部性)更好地执行,但规范要求(大致)3/2 N比较.那怎么可能呢？
它通过处理对而不是单个项来工作.取范围(#0和#1)中的前两项,我们可以比较它们并将最大值分配给最大值,将最小值分配给最小值.然后,我们比较接下来的两个项目(#3和#4)来决定哪个项目更大; 我们将较大的值与最大值进行比较,将较小的值与最小值进行比较,并根据需要更新max-value/min-value.然后我们用另外一对(#5和#6,然后#7和#8等)重复这个过程.
因此,每对需要进行三次比较 - 相互之间,然后是当前最大值的最高值,最低值是当前最小值.这减少了3/2 N所需的比较次数!
然而,根据下面的评论,应该注意的是,当使用比较便宜的类型(或比较器)时,这种"改进的"算法在现代处理器上的性能往往比天真版本更差 - 特别是在范围超过vector<int>或类似:每对中两个元素之间的比较具有不可预测的结果,导致处理器中的分支预测失败(尽管只有在数据或多或少随机排序时才会出现这种情况); 当前的编译器并不总是将分支转换为条件转移,因为它们可能.此外,编译器更难以矢量化更复杂的算法.
理论上,我认为,C++库实现可以为minmax_element函数提供重载,该函数使用原始(int等)元素类型的朴素算法和默认比较器.虽然标准强制要求比较次数,但如果无法观察到这些比较的影响,那么实际计算的数量并不重要,只要时间复杂度相同(O(N)在两种情况下都是如此).但是,虽然这可能会在随机排序的数据中提供更好的性能,但在订购数据时可能会产生更差的性能.
考虑到上述所有情况,一个简单的测试用例(下面)显示了一个有趣的结果:对于随机排序的数据,使用min_element和max_element单独使用可能比使用稍快一些minmax_element.但是,对于排序数据,minmax_element比使用min_element和max_element单独更快.在我的系统(Haswell处理器)下面(用gcc -O3 -std=c++11 -march=nativeGCC版本5.4 编译),样品运行分别显示692毫秒的最小/最大值和848的最小值组合.当然,运行之间存在一些差异,但这些值似乎很典型.
注意:
v.push_back(r(gen))与v.push_back(i)在下面的程序)的性能是非常不同:对单独最小/最大,它的周围728毫秒,而对于组合极大极小,它下降到246毫秒.代码:
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
constexpr int numEls = 100000000;
void recresult(std::vector<int> *v, int min, int max)
{
// Make sure the compiler doesn't optimize out the values:
__asm__ volatile (
""
:
: "rm"(v), "rm"(min), "rm"(max)
);
}
int main(int argc, char **argv)
{
using namespace std;
std::mt19937 gen(0);
uniform_int_distribution<> r(0, 100000);
vector<int> v;
for (int i = 0; i < numEls; i++) {
v.push_back(r(gen));
}
// run once for warmup
int min = *min_element(v.begin(), v.end());
int max = *max_element(v.begin(), v.end());
recresult(&v, min, max);
// min/max separately:
{
auto starttime = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 5; i++) {
int min = *min_element(v.begin(), v.end());
int max = *max_element(v.begin(), v.end());
recresult(&v, min, max);
}
auto endtime = std::chrono::high_resolution_clock::now();
auto millis = std::chrono::duration_cast<std::chrono::milliseconds>(endtime - starttime).count();
cout << "min/max element: " << millis << " milliseconds." << endl;
}
// run once for warmup
auto minmaxi = minmax_element(v.begin(), v.end());
recresult(&v, *(minmaxi.first), *(minmaxi.second));
// minmax together:
{
auto starttime = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 5; i++) {
minmaxi = minmax_element(v.begin(), v.end());
recresult(&v, *(minmaxi.first), *(minmaxi.second));
}
auto endtime = std::chrono::high_resolution_clock::now();
auto millis = std::chrono::duration_cast<std::chrono::milliseconds>(endtime - starttime).count();
cout << "minmax element: " << millis << " milliseconds." << endl;
}
return 0;
}