Page 1 of 1

Question on execution speed (CPU seconds)

Posted: Tue May 05, 2009 12:22 am
by dennismv
I solved Problem 2085. Then I've noticed that my code runs in 1.434 CPU seconds.

Statistics for the problem shows CPU times much smaller than that.
I got curious and optimized my problem and tried different methods of reading input and processing it. My best CPU time was 0.244 CPU seconds, still nothing like 0.053 CPU seconds for the submissions on the problem statistics.

The code I wrote to get 0.244 CPU seconds was pretty well optimized and used some of the more basic features of C++ and I even tried C. I thus wonder how precise is time measured and was the Judging machine or its software ever changed while the old times were kept? Or is there really some code for that problem that will execute in about 0.053 seconds?

Re: Question on execution speed (CPU seconds)

Posted: Tue May 05, 2009 12:50 am
by mf
In problems like that, I/O and input parsing time is going to be a very significant part of program's runtime. Custom I/O routines (perhaps, even coded in assembly) can be much faster than simple scanf.
was the Judging machine or its software ever changed
I think they still use their old Pentium III system and old compilers at icpc live archive. E.g. Java is still 1.1 there!

Oh, and optimization (gcc -O2 flag) is probably off, too. So you can try to compile with optimization locally and submit just the assembly output, wrapped by asm directive.

Re: Question on execution speed (CPU seconds)

Posted: Tue Sep 29, 2009 5:24 pm
by Daniel.Q
This is a cool topic. Anyone has any other thoughts to minimize the program running time in terms of C++?

Re: Question on execution speed (CPU seconds)

Posted: Tue May 25, 2010 3:18 pm
by smithdwsn
I think you have to manage CPU scheduling. It will help to improve the speed of execution.

Re: Question on execution speed (CPU seconds)

Posted: Tue Jun 29, 2010 1:15 pm
by Jan
There are other ideas, too. mf has shown some. Some more hints

1) Some functions can be made 'inline'.
2) When passing vectors or stl structures to functions, try to use references.
3) Sometimes non recursive functions improve runtime.
4) For better running time, manual structures (non-stl) help a lot.

And still there are a lot more.