CODEWITHSUNDEEP
c++algorithmboost
Andriy
Andriy

Reputation: 8604

Standard or boost algorithm for finding the index for the minimum of f(Xi)

My problem is following: Given a contaner X = {x1, x2, ...,xn} and a function f, find the index i where the value f(xi) reaches the minimum.

Of course, I can implement it from scratch, but I've got a feeling that I've invented a bicycle, so I'm looking for a shorter code using standard or boost algorithms. The best I could get was

template <typename Val>
Val f(Val)
{
.........
}

template <typename It>
It find_minimum(It begin, It end)
{
return std::min_element(begin, end, 
   [](typename It::value_type val1, typename It::value_type val2)
  {
  return f(val1) < f(val2);
  });
}

but it suffers from the problem that f is evaluated 2N-1 times.

Upvotes: 2

Views: 313

Answers (4)

J. Calleja
J. Calleja

Reputation: 4905

The shorter answer I can find uses std::min_element and boost::transform_iterator:

return std::min_element(
  boost::make_transform_iterator(begin, f), 
  boost::make_transform_iterator(end, f)).base();

However, it may need 2N-1 function calls depending on the std::min_element implementation.

Upvotes: 0

distantTransformer
distantTransformer

Reputation: 119

You could use lambda with state, if you do know implementataion of std::min_element 

auto minElt = std::min_element(data.begin(), data.end(), [f](const int& a, const int& b)->bool
                               {
                                   static int minValCash = f(b);
                                   int v2 = f(a);
                                   bool result = v2 < minValCash;
                                   if(!result)
                                    std::swap(v2, minValCash);
                                   return result;
                               });

Upvotes: 0

Mario
Mario

Reputation: 36497

How about using an additional step to calculate and store all f(x), then look for the minimum value?

Alternative idea: Iterate over all possible values of x and store the previous minimum only?

Upvotes: 0

CoffeDeveloper
CoffeDeveloper

Reputation: 8315

Just use this algorithm (pseudo code, don't have time to make it template correct)

It element= X.first()
Val min = f(element)
It min_el = element
while(element= element.next())
{
    Val temp = f(element);
    if( min > temp)
    {
        min_el = element;
        min = temp;
    }
}
return min_el

Upvotes: 1

Related Questions