使用std :: min_element()时保存函数求值 [英] Saving function evaluations while using std::min_element()

问题描述

假设给定了一个2D点向量，并且期望找到的

Suppose you are given a vector of 2D points and are expected to find the point with the least Euclidean norm.

这些点以 std :: vector< point_t>的形式提供.点，其中包含以下 typedef std :: pair< double，double>point_t .可以使用

The points are provided as std::vector<point_t> points whith the following typedef std::pair<double, double> point_t. The norm can be calculated using

double norm(point_t p)
{
    return pow(p.first, 2) + pow(p.second, 2);
}

我自己编写循环，我将执行以下操作:

Writing the loop myself I would do the following:

auto leastPoint = points.cend();
auto leastNorm = std::numeric_limits<double>::max();
for (auto iter = points.cbegin(), end = points.cend(); iter != end; ++iter)
{
    double const currentNorm = norm(*iter);
    if (currentNorm < leastNorm)
    {
        leastNorm = currentNorm;
        leastPoint = iter;
    }
}

但是应该使用STL算法而不是浪费自己的循环，所以我很想了解以下内容:

But one should use STL algorithms instead of wirting one's own loops, so I'm tempted to to the following:

auto const leastPoint = std::min_element(points.cbegin(), points.cend(),
    [](point_t const lhs, point_t const rhs){ return norm(lhs) < norm(rhs); });

但是有一个警告:如果 n = points.size()，则第一个实现需要对 norm()进行 n 个评估，但是第二种实现需要 2n-2 评估.(至少使用使用这种可能的实现方式)

But there is a caveat: if n = points.size() then the first implementation needs n evaluations of norm(), but the second implementation needs 2n-2 evaluations. (at least if this possible implementation is used)

所以我的问题是，是否有任何STL算法可以找到这一点，但仅对 norm()进行 n 个评估?

So my question is if there exists any STL algorithm with which I can find that point but with only n evaluations of norm()?

注释:

• 我知道big-Oh的复杂度是相同的，但后者仍然会导致两倍的评估次数
• 创建一个单独的矢量并在其中填充距离似乎只是为了启用STL算法而过大的杀伤力-对此有不同的看法吗?
• 实际上，我需要对该向量元素进行迭代以消除这一点.

推荐答案

这是范围工作组正在考虑添加范围达到标准，这可能允许采用更实用的管道方法，例如无需临时存储即可转换为min_element.

This is the sort of problem that boost::transform_iterator from the boost iterator library is designed to solve. There are limitations with the decorated iterator approach however and the C++ standards committee Ranges working group is looking into adding ranges to the standard which would potentially allow for a more functional approach of piping e.g. a transform to a min_element without needing temporary storage.

埃里克·尼布勒(Eric Niebler)在其博客上有一些关于范围的有趣帖子.

Eric Niebler has some interesting posts on ranges at his blog.

不幸的是，考虑到通常实现min_element的方式，transform_iterator并不能完全解决您的问题-每个比较都取消了两个迭代器的引用，因此您的函数最终仍然会被不必要地调用.您可以使用boost iterator_adaptor来实现类似"caching_transform_iterator"的方法，该方法可以避免在每次取消引用时重新计算，但对于norm()这样的方法可能会过大.如果您要进行更昂贵的计算，这可能是一种有用的技术.

Unfortunately transform_iterator doesn't quite solve your problem given the way min_element is typically implemented - both iterators are dereferenced for each comparison so your function will still end up getting called more often than necessary. You could use the boost iterator_adaptor to implement something like a 'caching_transform_iterator' which avoids recomputing on each dereference but it would probably be overkill for something like norm(). It might be a useful technique if you had a more expensive computation though.

这篇关于使用std :: min_element()时保存函数求值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！