[Tutor] Need help speeding up algorithm.

[Kent Johnson]

Terry Carroll wrote:
> On Tue, 25 Sep 2007, Ian Witham wrote:
> 
>> As I was using a list comprehension I wasn't sure how to make the
>> calculations stop when the result of integer division == 0.
> 
> I don't see how to do that, either.  Someone on this list (sorry, I forget 
> who) once suggested that the list comprehension should support a "while" 
> predicate, similar to the "if" filter.  Such a predicate would not just 
> filter the generated list, but actually stop its computation.

Take a look at itertools.takewhile()

> Now that you've solved your code, here's the function I came up with.  As 
> I said, it resists implimentation as a list comprehension:
> 
> def numfaczeroes(n):
>     """
>     return the count of trailing zeroes from n!
>     e.g., 10! = 3628800; count of trailing zeros = 2
>     """
>     exponent = 1
>     fivecount = 0
>     while (n//(5**exponent)) > 0:
>         fivecount += n//(5**exponent)
>         exponent += 1
>     return fivecount

Here is a version using takewhile() and a generator expression:

from itertools import count, takewhile

def numfaczeroes2(n):
     def while_(e):
         return n//(5**e) > 0
     return sum(n//(5**exponent) for exponent in takewhile(while_, 
count(1)))


It is quite a bit slower, though; probably because of the extra function 
call introduced for while_():

from timeit import Timer
print min(Timer('for i in range(1, 101): numfaczeroes(i)',
     setup='from __main__ import numfaczeroes').repeat(number=1000))

print min(Timer('for i in range(1, 101): numfaczeroes2(i)',
     setup='from __main__ import numfaczeroes2').repeat(number=1000))

prints:
0.14363694191
0.412271022797

You could also encapsulate the condition in a generator function:

def numfaczeroes3(n):
     def gen(n):
         e = 1
         while (n//(5**e)) > 0:
             yield e
             e += 1

     return sum(n//(5**exponent) for exponent in gen(n))

This is faster than numfaczeroes2 but still not as fast as the original.

Kent