Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Re: Shootout (fannkuch)

Reply
Thread Tools

Re: Shootout (fannkuch)

 
 
Branimir Maksimovic
Guest
Posts: n/a
 
      05-05-2008
On May 5, 8:54*am, Razii <(E-Mail Removed)> wrote:
> On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
>
> <(E-Mail Removed)> 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 proportion 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=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.

 
Reply With Quote
 
 
 
 
Isaac Gouy
Guest
Posts: n/a
 
      05-05-2008
On May 5, 3:10 am, Branimir Maksimovic <(E-Mail Removed)> wrote:
> On May 5, 8:54 am, Razii <(E-Mail Removed)> wrote:
>
> > On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy

>
> > <(E-Mail Removed)> 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.



The FAQ gives instructions on how to contribute better programs

http://shootout.alioth.debian.org/gp4/faq.php#play



> Well, I wouldn't be to serious aboutshootoutsite,
> 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 proportion on anything else.



Performance measurements are brittle.


> 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.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
HEXUS.reviews :: 3-way i955x motherboard shootout Silverstrand Front Page News 0 09-16-2005 09:43 PM
HEXUS.review :: Jabra BlueTooth headset shootout Silverstrand Front Page News 0 08-31-2005 01:51 PM
HEXUS.review: GeForce 7800 GTX shootout Silverstrand Front Page News 0 08-04-2005 05:22 PM
Results of DIMA 2004 Printer Shootout Robert E. Williams Digital Photography 8 02-20-2004 03:58 PM
Point and shoot shootout ChrisFerro Digital Photography 4 07-16-2003 04:16 PM



Advertisments