P5.1.1The IPython %timeit magic
Improve on the algorithm to find the number of factors of an integer given in Section 5.1.3 of the book by (a) looping the trial factor, i, up to no greater than the square root of n (why is it not necessary to test values of i greater than this?), and (b) using a generator (see Section 4.3.5). Compare the execution speed of these alternatives using the %timeit IPython magic.
Show solution
(a) The first improvement to this algorithm is given by the function factors1(), below. Within IPython, this function can be written in the default text editor and initialized using the %edit magic:
def factors1(n):
facs = set()
for i in range(1, int(math.sqrt(n)) + 1):
if not n % i:
facs |= {i, n // i}
return facs
By adding both the number i which is found to be a factor of n and n // i (which is also a factor of n) it is not necessary to test values of i greater than the square root of n: such values will already have been included as n // i. We use a set() so that values for which i and n // i are equal are not duplicated in the output.
To time it, call it with some large(ish) integer using the %timeit magic:
In [x]: %timeit factors1(123456789)
1000 loops, best of 3: 1.33 ms per loop
(b) The same algorithm can be coded using a generator expression:
def gen_factors2(n):
yield 1
for i in range(2, int(math.sqrt(n)) + 1):
if not n % i:
yield i
yield n // i
yield n
def factors2(n):
return set(gen_factors2(n))
but does not lead to a significantly different execution time:
In [131]: %timeit factors2(123456789)
1000 loops, best of 3: 1.27 ms per loop
(Generators are very memory efficient but cannot generally be expected to be faster than list comprehensions.)