优化的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实际上在某些项上多次调用它这个事实可能令人担忧。这是预期的，因为编译器不能猜测score是纯函数。

如果每个项目只调用一次argmin，我怎么能找到score呢？追忆是一种可能，还有什么吗？

我的目标是编写一个易于阅读的代码片段，在一个像在集合上调用std::min_element这样显而易见的梦世界中。

Answer 1

如user @liliscent所建议的那样，人们可以：

1. 生成一组预先计算过的分数，
2. 从中找出最低分数，
3. 并从最小得分的位置推断最小项的位置。

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

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

用现场演示。

Answer 2

这是一个你想做的函数--甚至超越了直观的“每个元素一次调用分数”，意识到没有比负无穷大更小的东西了！

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 3

如前所述，如果向量不是太大，您可以使用std::transform存储所有分数，然后应用std::min_element。

但是，如果您想要从“懒惰评估”中获益，并且仍然希望使用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);
            }
    });