Question on execution speed (CPU seconds)

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
dennismv
New poster
Posts: 3
Joined: Tue Jul 03, 2007 2:48 pm

Question on execution speed (CPU seconds)

Post by dennismv » Tue May 05, 2009 12:22 am

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?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Question on execution speed (CPU seconds)

Post by mf » Tue May 05, 2009 12:50 am

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.

Daniel.Q
New poster
Posts: 1
Joined: Tue Sep 29, 2009 8:52 am

Re: Question on execution speed (CPU seconds)

Post by Daniel.Q » Tue Sep 29, 2009 5:24 pm

This is a cool topic. Anyone has any other thoughts to minimize the program running time in terms of C++?

smithdwsn
New poster
Posts: 4
Joined: Mon May 24, 2010 8:50 pm

Re: Question on execution speed (CPU seconds)

Post by smithdwsn » Tue May 25, 2010 3:18 pm

I think you have to manage CPU scheduling. It will help to improve the speed of execution.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: Question on execution speed (CPU seconds)

Post by Jan » Tue Jun 29, 2010 1:15 pm

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.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “C++”