Jeff said:
"Siemel Naran" <
[email protected]> wrote in message
If this is a very large vector, and this call is in the core loop of
your code, then maybe it's reasonable to worry about the 2-pass vs.
1-pass thing. Or more accurately, a 3-pass vs. 2-pass since the
normalizing the vectors will require another pass.
Here's a one pass solution to finding the max and min:
#include <algorithm>
#include <limits.h>
using namespace std;
struct MaxMin {
int max;
int min;
MaxMin() : max(MIN_INT), min(MAX_INT) {}
inline void operator()(int n) {
if (n < min) min = n;
if (n > max) max = n;
}
};
....
MaxMin mm;
Vector<int> myvector;
// fill myvector
foreach(myvector.begin(), myvector.end(), mm);
// Now the max and min are stored in mm.max and mm.min.
But in any case, please measure the running time of this solution vs.
the running time of the one-pass solution. I suspect there will be so
little difference that the max_element() and min_element() approach
will be preferable because it requires fewer lines of code.
So I actually timed it. Sure, if the cost of operator<(const T&, const T&)
is expensive, then the time of the for loop (namely ++i and i<N), is small
in comparison to the body of the for loop which calls operator<(const T&,
const T&). But if T is int or some other small type, as is often the case
for numerical programs, then we expect the difference to be significant.
I wrote a program that takes a command line argument. If it is "one" it
calls the one-pass method, and for "two" it calls the two-pass method. The
program creates an array of 10 million integers, fills them with random
numbers, then calls either the one-pass or two-pass method to compute the
min and max. To test the functionality of the algorithm only, and not how
well the compiler optimizes STL algorithms, I encoded the logic of the
algorithms min_element etc in the function and did not use functors.
The one pass method took 190 to 195 clock cycles (I ran it about 5 times).
The two pass method to 310 to 370 clock cycles, with a larger standard
deviation for some reason. This is a significant difference.
My platform is Windows ME, 128 MB RAM, using Borland C++ Builder version 6,
AMD Athlon processor.
#if defined(__BORLANDC__)
#include <vcl.h>
#endif
#include <string>
#include <cstdlib> // rand
#include <ctime> // clock
#include <utility> // pair
#include <iostream>
#include <cassert>
typedef std:
air<int,int> PairInt;
PairInt action1(register const int * begin, register const int *const end)
{
assert(begin != end);
register int min = *begin;
register int max = min;
for (++begin; begin!=end; ++begin)
{
const int val = *begin;
if (val<min) min=val;
else if (val>max) max=val;
}
return PairInt(min, max);
}
PairInt action2(const int *const const_begin, register const int *const end)
{
assert(const_begin != end);
register int min = *const_begin;
register int max = min;
register const int * begin = NULL;
begin = const_begin;
for (++begin; begin!=end; ++begin)
{
register const int val = *begin;
if (val<min) min=val;
}
begin = const_begin;
for (++begin; begin!=end; ++begin)
{
register const int val = *begin;
if (val>max) max=val;
}
return PairInt(min, max);
}
int main(int argc, char * * argv)
{
if (argc == 2)
{
const int N = 10000000;
int * array = new int[N];
int *const begin = array;
int *const end = array+N;
for (int * iter = begin; iter != end; ++iter) *iter = std::rand();
const std::string which = argv[1];
typedef PairInt (* PtrAction)(const int *, const int *);
PtrAction ptr = NULL;
if (which == "one") ptr = &action1;
else if (which == "two") ptr = &action2;
if (ptr)
{
using std::clock_t;
using std::clock;
const clock_t clock_start = clock();
const PairInt pair = (*ptr)(begin, end);
const clock_t clock_end = clock();
std::cout
<< "min = " << pair.first << ", "
<< "max = " << pair.second << ", "
<< "time = " << clock_end - clock_start
<< '\n'
;
}
delete[] array;
}
}
