Optimized argmin: an effective way to find an item minimizing a function

Question

Let us say I've got a collection of items and a score function on them:

struct Item { /* some data */ };
std::vector<Item> items;
double score(Item);

I'd like to find the item from that collection whose score is the lowest. An easy way to write this is:

const auto argmin = std::min_element(begin(items), end(items), [](Item a, Item b) {
    return score(a) < score(b);
});

But if score is a heavy-to-compute function, the fact that std::min_element actually calls it multiple times on some items may be worrying. And this is expected because the compiler cannot guess score is a pure function.

How could I find argmin but with score being called only once per item? Memoization is one possibility, anything else?

My objective is to write a code snippet which is easy to read, in a dream world as obvious as calling std::min_element on the collection is.

Answer 1

As I commented above, if the vector is not too big, you can use std::transform to store all scores first, then apply std::min_element.

However, if you want to take benefit of "lazy evaluation", and still want to use C++'s STL, there are some tricks to work it out.

The point is std::accumulate can be regarded as a general reduce or fold operation (like foldl in haskell). With C++17's syntax sugar for std::tuple, we can write something like:

    auto [min_ind, _, min_value] = std::accumulate(items.begin(), items.end(),
        std::make_tuple(-1LU, 0LU, std::numeric_limits<double>::max()),
        [] (std::tuple<std::size_t, std::size_t, double> accu, const Item &s) {
            // up to this point, the index of min, the current index, and the last minimal value
            auto [min_ind, cur_ind, prev_min] = accu;
            double r = score(s);
            if ( r < prev_min ) {
                return std::make_tuple(cur_ind, cur_ind + 1, r);
            } else {
                return std::make_tuple(min_ind, cur_ind + 1, prev_min);
            }
    });

Answer 2

Here's a function that does what you want--even going beyond the intuitive "call score exactly once per element" by realizing that there's nothing smaller than negative infinity!

const Item* smallest(const std::vector<Item>& items)
{
    double min_score = items.empty() ? NAN : INFINITY;
    const Item* min_item = items.empty() ? nullptr : &*begin(items);
    for (const auto& item : items) {
        double item_score = score(item);
        if (item_score < min_score) {
            min_score = item_score;
            min_item = &item;
            if (item_score == -INFINITY) {
                break;
            }
        }
    }
    return min_item;
}