与 min_element 和 max_element 一起使用 minmax_element 是否有任何效率优势？

Question

std::minmax_element : returns 一对，由指向最小元素的迭代器作为第一个元素和指向最大元素的迭代器作为第二个元素组成。

std::min_element : returns 指向 [first, last) 范围内最小元素的迭代器。

std::max_element : returns 指向 [first, last) 范围内最大元素的迭代器。

std::minmax_element是否使用完整列表的排序来实现？

处理 从 std::minmax_element 返回的对 的开销是否值得？

Answer 1

是的。您只在范围内迭代一次，而不是重复两次。

Answer 2

您不必担心 std::minmax_element 进行任何排序。它以遍历的确切方式离开范围。它更有效的原因是它可以在一次通过中同时找到最大值和最小值，而当分别查找最大值和最小值时，您必须进行两次完整遍历。

std::minmax_element 具有 max(floor(3/2(N−1)), 0) 的复杂性，其中 std::max_element 和 std::min_element 均为 max(N-1,0)，因此使用 [= 可减少约 25% 的操作11=]

还有一个区别，std::minmax_element 找到最后一个最大的元素，而 std::max_element 找到第一个最大的元素。

因此，如果您需要找到范围的最小值和最大值，那么您应该使用 std::minmax_element。如果您只需要最小值或最大值，那么您应该使用专用版本。使用即将推出的 C++17 标准和结构化绑定，处理来自 std::minmax_element 的 return 将变得更加容易。你将能够写

auto [min, max] = std::minmax_element(...);

现在该对的第一个元素存储在 min 中，第二个元素存储在 max 中。

Answer 3

std::minmax_element 复杂度：

At most max(floor(3/2(N−1)), 0) applications of the predicate, where N = std::distance(first, last).

std::min_element 复杂度（与 max_element 相同）：

Exactly max(N-1,0) comparisons, where N = std::distance(first, last).

忽略 max 和 floor，我们得到：

(N-1) * 2 vs 3/2 (N-1)

因此，通过使用 minmax_element，您可以使用 max_element + min_element 或更好的方式获得 3/4 需要的比较。

minmax_element 使用 < 运算符 ~~的传递性，它知道如果更新最小值则不需要比较最大值~~通过一次比较两个元素，即如果 a < b 那么我们只需要检查 min(a, current_min) 和 max(b, current_max)，反之亦然。

另外值得注意的是：

This algorithm is different from std::make_pair(std::min_element(), std::max_element()), not only in efficiency, but also in that this algorithm finds the last biggest element while std::max_element finds the first biggest element.

Answer 4

其他回答都不错。然而，我想补充一点关于 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!

然而，根据下面的评论，应该注意的是，当使用比较便宜的类型（或比较器）时，这种 "improved" 算法在现代处理器上往往会产生比原始版本更差的性能 -值得注意的是，范围超过 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=native、GCC 5.4 版编译）样本运行分别显示 min/max 692 毫秒和 minmax 组合 848 毫秒。运行s 之间当然存在一些差异，但这些值看起来很典型。

注意：

性能差异很小，不太可能成为实际程序中的主导因素；
差异取决于编译器优化；未来，结果很可能会逆转；
对于更复杂的数据类型（或者更确切地说，对于更复杂的比较器），结果可能会相反，因为在这种情况下，更少的比较可能会是一个显着的改进。
当样本数据是有序的而不是随机的（在下面的程序中将 v.push_back(r(gen)) 替换为 v.push_back(i)），性能非常不同：对于单独的min/max，大约 728 毫秒，而对于组合的 minmax，它下降到 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;
}

与 min_element 和 max_element 一起使用 minmax_element 是否有任何效率优势？

Is there any efficiency advantage in using minmax_element over min_element and max_element together?

c++

max

min