Russian Qt Forum
Сентябрь 26, 2018, 12:55 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Поиск лучшего элемента через stl/boost алгоритм  (Прочитано 534 раз)
kamre
Частый гость
***
Offline Offline

Сообщений: 230


Просмотр профиля
« : Июнь 29, 2018, 08:48 »

Задача простая и довольно типичная:
 - имеется последовательность элементов (может быть контейнер, пара итераторов, ...)
 - есть нетривиальный алгоритм для оценки элементов, результат представляется в виде значения типа 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 - опять же потеря производительности, насколько я понимаю.

Так чем можно заменить простой цикл с поиском лучшего элемента?
Записан
Пантер
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 5684


Жаждущий знаний


Просмотр профиля WWW
« Ответ #1 : Июнь 29, 2018, 09:00 »

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

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

1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
kamre
Частый гость
***
Offline Offline

Сообщений: 230


Просмотр профиля
« Ответ #2 : Июнь 29, 2018, 09:53 »

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

Меня бы устроил вариант через boost::range типа такого:
Код:
    auto iter = boost::max_element(points | boost::adaptors::transformed(cost));
Простая и понятная запись, но оно не работает с lambda.
« Последнее редактирование: Июнь 29, 2018, 10:00 от kamre » Записан
qate
Гипер активный житель
*****
Offline Offline

Сообщений: 893


Просмотр профиля
« Ответ #3 : Июнь 29, 2018, 11:01 »

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

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

Сообщений: 1788



Просмотр профиля
« Ответ #4 : Июнь 29, 2018, 11:58 »

Да тут, наверное, проще свой 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
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
kamre
Частый гость
***
Offline Offline

Сообщений: 230


Просмотр профиля
« Ответ #5 : Июнь 29, 2018, 12:31 »

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

А в чём там выйгрышь? Он ведь тоже использует std::max_element в конечном счёте..
Да, boost::range не подходит в таком случае.
Записан
m_ax
Neo
******
Offline Offline

Сообщений: 1788



Просмотр профиля
« Ответ #6 : Июнь 29, 2018, 12:35 »

Цитировать
Странно, что такая простая задача комбинацией готовых алгоритмов не решается.
Не, в принципе, решается через тот же 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;
   });
 
« Последнее редактирование: Июнь 29, 2018, 12:37 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 10165


Просмотр профиля
« Ответ #7 : Июнь 29, 2018, 16:21 »

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

Сообщений: 486



Просмотр профиля
« Ответ #8 : Июнь 30, 2018, 13:17 »

Меня бы устроил вариант через 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 рандом какой присутствует, или зависимость от времени. Алгоритму нужно об этом как-то сообщать. И в этом случае действительно проще свой алгоритм написать.
Записан

Пока сам не сделаешь...
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Страница сгенерирована за 0.138 секунд. Запросов: 22.