[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
