Поиск лучшего элемента через stl/boost алгоритм

[kamre]

Задача простая и довольно типичная:
 - имеется последовательность элементов (может быть контейнер, пара итераторов, ...)
 - есть нетривиальный алгоритм для оценки элементов, результат представляется в виде значения типа double,
 - нужно найти элемент (его индекс/итератор) с максимальным значением оценки.

По сути нужно применить к каждому элементу алгоритм оценки и выбрать тот, у которого оценка максимальная.
Алгоритм для оценки сложный и вызывать его несколько раз для одного и того же элемента неэффективно.

Как можно эту простую задачу решить через алгоритмы в stl/boost чтобы не писать каждый раз вручную цикл наподобие такого:

Код:

#include <vector>
#include <iostream>

struct Point
{
    double x, y, z;
};

double dot(const Point& a, const Point& b)
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

int main()
{
    // data to process
    std::vector<Point> points = {
        {0, 0, 0},
        {1, 2, 3},
        {-1, -2, 5}
    };

    // context for cost function
    Point dir{0, 1, 0};

    // cost function is lambda wich captures some context
    // computationally expensive should not be called several times for same element
    auto cost = [&](const Point& p) { return dot(dir, p); };

    // we need to find index of point with maximal cost
    size_t index = 0;
    double maxCost = cost(points[index]);
    for (size_t i = 0; i < points.size(); ++i)
    {
        double c = cost(points[i]);
        if (maxCost < c)
        {
            maxCost = c;
            index = i;
        }
    }
    std::cout << "Index of point with maximal cost: " << index << std::endl;

    // how can this be written with stl/boost algorithms?
}

?

Алгоритм std::max_element не подходит сразу, т.к. требует предикат для сравнения и будет несколько раз вызывать функцию оценки для одного и того же элемента.

Попробовал также boost::range, там есть boost::adaptors::transformed, но в него не получается передавать lambda, которая захватывает контекст. Оборачивать такую lambda в std::function - опять же потеря производительности, насколько я понимаю.

Так чем можно заменить простой цикл с поиском лучшего элемента?

[Пантер]

> Алгоритм std::max_element не подходит сразу, т.к. требует предикат для сравнения и будет несколько раз вызывать функцию оценки для одного и того же элемента.

Что тебе мешает закешировать в предикате?

[kamre]

Что тебе мешает закешировать в предикате?

Что именно закешировать? Одно значение только? Все равно придется сравнивать с двумя аргументами предиката, это лишняя работа.

Меня бы устроил вариант через boost::range типа такого:

Код:

    auto iter = boost::max_element(points | boost::adaptors::transformed(cost));

Простая и понятная запись, но оно не работает с lambda.

[qate]

Что тебе мешает закешировать в предикате?

Что именно закешировать? Одно значение только? Все равно придется сравнивать с двумя аргументами предиката, это лишняя работа.

наверно имелось ввиду закэшировать в мапе QHash<Point, double> произведенные расчеты, тогда для того же Point расчет уже выполнен

[m_ax]

Да тут, наверное, проще свой qmax_element написать:

Код

C++ (Qt)
template <class It,  class UnaryFunction>
It qmax_element(It first, It last, UnaryFunction f)
{
    auto max = f(*first);
    It it = first++;
 
    for (; first != last; ++first)
    {
        auto val = f(*first);
        if (val > max)
        {
            max = val;
            it = first;
        }
    }
    return it;
}
 

Меня бы устроил вариант через boost::range

А в чём там выйгрышь? Он ведь тоже использует std::max_element в конечном счёте..
https://www.boost.org/doc/libs/1_56_0/boost/range/algorithm/max_element.hpp

[kamre]

Да тут, наверное, проще свой qmax_element написать:

Вот у меня такое же мнение сложилось, что придется самому написать. Странно, что такая простая задача комбинацией готовых алгоритмов не решается.

А в чём там выйгрышь? Он ведь тоже использует std::max_element в конечном счёте..

Да, boost::range не подходит в таком случае.

[m_ax]

Странно, что такая простая задача комбинацией готовых алгоритмов не решается.

Не, в принципе, решается через тот же std::max_element, но это на любителя:

Код

C++ (Qt)
    std::vector<int> v = {21, 3434222, 3, -10, -4, 101, 5};
 
    auto max = cost(v[0]);
 
    auto it = std::max_element(v.begin(), v.end(), [&max](int, int x)->bool
    {
        auto val = cost(x);
        bool res = val > max;
        if (res)
            max = val;
 
        return res;
    });
 

[Igors]

Странно, что такая простая задача комбинацией готовых алгоритмов не решается.

Я этому давно не удивляюсь. Простецкий for часто оказывается лучшим решением. Хороших, полезных вещей в std::algorithm мало, основная масса так - написать вумную соплю чтобы было на 1-2 строки меньше.

[ViTech]

Меня бы устроил вариант через boost::range типа такого:

Код:

    auto iter = boost::max_element(points | boost::adaptors::transformed(cost));

Простая и понятная запись, но оно не работает с lambda.

С лямбдой работает Range-v3:

Код

C++ (Qt)
    auto points_costs = ranges::view::transform(points, cost);
    auto index        = ranges::distance(points_costs.begin(),
                                         ranges::max_element(points_costs));

Но во время работы ranges::max_element могут повторно вычисляться cost (для текущей максимальной точки).

Да тут, наверное, проще свой qmax_element написать:

Вот у меня такое же мнение сложилось, что придется самому написать. Странно, что такая простая задача комбинацией готовых алгоритмов не решается.

Задача может не такая уж и простая. Стандартные алгоритмы не знают, что можно кэшировать, а что нужно вычислять каждый раз. Может в cost рандом какой присутствует, или зависимость от времени. Алгоритму нужно об этом как-то сообщать. И в этом случае действительно проще свой алгоритм написать.