maxima & minima

[Alf P. Steinbach]

* Baloff:

Is there a library which can help in doing the task below or do I need
to write something up?

It's almost guaranteed to be less work to write your own code than
to find, install and figure out a library.

I need to get the index of the relative “local” maximas and minimas in a
sequence or real numbers.

The indices, surely?

That is when the derivative is zero and there
is a change in direction.

Uhm, a sequence doesn't have a derivate, but taking that as a figure of
speech: just loop over the numbers and note every change and zero in the
first difference.

 

[Chris Theis]

Hello group

Is there a library which can help in doing the task below or do I need to
write something up?

I need to get the index of the relative “local” maximas and minimas in a
sequence or real numbers. That is when the derivative is zero and there
is a change in direction.

Thanks

You can iterate over the sequence of values and calculate the derivate
easily using the finite difference formula. Then just observe a change in
the sign of two consecutive derivates and you have you minimum or maximum.
However, if you want to classify them you'll have to calculate the 2nd
derivate too and in this case I'd suggest to calculate the derivate not
using a linear connection of two points but rather a parabola fitted with
three points of your sequence.

Cheers
Chris

 

[John Carson]

Hello group

Is there a library which can help in doing the task below or do I need
to write something up?

I need to get the index of the relative “local” maximas and minimas
in a sequence or real numbers. That is when the derivative is zero
and there is a change in direction.

Thanks

Just for fun, I have written some quick code to solve your problem. It seems
to work, but I suggest you test it more thoroughly than I have.

It defines a template class Optima. The template parameter is a pointer or
iterator of the type needed to traverse the container storing the real
numbers. You declare an instance of this class and supply to its constructor
two arguments:

1. A pointer/iterator to the first real number to be tested.
2. A pointer/iterator to one past the last real number to be tested or a
count of the number of objects to be tested. The second alternative only
works with pointers/random access iterators.

The constructor creates two vectors of pointers/iterators. The members of
the first vector point to the elements that are minima. The members of the
second vector point to the elements that are maxima. References to these two
vectors can be retrieved from an Optima object with the member functions
MinIndices() and MaxIndices().

The class and a sample use are given below. It is assumed that the real
numbers are stored as doubles.

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <vector>
#include <functional>
using namespace std;

enum OptType {MIN, MAX};

template<typename Iterator>
class Optima
{
public:
Optima(Iterator a_start, int size) : start(a_start),
finish(a_start+size)
{
FindAllOptima();
}
Optima(Iterator a_start, Iterator a_finish)
: start(a_start), finish(a_finish)
{
FindAllOptima();
}

const vector<Iterator> & MinIndices()
{
return optIndex[MIN];
}
const vector<Iterator> & MaxIndices()
{
return optIndex[MAX];
}
private:
Iterator it, itnext, start, finish;
vector<Iterator> optIndex[2];
void FindAllOptima();
void FindFirstOptima();
template<OptType ot, typename Comparison>
void FindNextOptima();
void FindNextMin() { FindNextOptima<MIN, less<double> > ();}
void FindNextMax() { FindNextOptima<MAX, greater<double> > ();}
};

/////////// Use of class (member definitions come later) ///////////

const int size = 200;
double g_array[size];
typedef double * ItType;

int main()
{
for(int i=0; i<size; ++i)
g_array = rand();

ItType itstart = g_array;
ItType itfinish = g_array+size;


Optima<ItType> opt(itstart, itfinish);

// print out the results;
const vector<ItType>& maxIndices = opt.MaxIndices();
const vector<ItType>& minIndices = opt.MinIndices();

size_t imax=0, imin=0;

for(ItType it = itstart; it != itfinish; ++it)
{
// first the number
cout << setw(7) << *it;
// now show if it's a local max
if(it == maxIndices[imax])
{
cout << " Max";
if(imax < maxIndices.size()-1)
++imax;
}
// now show if it's a local min
if(it == minIndices[imin])
{
cout << " Min";
if(imin < minIndices.size()-1)
++imin;
}
cout << endl;
}
}



///// Member function definitons ////////////////////////

template<typename Iterator>
void Optima<Iterator>::FindFirstOptima()
{
// first check for boundary min/max
if(*it < *itnext)
optIndex[MIN].push_back(it);
else if(*it > *itnext)
optIndex[MAX].push_back(it);
else // constant section initially
{
// get past the constant section
while(itnext != finish && *it == *itnext)
{
++it, ++itnext;
}

if(itnext == finish) // constant to the end
{
for(Iterator k = start; k != itnext; ++k)
{
optIndex[MIN].push_back(k);
optIndex[MAX].push_back(k);
}
}
else if(*it < *itnext) // constant then increasing => min
{
for(Iterator k = start; k != itnext; ++k)
{
optIndex[MIN].push_back(k);
}
}
else // constant then decreasing => max
{
for(Iterator k = start; k != itnext; ++k)
{
optIndex[MAX].push_back(k);
}
}
}
}

