Поиск минимального элемента на основе преобразованного значения

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

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 приветствуется. С++ 17 и диапазоны интересны для просмотра.

Ответы

Ответ 1

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

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

Диапазоны сами по себе должны поступать на стандартный С++ с С++ 17.

Edit

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

Итак, здесь что-то весело:

#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;
}

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

Небольшое редактирование: Я тестировал VS2015 и работает, как ожидалось, с помощью std::min_element.

Ответ 2

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

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

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

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

Ответ 3

Здесь решение с использованием (уже работает с range-v3 library, реализация автором предстоящие диапазоны 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.

Ответ 4

Если вы берете 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 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" в конце.

Ответ 5

Вот еще один вариант, но он по-прежнему эффективно является вашим вторым решением. Честно говоря, это не выглядит ясным, но кому-то это может понравиться. (Я использую 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, который делает ваши намерения ясными.