c++ - 优化的 argmin : an effective way to find an item minimizing a function

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 是 pure function .

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

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

Answer 1

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

但是，如果您想利用“懒惰求值”的好处，并且仍然想使用 C++ 的 STL，可以使用一些技巧来解决。

重点是 std::accumulate 可以被视为一般的 reduce 或 fold 操作(如 foldl 在 haskell )。使用 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);
            }
    });