CODEWITHSUNDEEP
c++algorithmsearchstandard-library
YSC
YSC

Reputation: 40080

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

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.

Upvotes: 10

Views: 970

Answers (3)

John Zwinck
John Zwinck

Reputation: 249293

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

Upvotes: 3

YSC
YSC

Reputation: 40080

As suggested bu user @liliscent, one could:

  1. generate a collection of precalculated scores,
  2. find the minimum score from it,
  3. and infer the position of the minimizing item from the position of the minimum score.

This is my reading of their suggestion:

template<class InputIt, class Scoring>
auto argmin(InputIt first, InputIt last, Scoring scoring)
{
    using score_type = typename std::result_of_t<Scoring(typename std::iterator_traits<InputIt>::value_type)>;
    std::vector<score_type> scores(std::distance(first, last));
    std::transform(first, last, begin(scores), scoring);
    const auto scoremin = std::min_element(begin(scores), end(scores));
    return first + std::distance(begin(scores), scoremin);
}

With a live demo.

Upvotes: 1

llllllllll
llllllllll

Reputation: 16404

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

Upvotes: 3

Related Questions