On May 5, 3:10 am, Branimir Maksimovic <bm...@[EMAIL PROTECTED]
> wrote:
> On May 5, 8:54 am, 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
> >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 pro****tion 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.
|
