"Baloff" <vd****@bi.edu.gr> wrote in message
news:42********@news.iprimus.com.au
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[i] = 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();
}
}
--
John Carson
