On May 5, 8:54 am, Razii <tynkf...@hotmail.com> wrote:
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
<igo...@yahoo.com> wrote:
Why don't you go through all...
This time I am going to demonstrate a very serious problem with the
shootoutsite.
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.
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=1):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=0, maxFlips=0;
do
{
if(dispcount++<30)
{
copy(perm.begin(),perm.end(),ostream_iterator<int>(o));
o<<'\n';
}
if (!(perm[0]==1 || perm[n-1]==n)) // ?? why
{
copy(perm.begin(),perm.end(),flips.begin());
int nflips=0;
while(flips[0]!=1)
{
reverse(flips.begin(),flips.begin()+flips[0]);
++nflips;
}
if(nflips>maxFlips)maxFlips=nflips;
}
}while(next_permutation(perm.begin(),perm.end()));
return maxFlips;
}
int main(int argc, const char **argv) {
int n = (argc>1) ? atoi(argv[1]) : 0;
cout << "Pfannkuchen(" << n << ") = "
<< fannkuch(n, cout) << '\n';
return 0;
}
Greetings, Branimir.