2015-10-16 11 views
11

Вот эта задача пришла ко мне из обзора кода. Я хочу выбрать минимальное значение из набора, основываясь на специальном предикате сравнения. Например:Поиск минимального элемента на основе преобразованного значения

struct Complex { ... }; 

float calcReduction(Complex elem); 

Complex findMinValueWithPredicates(const std::vector<Complex>& values) 
{ 
    auto it = std::min_element(values.begin(), values.end(), 
          [](const Complex& a, const Complex& b) { 
           return calcReduction(a) < calcReduction(b); 
          }); 

    if (it == values.end()) throw std::runtime_error(""); 

    return *it; 
} 

Здесь я нахожу минимальный элемент, основанный на предикате. Этот предикат вычисляет уменьшение обоих значений до float, а затем сравнивает эти поплавки. Отлично работает, выглядит аккуратно.

У вас проблема? Да, для набора N элементов calcReduction() называется 2N раз, а его достаточно вычислить только N раз - один раз для каждого элемента.

Одним из способов решения этой проблемы заключается в написании явных вычислений:

Complex findMinValueExplicit(const std::vector<Complex>& values) 
{ 
    float minReduction = std::numeric_limits<float>::max(); 
    Complex minValue; 

    for (Complex value : values) 
    { 
    float reduction = calcReduction(value); 
    if (reduction < minReduction) 
    { 
     minReduction = reduction; 
     minValue = value; 
    } 
    } 

    if (minReduction == std::numeric_limits<float>::max()) throw std::runtime_error(""); 

    return minValue; 
} 

Он отлично работает, и у нас есть только N звонков на calcReduction(). Однако он выглядит слишком многословным, и намерение не является таким ясным, по сравнению с явным вызовом min_element. Потому что, когда вы звоните min_element, действительно легко догадаться, что вы найдете минимальный элемент, знаете ли.

Единственная идея, которую я имею сейчас, - создать собственный алгоритм, такой как min_element_with_reduction, принимая диапазон и функцию уменьшения. Звучит разумно, но мне интересно, есть ли готовые решения.

Любые идеи о том, как решить эту задачу с явным намерением и некоторыми готовыми решениями? Boost приветствуется. C++ 17 и диапазоны интересны.

+1

Чтобы упростить код, я бы начал с проверки 'values.empty()' first. Затем инициализируйте первый элемент и введите цикл над оставшимися элементами. Нет, это, вероятно, не так очевидно, как ваш текущий код, но если вы оптимизируете этот код для максимальной скорости (вы профилировали это, правда?), Некоторые компромиссы приемлемы для IMHO, особенно если результирующий код правильно объясняется в комментариях. –

+0

@UlrichEckhardt Я думаю, что вы правы, единственная разумная вещь - определить мой собственный алгоритм. Другие решения выглядят полностью ... сложными. – Mikhail

ответ

6

Вы можете использовать boost::rangelibrary.

