"Jeff" <surferjeff@gmail.com> wrote in message
news:781dd16f.0404230707.eea2968@posting.google.co m...[color=blue]
> "Siemel Naran" <SiemelNaran@REMOVE.att.net> wrote in message[/color]
news:<sp2ic.12749$_o3.420355@bgtnsc05-news.ops.worldnet.att.net>...[color=blue][color=green]
> > "Victor Bazarov" <v.Abazarov@comAcast.net> wrote in message[/color][/color]
news:gg0ic.5519
[color=blue][color=green][color=darkred]
> > > But the whole point of complexity being the same is that while doing
> > > your single path, you will have to do more on every iteration, which
> > > basically negates the difference between one and two passes.[/color]
> >
> > Sure, there's no time saved in the instructions of the body of the loop.
> > But there is the time saved in the loop itself. In the 2 pass algorithm[/color][/color]
for[color=blue][color=green]
> > (int i=0; i<N; i++) we do i++ and i<N a total of 2*N times. In[/color][/color]
mathematical[color=blue][color=green]
> > libraries, people are very concerned about performance.[/color][/color]
[color=blue]
> 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.[/color]
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::pair<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;
}
}
