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

[Andre Engels]

2006/10/7, Geoframer <geoframer at gmail.com>:
> Hi everyone,
>
> The last few days i've been learning python and have been doing this by
> trying to solve problems for a programming competition.
> One particular problem is bugging me. I have already solved it but my
> solution does not compute in the set time-condition. I know
> for a fact that this particular problem is solvable in the time-limit using
> Python, so i was wondering if my solution is maybe inefficitient code-wise.
> If my code can't be optimized for speed any more i must be missing something
> and should labor hard to find a new algorithm ;-).
>
> The problem is to compute the number of trailing zero's in factorials (n! =
> 1*2*3*4*.......*n). with n <= 1000000000
>
 > My solution is as follows (a = times to read a number (b) to process) :
>
> ---------------------------------------------------------------------------
>
> a = input()
> for i in range(a):
>     lst = (5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625,
> 48828125, 244140625)
>     ans = 0
>     b = input()
>     for i in lst:
>         if i <= b:
>              ans += b//i
>     print ans
>
> ----------------------------------------------------------------------------
>
> Please, if you have suggestions to improve the speed of this algorithm give
> an argumentation as to why a certain something is faster.
> That would allow me to learn to program faster algorithms in Python al
> together instead of just in this problem.

The program as you have shown it, skims to incorrectness. Please don't
use the same variable (i) for two nested loops!

Regarding speed, I see some small improvements:

* lst is created each time you go through the loop; creating it once
would suffice as well
* If we have found that some i is larger than b, then definitely the
next one will be

a = input()
lst = (5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625,
48828125, 244140625)
for i in range(a):
    ans = 0
    b = input()
    for j in lst:
        if j <= b:
            ans += b//i
        else:
            break
    print ans

The first thing (moving the lst= out of the loop) will definitely make
a (tiny) improvement on speed; it also improves the logic of your
code. The second (the else: break) I am not sure whether it will
improve things (because often you will go into the else at the last
time or not at all).

Your program goes wrong for large values of b. This should be avoided
- the program should have as little chance as possible for the user to
give 'wrong' input, either by forbidding it or by dealing with it.
Here the latter is easily done:

The way I would do this (although it would make the program slower
rather than faster because it would make the check each time that b is
set:

replace

lst = (5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625,
48828125, 244140625)

by

lst = [5]

and after b=input()
add:
while lst[-1]*5 < b:
    lst.append(lst[-1]*5)

And finally I wonder why on Earth you would worry about the speed of
this program, given that the running time over 1 number is just a
fraction of the time it costs you to type in that number.



-- 
Andre Engels, andreengels at gmail.com
ICQ: 6260644  --  Skype: a_engels