优化的 argmin：找到最小化函数的项目的有效方法

Question

假设我有一个项目集合和对它们的评分函数：

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

我想从该集合中找到得分最低的项目。一个简单的写法是：

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

但是如果 score 是一个计算量很大的函数，那么 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.

如何找到 argmin 但每个项目只调用一次 score？记忆化是一种可能性，还有别的吗？

我的 objective 是写一个易于阅读的代码片段，在梦幻世界中就像在集合上调用 std::min_element 一样明显。

Answer 1

这是一个函数，它可以满足您的需求——甚至超越了直觉 "call score exactly once per element" 意识到没有比负无穷大更小的东西了！

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

Answer 2

正如我在上面评论的那样，如果向量不是太大，可以先使用std::transform存储所有分数，然后应用std::min_element。

但是，如果您想利用 "lazy evaluation"，并且仍然想使用 C++ 的 STL，可以使用一些技巧来解决。

重点是std::accumulate可以看作是一般的reduce或fold操作（就像haskell中的foldl）。使用 C++17 的 std::tuple 语法糖，我们可以这样写：

    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 3

根据用户@liliscent 的建议，可以：

生成一组预先计算的分数，
从中找出最低分，
并从最小分数的位置推断最小化项的位置。

这是我对他们建议的解读：

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

有了live demo.

优化的 argmin：找到最小化函数的项目的有效方法

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

c++

algorithm

search

standard-library