与min_element和max_ELMENT一起使用相比,使用minmax_ALEMENT是否有任何效率优势?

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

具有 max(floor(3/2(N−1)), 0) 作为 std::max_element 和 std::min_element 每个 max(N-1,0) 因此,使用 std::minmax_element

还有一个区别是: std::minmax_element 查找最后一个最大元素,而 标准::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/2N比较。那怎么可能呢?

因此,每对需要三个比较-相互比较,然后最高值与当前最大值比较,最低值与当前最小值比较。这将所需的比较次数减少到3/2 N!

然而,根据下面的评论,应该注意的是,当使用比较便宜的类型(或比较器)时,这种“改进的”算法在现代处理器上往往比原始版本产生更差的性能,特别是在 vector<int> 或类似:每对元素之间的比较具有不可预测的结果,导致处理器中的分支预测失败(尽管这仅在数据或多或少随机排序的情况下才是正确的);当前的编译器并不总是像可能的那样将分支转换为条件转移。而且,编译器更难对更复杂的算法进行矢量化。

理论上,我认为C++库实现可以为 最小最大元素 函数,该函数使用原语的朴素算法( int 等)具有默认比较器的元素类型。虽然该标准规定了对比较次数的限制,但如果无法观察到这些比较的效果,则只要时间复杂度相同(即- O(N) 在两种情况下)。然而,虽然这可能会为随机排序的数据提供更好的性能,但在数据排序时可能会产生更差的性能。

考虑到以上所有内容,一个简单的测试用例(如下)显示了一个有趣的结果:对于随机排序的数据, 使用 最小元素 和 比使用 最小最大元素 . 然而对于分类数据, 最小最大元素 比使用 最小元素 和 max_element 分别地在我的系统(Haswell处理器)上,以下(用 gcc -O3 -std=c++11 -march=native ,GCC版本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;
}

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

std::minmax_element 复杂性:

谓词的最多max(floor(3/2(N1)),0)应用,其中N=std::距离(第一,最后)。

std::min_element 复杂性(与 max_element ):

正好是最大(N-1,0)比较,其中N=std::距离(第一个,最后一个)。

忽略 max 和 floor 我们得到:

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

minmax_element 你明白 3/4 您需要使用 max_element + min_element 或更好。

最小最大元素 < ,它知道如果它正在更新最小值,则不需要比较最大值 通过同时比较两个元素,即 a < b 那么我们只需要检查一下 min(a, current_min) 和 max(b, current_max) 反之亦然。

还值得注意的是:

该算法与std::make_pair(std::min_element(),std::,max_elements())的不同之处不仅在于效率,而且在于该算法查找最后一个最大元素,而std::max_element查找第一个最大元素。