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

[Geoframer]

Thanks everyone for the valuable suggestions. Lots of suggestions which i'm
sure will improve the speed and performance of my solution. It is indeed the
problem Tim said, and it helps a lot to get some help from one of the
fastest people on there ;-). I just find it's more fun (and probably more
productive) to learn by trying as well as reading. I'm sure i'll be able to
solve some other problems with the suggestions here as i've run into the
timelimit more often already.

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 <tim.peters at gmail.com> 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20061008/4adfe5aa/attachment.html