template<typename Iterator>
template<OptType ot, typename Comparison>
void Optima<Iterator>::FindNextOptima()
{
static Comparison comp;
// get past changing section
while(itnext != finish && comp(*itnext, *it))
{
++it, ++itnext;
}

if(itnext == finish) // changing section lasts to the end
optIndex[ot].push_back(it); // record boundary optimum
else // reach a constant section
{
// first optimum index
Iterator localStart = it;
// get to end of constant section
while(itnext != finish && *itnext == *it)
{
++it, ++itnext;
}
if(itnext == finish // constant to the end
|| comp(*it, *itnext)) // sign reversal in differences
{
for(Iterator k = localStart; k != itnext; ++k)
optIndex[ot].push_back(k);
}
// else differences revert to previous value so it's an inflection
}
}

template<typename Iterator>
void Optima<Iterator>::FindAllOptima()
{
it = start;
itnext = start;
++itnext;

FindFirstOptima();
while(itnext != finish)
{
if(*it < *itnext)
FindNextMax();
else
FindNextMin();
}
}

 

[Howard]

Hello group

Is there a library which can help in doing the task below or do I need to
write something up?

I need to get the index of the relative local maximas and minimas in a
sequence or real numbers. That is when the derivative is zero and there
is a change in direction.

Thanks

As Alf mentioned, there is no derivative of a sequence. You'd first need to
compute a formula for an equation which satisfies the sequence before you
could compute a derivative. And there are an infinite number of functions
which satisfy any given sequence of points, so there may be any number of
local maximas and minimas.

Besides, it's really redundant to state that the derivative must be zero,
because, given any continuous function of x which maps to the sequence, then
any time the y direction changes, at at least one location within the
sequence of three points used to detect a direction change, the derivative
must equal zero. Consider the values 4,2,3 (at x values of 1,2,3, let's
say). The function is tending downward from 4 to 2, then upward from 2 to
3. So, at at least one location, if the function is continuous, the curve
must have changed directions, and thus has a derivative of zero. But
there's no way of telling *where* any of those possible changes occurred.
However, since you are asked only to find the index, you can at least narrow
it down to "somewhere in the vicinity of x=2". It could actually be
arbitrarily close to x=1 or x=3, but since you have no way to tell without a
formula for the function, you might as well choose the "inflection" point,
or x=2.

As a general rule, then, simply check every set of three consecutive points,
and report the value of x for every x for which both its neighbors are
either greater or smaller:

for (int x = 1; x < (N-1); ++x)
if ((f[x-1] < f[x]) && (f[x] > f[x+1]))
ReportLocalMaxima(x,f[x]);
else if ((f[x-1] > f[x]) && (f[x] < f[x+1]))
ReportLocalMinima(x,f[x]);

-Howard

 

[Karl Heinz Buchegger]

As a general rule, then, simply check every set of three consecutive points,
and report the value of x for every x for which both its neighbors are
either greater or smaller:

But take care to report a sequence such as

4, 2, 2, 3

as a local minimum!
In other words: just by looking at only 3 points in sequence, you will
miss some minima/maxima.

 

[Howard]

But take care to report a sequence such as

4, 2, 2, 3

as a local minimum!
In other words: just by looking at only 3 points in sequence, you will
miss some minima/maxima.

Ooh! Good point! Blows my simple loop out of the water, huh? But if
the above is allowed, then what would you report as the index of the
minimum? I think that question needs to be addressed to whoever made the
spec's in the first place. (A college instructor?)

-Howard

 

[John Carson]

Ooh! Good point! Blows my simple loop out of the water, huh? But if
the above is allowed, then what would you report as the index
of the minimum? I think that question needs to be addressed to
whoever made the spec's in the first place. (A college instructor?)

There is nothing to say that a local maximum or minimum must be a *strict*
local maximum/minimum even when a continuous function domain is being
considered. Functions can easily have horizontal sections in which you have
a continuum of optima, with all points interior to the horizontal section
having the same value as all points in a sufficiently small neighbourhood of
them. In the case of 4, 2, 2, 3, the indices of both '2's should be
recorded.

 

[John Carson]

The constructor creates two vectors of pointers/iterators. The
members of the first vector point to the elements that are minima.
The members of the second vector point to the elements that are
maxima.

I did this for generality. If you are working with C-style arrays or C++
vectors and want indices, then you can get them as follows.

If working with pointers, then you can get indices from the pointers by
simply subtracting the pointer to the zero element from the pointer to the
element of interest, e.g.,

int indexOfMax = ptrToMax - ptrToZeroElement;

If you are working with vectors from the standard library and the associated
iterators, say:

vector<double> vec(N);
vector<double>::iterator itr;

then if itr points to a maximum, the associated index is

int indexOfMax = itr - vec.begin();

 

[Baloff]

Hello group

Is there a library which can help in doing the task below or do I need
to write something up?

I need to get the index of the relative “local” maximas and minimas in a
sequence or real numbers. That is when the derivative is zero and there
is a change in direction.

Thanks

 

[Tatu Portin]

Hello group

Is there a library which can help in doing the task below or do I need
to write something up?

I need to get the index of the relative “local†maximas and minimas in a
sequence or real numbers. That is when the derivative is zero and there
is a change in direction.

Thanks

Look at GNU Scientific Library.