优化的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

正如用户 @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);
}

通过现场演示。