[Tutor] Can my code be optimized any further (speed-wise)?

[Tim Peters]

[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.