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?
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.