On May 5, 8:54=A0am, Razii <tynkf...@[EMAIL PROTECTED]
> wrote:
> On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
>
> <igo...@[EMAIL PROTECTED]
> wrote:
> >Why don't you go through all...
>
> This time I am going to demonstrate a very serious problem with the
> shootout site.
>
> The algorithms used by C, C++, and D are BETTER than the Java
> versions! What the heck? In some cases Java version is so bad that
> it's 10 times slower.
>
Well, I wouldn't be to serious about shootout site,
as programs compared are trivial and results vary on
setup and machine. You can conclude only that
on particular machine, with particular
os, with particular setup, results are as they
are. You can't conclude that results will
be in same pro****tion on anything else.
For example on my computer both c and c++ versions
show same execution time (gcc 4.2.3).
That should be that way as both are basically same.
C++ version uses vector instead of raw array and
also swaps with std function instead of doing it manually.
But that costs 30% in performance according to site.
Interesting is that following version of c++ program
shows 10% increase in performance relative to both c and c++ version
on the site on my computer ;)
I only use next_permutation instead of algorithm showed
in benchmark, and populate arrays in range of 1..n,
instead of 0..n-1.
What isn't clear to me is why flips are not performed
when permutation array has maximum value for last
element?
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
struct Inc{
int operator()(){ return i_++; }
Inc(int i=3D1):i_(i){}
int i_;
};
int fannkuch(int n, ostream &o) {
if (n < 1) return 0;
vector<int> perm(n),flips(n);
generate(perm.begin(),perm.end(),Inc());
int dispcount=3D0, maxFlips=3D0;
do
{
if(dispcount++<30)
{
copy(perm.begin(),perm.end(),ostream_iterator<int>(o));
o<<'\n';
}
if (!(perm[0]=3D=3D1 || perm[n-1]=3D=3Dn)) // ?? why
{
copy(perm.begin(),perm.end(),flips.begin());
int nflips=3D0;
while(flips[0]!=3D1)
{
reverse(flips.begin(),flips.begin()+flips[0]);
++nflips;
}
if(nflips>maxFlips)maxFlips=3Dnflips;
}
}while(next_permutation(perm.begin(),perm.end()));
return maxFlips;
}
int main(int argc, const char **argv) {
int n =3D (argc>1) ? atoi(argv[1]) : 0;
cout << "Pfannkuchen(" << n << ") =3D "
<< fannkuch(n, cout) << '\n';
return 0;
}
Greetings, Branimir.
|
