使用minmax_element比同时使用min_element和max_element有什么效率优势吗？

Question

使用minmax_element比同时使用min_element和max_element有什么效率优势吗？

c++maxmin

7

std::minmax_element：返回一个由最小元素迭代器作为第一个元素和最大元素迭代器作为第二个元素组成的 pair。

std::min_element：返回范围 [first,last) 中最小元素的迭代器。

std::max_element：返回范围 [first,last) 中最大元素的迭代器。

std::minmax_element 是否使用 对整个列表进行排序 来实现？

从 std::minmax_element 返回的 pair 处理开销值得吗？

- Saurav Sahu

4个回答

8

其他答案都很好。不过我想补充一下有关 minmax_element 如何工作的内容，这也有助于解释为什么它（通常）比分别运行 min_element 和 max_element 更好，并讨论一些特定情况下它表现不佳的情况。

如果我们考虑一个天真的实现，您将维护一个最大值和最小值（以及它们对应的迭代器），然后简单地遍历整个范围，将每个值与最小值和最大值进行比较，并根据需要调整其中一个。但是，这将给您带来总共 2N 次比较；虽然它可能比两次遍历列表要快（由于更好的局部性使用），但规范要求（大约）3/2 N 次比较。那怎么可能呢？

它通过处理对而不是单个项来工作。取范围中的前两个项目（＃0和＃1），我们可以比较它们并将最大值分配给 max-value，将最小值分配给 min-value。然后，我们比较下两个项目（＃3和＃4）以确定它们中哪一个更大；我们将较大的与 max-value 进行比较，并将较小的与 min-value 进行比较，并根据需要更新 max-value/min-value。然后，我们使用每个附加对（＃5和＃6，然后是＃7和＃8等）重复此过程。

因此，每个对都需要三次比较-彼此之间的比较，然后是与当前最大值的最高值和与当前最小值的最低值的比较。这将减少所需的比较次数为 3/2 N！

正如下面的评论所述，但是应该注意，当使用比较便宜的类型（或比较器）时，这种“改进”的算法在现代处理器上往往会产生更差的性能-特别是在 vector<int> 或类似的范围内：每个对的两个元素之间的比较具有不可预测的结果，导致处理器中的分支预测失败（尽管仅在数据被更或多或少随机排序的情况下才是如此）；当前编译器不总是将分支转换为条件传输，因为它们可能可以。此外，更复杂的算法更难以进行编译器矢量化。

理论上，我认为，C++ 库实现可以为原始（int 等）元素类型提供重载的 minmax_element 函数，其中使用默认比较器的天真算法。虽然标准规定了比较次数的限制，但是如果这些比较的效果不能被观察到，则实际计算的数量并不重要，只要时间复杂度相同（在这两种情况下都为 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 毫秒。当然，不同的运行之间会有一些变化，但这些值似乎是典型值。

请注意：

性能差异小到足以不太可能成为现实程序中的主导因素；
差异依赖于编译器优化；在将来，结果可能会反转；
对于更复杂的数据类型（或者更准确地说是针对更复杂的比较器），结果可能会反转，因为在这种情况下，较少的比较往往会带来显著的改进；
当样本数据是有序的而不是随机的时候（在下面的程序中将 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;
}

- davmac

2

有趣的事实：在现代处理器上，对于一个元素随机排列的vector<int>，那3N/2次比较所需的时间比进行朴素的2N次比较要长得多，这是因为分支预测的缘故。 - Marc Glisse

1

预测准确的分支非常便宜。你可以尝试各种技巧，但如果你想用标量代码和3n/2技巧打败朴素版本，我会感到惊讶。 - Marc Glisse

1

使用-fprofile-generate/-fprofile-use已经将运行时间缩短了30%。这些函数很难进行优化，因为它们返回的是位置而不是值。请注意，在向量化方面，2n版本比3n/2版本更容易（后者无论如何都没有好处，因为计算最小值和最大值需要2个操作）。 - Marc Glisse

@MarcGlisse和PeterCordes，谢谢。我觉得这真的很有趣。我已经将一些讨论编辑到答案中了；请随意进行进一步的编辑。 - davmac

1

@PeterCordes https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78151 是关于*min_element向量化被忽略的问题。 - Marc Glisse

显示剩余8条评论

6

是的。您只需要一次迭代范围，而不是两次。

- krzaq

好的，你的意思是内部实现维护两个标志：minimum_till_now和maximum_till_now，并且在完整遍历结束时返回它们吗？ - Saurav Sahu

是的，实际上使用你提到的另外两种算法来实现这个算法是没有意义的。话虽如此，请看NathanOliver的回答——差异也在于比较次数。 - krzaq

3

std::minmax_element 的时间复杂度：

最多对谓词进行 max(floor(3/2(N−1)), 0) 次应用，其中 N = std::distance(first, last)。

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

恰好进行 max(N-1,0) 次比较，其中 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)，反之亦然。

还值得注意的是：

这个算法与std::make_pair(std::min_element(), std::max_element())不同，不仅效率不同，而且该算法找到的是最后一个最大元素，而std::max_element找到的是第一个最大元素。

- sbabbi

你对“如果正在更新最小值，则不需要比较最大值”的提高效率的解释并不准确。如果这样做，它只会在极少数元素更新最小值时略微提高效率。相反，该函数采用不同的策略，在所有情况下都可以提高25％的效率（有关更多信息，请参见davmac的答案）。 - Marc van Leeuwen

@MarcvanLeeuwen 好的，没问题，正在更新答案。 - sbabbi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NathanOliver · Accepted Answer

不用担心 std::minmax_element 会进行任何排序。它会在遍历范围时始终保持原样。它更高效的原因是可以一次性找到最大值和最小值，在分别查找最大值和最小值时需要两次完整遍历。

std::minmax_element 的复杂度为 max(floor(3/2(N−1)), 0)，而 std::max_element 和 std::min_element 分别是 max(N-1,0)，所以使用 std::minmax_element 可以减少约25%的操作。

此外，std::minmax_element 找到的是最后一个最大元素，而 std::max_element 找到的是第一个最大元素。

因此，如果您需要找到范围内的最小值和最大值，则应使用 std::minmax_element。如果您只需要最小值或最大值，则应使用专门的版本。使用即将推出的C++17标准和结构化绑定处理从 std::minmax_element 返回的结果将变得更加容易。您将能够编写

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

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