auto reductionLambda = [](const Complex& a) { return calcReduction(a); }; 
auto it = boost::range::min_element(values | boost::adaptors::transformed( 
          std::ref(reductionLambda)); 

Диапазоны сами должны также соответствовать стандарту C++ с C++ 17.

Редактировать

Как мы выяснили, в комментариях, это будет также сделать преобразование в два раза.

Так вот что-то весело:

#include <boost/iterator/iterator_adaptor.hpp> 
#include <boost/assign.hpp> 
#include <algorithm> 
#include <iostream> 
#include <vector> 
#include <functional> 


template <class Iterator, class UnaryFunction> 
class memoizing_transform_iterator 
    : public boost::iterator_adaptor< 
     memoizing_transform_iterator<Iterator, UnaryFunction> // Derived 
     , Iterator            // Base 
     , std::decay_t<decltype(std::declval<UnaryFunction>()(std::declval<typename Iterator::value_type>()))> // Value 
     , boost::forward_traversal_tag // CategoryOrTraversal 
    > 
{ 
public: 
    memoizing_transform_iterator() {} 

    explicit memoizing_transform_iterator(Iterator iter, UnaryFunction f) 
     : memoizing_transform_iterator::iterator_adaptor_(iter), fun(f) {} 

    static int total; 
private: 
    friend class boost::iterator_core_access; 
    void increment() { ++this->base_reference(); memoized = false; } 

    using MemoType = std::decay_t<decltype(std::declval<UnaryFunction>()(std::declval<typename Iterator::value_type>()))>;  

    MemoType& dereference() const 
    { 
     if (!memoized) { 
      ++total; 
      memoized = true; 
      memo = fun(*this->base()); 
     } 
     return memo; 
    } 

    UnaryFunction fun; 
    mutable bool memoized = false; 
    mutable MemoType memo; 
}; 


template <class Iterator, class UnaryFunction> 
auto make_memoizing_transform_iterator(Iterator i, UnaryFunction&& f) 
{ 
    return memoizing_transform_iterator<Iterator, UnaryFunction>(i, f); 
} 



template<class I, class U> 
int memoizing_transform_iterator<I, U>::total = 0; 


// THIS IS COPIED FROM LIBSTDC++ 
template<typename _ForwardIterator> 
    _ForwardIterator 
    min_el(_ForwardIterator __first, _ForwardIterator __last) 
    { 
     if (__first == __last) 
    return __first; 
     _ForwardIterator __result = __first; 
     while (++__first != __last) 
    if (*__first < *__result) 
     __result = __first; 
     return __result; 
    } 


int main(int argc, const char* argv[]) 
{ 
    using namespace boost::assign; 

    std::vector<int> input; 
    input += 2,3,4,1,5,6,7,8,9,10; 


    auto transformLambda = [](const int& a) { return a*2; }; 


    auto begin_it = make_memoizing_transform_iterator(input.begin(), std::ref(transformLambda)); 
    auto end_it = make_memoizing_transform_iterator(input.end(), std::ref(transformLambda)); 
    std::cout << *min_el(begin_it, end_it).base() << "\n"; 

    std::cout <<begin_it.total; 

    return 0; 
} 

В принципе я реализовал итератор, memoizes результат вызова функтор преобразования. Странная часть состоит в том, что, по крайней мере, в онлайн-компиляторах, итераторы копируются до того, как их разыменованные значения сравниваются (таким образом, побеждая цель memoizing). Однако, когда я просто копировал реализацию из libstdC++, она работает так, как ожидалось. Возможно, вы могли бы попробовать его на настоящей машине? Живой пример: here.

Малые изменения: Я тестировал на VS2015, и она работает, как ожидалось с std::min_element.

+1

Или ['boost :: transform_iterator'] (http://www.boost.org/doc/libs/1_53_0/libs/iterator/doc/transform_iterator.html), если вам не нравятся диапазоны и/или необходимо напишите его сами (итераторы предельно легче писать, чем диапазоны, поскольку они обычно являются предварительным условием). – Yakk

+0

'* it' вернет уменьшенное значение, и невозможно получить базовое значение' Complex'. Кроме того, я думаю, что здесь будут и вычисления «2N», как в моем первом фрагменте кода. – Mikhail

+2

@Mikhail. Вы можете получить исходное значение, используя 'base()' на возвращенном итераторе. Однако вы, вероятно, правы в отношении перерасчета. Хммм. – Rostislav

2

Если взять minElem в качестве параметра лямбда можно использовать min_element

Complex findMinValueWithPredicates(const std::vector<Complex>& values) 
{ 
    float minElem = std::numeric_limits<float>::max(); 
    auto it = std::min_element(values.begin(), values.end(), 
          [&minElem](const Complex& a, const Complex& b) { 
           float tmp = calcReduction(a); 
           if (tmp < minElem) { 
            minElem = tmp; 
            return true; 
           } 
           return false; 
          }); 

    if (it == values.end()) throw std::runtime_error(""); 

    return *it; 
} 

Edit: Почему эта работа, когда b не используется? 25.4.7.21 min_element

21 Возвращает: первый итератор я в диапазоне [первый, последний) таким образом, что для каждого итератора J в диапазоне [первый, последний) следующие соответствующие условия: (* j < * i) или comp (* j, * i) == false. Возвращает последний, если первый == последний.

потому b должны были названы smallestYet (код из cplusplus.com)

template <class ForwardIterator> 
    ForwardIterator min_element (ForwardIterator first, ForwardIterator last) 
{ 
    if (first==last) return last; 
    ForwardIterator smallest = first; 

    while (++first!=last) 
    if (*first<*smallest) // or: if (comp(*first,*smallest)) for version (2) 
     smallest=first; 
    return smallest; 
} 

Который ведет меня к новой любимой цитате:

"Есть только 10 жесткие проблемы в области компьютерных наук: недействительность кэша, именование вещей и ошибки «один за другим» ».

  • Прокомментировал, что мы можем быть вне очереди, поскольку мы не используем b.
  • Я обеспокоен тем, что кеширование minElem может быть неправильным.
  • И я понял, что имя b должно было быть более значимым, поскольку это «разыменованный итератор до наименьшего элемента» или smallestYet.
  • Наконец, не все понимают двоичный код, когда его не написано с помощью «b» в конце.
+0

Это действительно мой второй код, сжатый, завернутый в' min_element'. Я не думаю, что это более читаемо, чем для диапазона. – Mikhail

+0

Рассмотрим 'values ​​= {std :: numeric_limits :: max()}' есть ли какая-либо функциональная разница? – Surt

+0

Согласитесь, ваша реализация будет обрабатывать этот случай, в то время как мой не будет. +1 для этого. – Mikhail

3

Единственное, чего не хватает, это мета-итератор.

Мета-итератор принимает итератор и создает итератор, содержащий его копию. Он передает все операции через содержащийся в нем итератор, за исключением случаев, когда разыменованные возвращают копию содержащегося итератора.

С осторожностью, код, используемый для этого, также работает, чтобы создать итератор поверх size_t или int или аналогичных torsor -likes.

template<class It, class R> 
struct reduced_t { 
    It it; 
    R r; 
    friend bool operator<(reduced_t const& lhs, reduced_t const& rhs) { 
    return lhs.r < rhs.r; 
    } 
}; 
template<class It, class F> 
reduced_t<It, std::result_of_t<F(typename std::iterator_traits<It>::reference)>> 
reducer(It it, F&& f) { 
    return {it, std::forward<F>(f)(*it)}; 
} 

template<class It, class F> 
It reduce(It begin, It end, F&& f) { 
    if (begin==end) 
    return begin; 

    return std::accumulate(
    meta_iterator(std::next(begin)), meta_iterator(end), 
    reducer(begin, f), 
    [&](
     auto&& reduced, // reduced_t<blah...> in C++11 
     It i 
    ) { 
     auto r2 = reducer(i, f); 
     return (std::min)(reduced, r2); 
    } 
).it; 
}; 

f(*it) вызывается ровно один раз на итератор.

Я бы не назвал это ... очевидным. Фокус в том, что мы используем accumulate и мета-итераторы для реализации min_element, тогда мы можем иметь accumulate работать с преобразованными элементами (который вызывается один раз и возвращается).

Вы можете переписать его в стиле программирования на основе стека с использованием примитивов, но есть много примитивов для записи. Может быть, post range-v3.


На данный момент я представляю, что у вас есть мощная композиционная библиотека программирования. Если бы я это сделал, мы могли бы сделать следующее:

reducer(X, f) можно переписать graph(deref |then| f)(X) используя order_by(get_n_t<1>) для заказа.

accumulate звонок может быть прочитан accumulate(skip_first(range), g(begin(range)), get_least(order_by(get_n_t<1>))).

Не уверен, что это яснее.

+0

Не уверен, что я буду использовать его, но подход с итератором, сохраняющий результаты восстановления, выглядит естественным. Благодарю. – Mikhail

+0

Зачем ждать мощную композиционную библиотеку, [range-v3 уже работает] (http://stackoverflow.com/a/34570306/819272), как вы можете видеть в моем ответе :) – TemplateRex

2

Вот еще один вариант, но он по-прежнему эффективно является вашим вторым решением. Честно говоря, это не выглядит ясным, но кому-то это может понравиться. (Я использую std::pair<float, Complex> для хранения результата восстановления и значение, которое было уменьшено.)

std::pair<float, Complex> result{std::numeric_limits<float>::max(), {}}; 
auto output_function = [&result](std::pair<float, Complex> candidate) { 
    if (candidate.first < result.first) 
     result = candidate; 
}; 
std::transform(values.begin(), values.end(), 
       boost::make_function_output_iterator(output_function), 
       [](Complex x) { return std::make_pair(calcReduction(x), x); }); 

P.S. Если ваш calcReduction стоит много, вы видели, как кешировать результаты в Complex объектах? Это приведет к несколько более сложной реализации, но вы сможете использовать простой std::min_element, который делает ваши намерения четкими.

+0

Выглядит неплохо, мне нравится этот подход , Собственно, парень, который изначально реализовал этот код, также использовал 'пар', но сохранял все их в векторе, а затем применял' min_element'. – Mikhail

3

Вот решение, используя (уже работает с range-v3 library, осуществлением автором предстоящего Ranges TS)

#include <range/v3/all.hpp> 
#include <iostream> 
#include <limits> 

using namespace ranges::v3; 

int main() 
{ 
    auto const expensive = [](auto x) { static int n; std::cout << n++ << " "; return x; }; 
    auto const v = view::closed_iota(1,10) | view::transform(expensive); 

    auto const m1 = *min_element(v); 
    std::cout << "\n" << m1 << "\n"; 

    auto const inf = std::numeric_limits<int>::max();  
    auto const min = [](auto x, auto y) { return std::min(x, y); }; 

    auto const m2 = accumulate(v, inf, min); 
    std::cout << "\n" << m2 << "\n";  
} 

Live On Coliru с выходом:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
1 
19 20 21 22 23 24 25 26 27 28 
1 

Как вам можно увидеть, используя min_element принимает 2N сравнения, но используя accumulate только N.

+0

Для решения этой проблемы вам нужны только сравнения N-1. – Yakk

+0

К сожалению, я не могу скомпилировать его в VS2015 с clang. – Mikhail

+0

@Mikhail VS2015 скоро получит Update2, возможно, он будет работать тогда. У меня нет опыта работы в VS2015. – TemplateRex

Смежные вопросы