BenI'm learning Python by teaching myself, ... I'm working on the

Benproject Euler problems, but I find that they don't really help my

Benprogramming skills; they are more math focused.

I've found quite the opposite to be the case. I've been programming in

Python for quite awhile and I find Project Euler helps me explore both the

math side of the problems (reminding me of all I've forgotten) but also

forces me to exercise various Python programming techniques and data

structures in ways I typically wouldn't in my day-to-day programming

existence. Some of the problems while conceptually simple to solve are

intractable computationally with naive algorithms.

Here are four of the five (I think) basic ways to solve Problem 1 (find the

sum of all numbers below 1000 which are multiples of 3 or 5). If you run it

notice the wide range of runtimes. Which ones degrade badly as N increases?

#!/usr/bin/env python

import time

N = 1000

t = time.time()

print sum([(n % 3 == 0 or n % 5 == 0) and n or 0 for n in xrange(N)]),

print "%.6f" % (time.time() - t)

t = time.time()

print (sum(xrange(3, N, 3))

+ sum(xrange(5, N, 5))

- sum(xrange(15, N, 15))),

print "%.6f" % (time.time() - t)

t = time.time()

print sum([n for n in xrange(N) if n % 3 == 0 or n % 5 == 0]),

print "%.6f" % (time.time() - t)

t = time.time()

print reduce(lambda x,y: x+y,

filter(lambda n: n%3==0 or n%5==0, xrange(N))),

print "%.6f" % (time.time() - t)

t = time.time()

print sum(set(xrange(3, N, 3)) | set(xrange(5, N, 5))),

print "%.6f" % (time.time() - t)

--

Skip Montanaro -

sk**@pobox.com -

http://smontanaro.dyndns.org/