Нахождение минимального элемента на основе преобразованного значения
Вот задача пришла ко мне из обзора кода. Я хочу выбрать минимальное значение из набора, основываясь на особом предикате сравнения. Как это:
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, принимая диапазон и функцию сокращения. Звучит разумно, но мне интересно, есть ли готовые решения.
Любые идеи о том, как решить эту задачу с ясным намерением и некоторые готовые решения? Повышение приветствуется. C ++ 17 и диапазоны интересно посмотреть.
Решение
Вы могли бы использовать boost::range библиотека.
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;
}
По сути, я реализовал итератор, который запоминает результат вызова функтора преобразования. Однако странная часть заключается в том, что, по крайней мере, в онлайн-компиляторах итераторы копируются до того, как их разыменованные значения сравниваются (что отрицательно сказывается на цели запоминания). Однако когда я просто скопировал реализацию из libstdc ++, она работает как положено. Возможно, вы могли бы попробовать это на реальной машине? Живой пример Вот.
Небольшое редактирование:
Я тестировал на VS2015, и он работает как ожидалось с std::min_element,
Другие решения
Не хватает только мета-итератора.
Мета-итератор берет итератор и создает итератор, который содержит его копию. Он передает все операции в содержащийся итератор, за исключением случаев, когда разыменованный возвращает копию содержащегося в нем итератора.
С любой осторожностью, код, используемый для этого, также работает для создания итератора над size_t или int или аналогичным торсер-нравится.
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 работать с преобразованными элементами (который вызывается один раз и возвращается).
Вы можете переписать его в стиле программирования на основе стека, используя примитивы, но есть много примитивов для записи. Возможно выложу диапазоны-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> ) ) ),
Не уверен, что это понятнее.
Вот решение с использованием (уже работает с библиотека range-v3, реализация автором предстоящего Ранг ТС)
#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";
}
Жить на Колиру с выходом:
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,
Если вы берете 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;
}
Редактировать:
Почему это работает, когда bне используется?
25.4.7.21 мин_элемент
21 Возвращает: первый итератор i в диапазоне [первый, последний) такой, что
для каждого итератора j в диапазоне [first, last) следующее
выполняются соответствующие условия:! (* 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» в конце.
Вот еще один вариант, но он по-прежнему эффективно ваше второе решение. Если честно, это не выглядит ясно, но кому-то это может понравиться. (Я использую 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); });
Постскриптум Если твой calcReduction стоит много, рассматривали ли вы результаты кэширования в Complex объекты? Это приведет к чуть более сложной реализации, но вы сможете использовать обычный std::min_element что делает ваши намерения ясными.