Next time i'll try to be more clear on what my problem is and how it is supposed to achieved! (The input was all streamed into the program automatically there was no manual input. I just used the input() function because i didn't have a clue yet how else to read in an integer ;-) )
Besides doing these little excersises i'm reading :
O'reilly's - 'Learning Python'
and 'Dive into python' (www.diveintopython.org).
So i'm hoping i can soon help people the way you guys helped me ;-)
Once again thanks everyone for their suggestions and time!!!
Regards - Geoframer
On 10/8/06, Tim Peters <
[EMAIL PROTECTED]> wrote:
[Geoframer]
> The last few days i've been learning python and have been doing this by
> trying to solve problems for a programming competition.
I assume you're talking about:
http://www.spoj.pl/problems/FCTRL/
If so, you'll note that I'm tied for the fastest Python solution there ;-)
The /guts/ of my method is just:
# count <- number of trailing zeroes in n!
count = 0
base = 5
while n >= base:
count += n // base
base *= 5
There are several reasons for why that's faster than what you tried,
which have been explained by others (doesn't create a list of divisors
each time; gets out of the loop as soon as there's no point to
continuing). It's /possible/ that it would be faster if you did keep
a canned list of powers of 5.
But for some of the SPOJ problems (like this one ;-)), that's not the
real thing to worry about! Some have very large input sets, and the
time spent doing I/O, and converting between strings and integers,
swamps the time needed to do calculations.
So, for example, in this problem I didn't read one line at a time.
Instead I did:
def main():
import sys
ncases = int(sys.stdin.readline())
all = map(int, sys.stdin.read().split())
assert ncases == len(all)
for n in z(all):
print n
The important part there is sucking in all of the test cases "in one
gulp", and converting to them /all/ to integers with a /single/ fast
map() call. The z() function is basically what I wrote above,
containing a loop to march over all the inputs. It's also important
for peak speed to use functions so that faster local-variable lookups
can be used instead of slower global-variable lookups.
But those aren't the most important parts either ;-) When it comes to
speed, it's rarely what you think it is.
Using the input() function was almost certainly your primary problem,
because input() endures the relatively enormous expense of /compiling/
the input string as a fully general Python _expression_, generating a
code object for that _expression_, interpreting that dynamically
generated Python code, and then tearing down the code object again.
For every input. It's not the slowest possible way to convert a
string to an integer, but you'd have to work hard to find a slower way
;-)
Just for fun, you might want to try /just/ changing:
b = input()
in your program to
b = int(raw_input())
I don't know whether you'll meet the time limit then, but it will run
much faster.
Finally, if you look at the 20 accepted Python solutions:
http://www.spoj.pl/ranks/FCTRL/lang=PYTH
you'll see that the top 5 all used enormously more memory than the
other 15. That's an almost-certain sign that they used psyco (which
the SPOJ folks have installed), like so:
# the rest of the code goes here
import psyco
psyco.full()
if __name__ == "__main__":
main()
Note that psyco doesn't always help -- sometimes it makes a program slower.
As the 15 other accepted Python solutions show, it's not necessary to
use psyco to meet the time limit for this problem. If I could, I'd
retract my run using psyco and settle for a non-psyco run -- I
couldn't care less about being "the fastest" on these, and just
/tried/ psyco here out of professional curiousity. Alas, SPOJ only
remembers the fastest correct run you submit.
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
