can ranges min recalculations be avoided

Question

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?

Neocene

Memoize pattern maybe? – Chiles

according to cppreference it is only specified that there are n-1 comparisons, but how often the projection is called seems to be not specified. – Issy

Transducers (from Clojure) are also a good option for sequence algorithms that combine for example mapping and reduction. I found this implementation for C++ but haven't tried it: github.com/arximboldi/zug . Interesting alternative to some algorithms in the STL. – Dropwort

fyi meta.#286051 – Issy

Answer 1

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.

Sissel

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

It might not be easy for the ranges::min() algorithm to retrieve the output type of the function (or Lambda) passed to it as argument. Without the type, it won't be able to keep a copy of a value. – Neocene

@LudovicAubert: Sure it is: auto value = proj(*it); – Sissel

if you then want to use std::is_pod you need a type, not a value – Neocene

@LudovicAubert: Why would you want to use is_pod? That's deprecated and doesn't really mean all that much. Also, decltype(proj(*it)). – Sissel

how to tell if value is copyable ? – Neocene

@LudovicAubert: Maybe is_copy_assignable? – Sissel

Answer 2

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)

Neocene

idiomatic c++20: godbolt.org/z/TdTx7KP5W idiomatic c++23: godbolt.org/z/xrMboce4Y – Nasho