如何避免ranges::min重复计算？C++性能优化技术问询

需求是在输入值范围内最小化某个函数，性能至关重要。但ranges::min算法会反复重新计算当前最优值的输出结果。

似乎该算法可以缓存最优值对应的输出，是否存在我未考虑到的点？

在以下示例中，为何f(x=0)需要被调用n次？

#include <ranges>
#include <algorithm>
#include <stdio.h>
using namespace std;

int main()
{
    auto f=[](int x){
        printf("calling f(x=%d)\n", x);
        return x*x;
    };
    auto rg = views::iota(0,4);
    int x1 = ranges::min(rg, {}, f);
}

程序输出：

calling f(x=0)
calling f(x=1)
calling f(x=0)
calling f(x=2)
calling f(x=0)
calling f(x=3)

是否存在更优化的ranges::min调用方式？

原因分析 #

ranges::min（即std::ranges::min）的设计逻辑是每次比较都会重新调用投影函数，C++标准并未要求该算法缓存投影后的结果。它的执行流程大致如下：

• 取出第一个元素，调用投影函数得到对应值
• 遍历后续每个元素，调用投影得到当前元素的值，再与当前最优元素的投影值比较
• 但每次比较时，它会重新调用投影函数获取当前最优元素的值，而非缓存第一次的计算结果

在你的示例中，当x=0成为当前最优元素后，每遇到下一个元素（1、2、3），都会重新调用f(0)来和f(1)、f(2)、f(3)比较，这就导致了重复调用。

优化方案 #

1. 优先使用ranges::min_element #

std::ranges::min_element的行为与ranges::min不同：它会遍历范围，对每个元素仅调用一次投影函数，同时记录当前最优元素的迭代器，后续比较时直接使用已缓存的投影结果，无需重复调用。

修改后的代码：

#include <ranges>
#include <algorithm>
#include <stdio.h>
using namespace std;

int main()
{
    auto f=[](int x){
        printf("calling f(x=%d)\n", x);
        return x*x;
    };
    auto rg = views::iota(0,4);
    auto it = ranges::min_element(rg, {}, f);
    int x1 = *it;
}

输出结果：

calling f(x=0)
calling f(x=1)
calling f(x=2)
calling f(x=3)

每个元素的投影函数仅被调用一次，完全避免了重复计算，这是最简洁高效的解决方案。

2. 预计算投影结果并配对原元素 #

如果因某些原因必须使用ranges::min，可以提前将所有元素的投影结果与原元素配对，物化后再查找最小值，确保投影仅计算一次：

#include <ranges>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;

int main()
{
    auto f=[](int x){
        printf("calling f(x=%d)\n", x);
        return x*x;
    };
    auto rg = views::iota(0,4);
    // 生成原元素与投影结果的配对视图
    auto paired_view = rg | views::transform([&](int x) { return make_pair(x, f(x)); });
    // 物化视图为容器，避免惰性求值导致的重复计算
    vector<pair<int, int>> paired_elements(paired_view.begin(), paired_view.end());
    // 基于投影结果找到对应的原元素
    auto min_pair = ranges::min(paired_elements, {}, &pair<int, int>::second);
    int x1 = min_pair.first;
}

这个版本的输出同样每个f(x)仅调用一次，通过预计算避免了重复调用。

总结 #

当投影函数计算成本较高、性能至关重要时，优先选择std::ranges::min_element，它天然避免了投影函数的重复调用。若必须使用ranges::min，则通过预计算投影结果并配对原元素的方式优化。

内容的提问来源于stack exchange，提问作者Ludovic Aubert