CODEWITHSUNDEEP
c++c++20minminimizationstd-ranges
Ludovic Aubert
Ludovic Aubert

Reputation: 10526

can ranges min recalculations be avoided

Goal is to minimize a function over a range of input values. Performance matters. Unfortunately, the ranges::min() algorithm recomputes the output for the live optimum over and over again.

It seems like the algorithm could cache the output value corresponding to the optimum, or am I missing something?

In this example, why does f(x=0) need to be called n times?

#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);
}

It outputs:

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

Is there a way to call ranges::min() in a more optimized way?

Upvotes: 5

Views: 117

Answers (2)

Ludovic Aubert
Ludovic Aubert

Reputation: 10526

There is always the option to compute all outputs first and then locate the min element. But it is a little less memory efficient.

#include <ranges>
#include <algorithm>
#include <vector>
#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);
    vector<int> costs(4);
    transform(ranges::begin(rg), ranges::end(rg), begin(costs), f);
    auto it = ranges::min_element(costs);
    int index = &*it - &costs[0];
}

It outputs:

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

Upvotes: 1

Nicol Bolas
Nicol Bolas

Reputation: 473537

Can ranges::min be implemented in a fashion such that it stores the projected object that it is currently testing against? Well, that would impose specific requirements on such an item. Namely, that you can overwrite it (if you find a smaller element, so that you can cache it in the same variable).

This is not currently a requirement of projection; the result simply has to be comparable with the comparison function. So to impose that would effectively make projection more strict.

Now, an implementation is allowed to cache the value if it so chooses, as projection functors are required to be pure. That is, if it detects that the value type from the projection is copyable, it can copy it. But that's a matter of quality of implementation, not a standard requirement.

Upvotes: 5

Related Questions