Re: Shootout (fannkuch)

Discussion in 'Java' started by Branimir Maksimovic, May 5, 2008.

  1. On May 5, 8:54 am, Razii <> wrote:
    > On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
    >
    > <> 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.
     
    Branimir Maksimovic, May 5, 2008
    #1
    1. Advertising

  2. Branimir Maksimovic

    Isaac Gouy Guest

    On May 5, 3:10 am, Branimir Maksimovic <> wrote:
    > On May 5, 8:54 am, Razii <> wrote:
    >
    > > On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy

    >
    > > <> 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.
     
    Isaac Gouy, May 5, 2008
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Michael Chermside

    ConfigParser shootout, preliminary entry

    Michael Chermside, Oct 17, 2004, in forum: Python
    Replies:
    15
    Views:
    503
    WakeBdr
    Oct 20, 2004
  2. Carlos Ribeiro
    Replies:
    6
    Views:
    491
    Carlos Ribeiro
    Oct 21, 2004
  3. David Wilson
    Replies:
    13
    Views:
    532
    Paul Moore
    Oct 25, 2004
  4. Jacob Lee

    code for Computer Language Shootout

    Jacob Lee, Mar 16, 2005, in forum: Python
    Replies:
    14
    Views:
    631
  5. Branimir Maksimovic

    Re: Shootout (fannkuch)

    Branimir Maksimovic, May 5, 2008, in forum: C++
    Replies:
    1
    Views:
    357
    Isaac Gouy
    May 5, 2008
Loading...

Share This Page