notebook.community

Edit and run

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.



In [1]:

    
from __future__ import print_function



In [2]:

    
def foo(n):
    return sum(filter(lambda x: x % 3 == 0 or x % 5 == 0, range(n)))



In [3]:

    
n=10
foo(n)









    Out[3]:





23



In [4]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 355 µs per loop






    Out[4]:





233168



In [5]:

    
def foo(n):
    total = 0
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total



In [6]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 251 µs per loop






    Out[6]:





233168

It is surprising that the naive code immediately above is faster than the functional programming version.



In [7]:

    
def foo(n):
    a = []
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            a.append(i)
    return sum(a)



In [8]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 305 µs per loop






    Out[8]:





233168



In [9]:

    
def foo(n):
    return sum([i for i in range(n) if i % 3 == 0 or i % 5 == 0])



In [10]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 258 µs per loop






    Out[10]:





233168



In [11]:

    
def foo(n):
    return sum((i for i in range(n) if i % 3 == 0 or i % 5 == 0))



In [12]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 261 µs per loop






    Out[12]:





233168



In [13]:

    
def foo(n):
    return sum((j for j in (i for i in range(n) if i % 3 == 0) if j % 5 == 0))



In [14]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 219 µs per loop






    Out[14]:





33165

Wow, the nested generator expressions above were fastest yet, and also ugliest.

The unnested list comprehension was faster than the unnested generator expression, so let's try nested list comprehensions.



In [15]:

    
def foo(n):
    return sum([j for j in [i for i in range(n) if i % 3 == 0] if j % 5 == 0])



In [16]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 195 µs per loop






    Out[16]:





33165

I expected the nested list comprehensions to be a little bit faster than the nested generator expressions, so I was surprised by the big speed increase.

Let's play with generators more.



In [17]:

    
def threes_or_fives(gen):
    for i in gen:
        if i % 3 == 0:
            yield i
        elif i % 5 == 0:
            yield i

def foo(n):
    return sum(threes_or_fives(range(n)))



In [18]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 254 µs per loop






    Out[18]:





233168



In [19]:

    
def threes_or_fives(gen):
    for i in gen:
        if i % 3 == 0 or i % 5 == 0:
            yield i

def foo(n):
    return sum(threes_or_fives(range(n)))



In [20]:

    
n=1000
%timeit foo(n)
foo(n)









    



The slowest run took 4.86 times longer than the fastest. This could mean that an intermediate result is being cached 
1000 loops, best of 3: 261 µs per loop






    Out[20]:





233168

It is surprising that the naive verbose generator function with two if statements is faster than the generator function with the combined if statement.

I thought of one more way later, using sets, that should be much more elegant.



In [21]:

    
def foo(n):
    return sum(set(range(0, n, 3)) | set(range(0, n, 5)))



In [22]:

    
n=1000
%timeit foo(n)
foo(n)









    



10000 loops, best of 3: 63.6 µs per loop






    Out[22]:





233168

Holy smokes! It is easier to read, but I did not expect it to be so fast.

I can not resist the temptation to generalize.



In [23]:

    
def foo(n, divisors):
    all_multiples = set([])
    for multiples in (set(range(0, n, divisor)) for divisor in divisors):
        all_multiples |= multiples
    return sum(multiples)



In [24]:

    
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)









    



10000 loops, best of 3: 60.9 µs per loop






    Out[24]:





99500

I am surprised that the generalized version is faster yet. It sure is ugly.

Of course, this does not compare to what I did last year in http://nbviewer.ipython.org/url/colug.net/python/all-ipython-notebooks/euler-001-multiples-of-3-and-5-20150220.ipynb.