Last week I wrote three Ruby methods for finding Armstrong numbers. Not only did I enjoy writing up those three solutions, it also got me thinking a little more critically about Ruby at work this week. Since I am teaching a Python class this weekend, I decided to make three implementations of something in Python to get my Pythonista juices flowing. Coding up an Armstrong number finder again would be boring, so I instead looked at Project Euler problems. I decided to start with the first problem — let’s start at the beginning, it’s a very good place to start.
The first problem is to find the sum of all the multiples of 3 or 5 below 1000. Before tackling all the numbers below 1000, let’s look at a simpler version of the same problem: find the sum of all the multiples of 3 or 5 below 10. The numbers below 10 that are multiples of 3 or 5 are 3, 5, 6, and 9.
3 + 5 + 6 + 9 = 23
Before beginning, I wrote some unit tests so I would know if my functions were working as expected.
import unittest from sum_of_multiples_of_3_and_5 import * class TestSumOfMultiplesOf3And5(unittest.TestCase): def test_5(self): self.assertEqual(3, sum_of_multiples_of_3_and_5(5)) def test_10(self): self.assertEqual(23, sum_of_multiples_of_3_and_5(10)) def test_15(self): self.assertEqual(45, sum_of_multiples_of_3_and_5(15)) unittest.main()
This seems like a small and reasonable method to find the sum. It passes unit testing and gives the desired result. These functions are written in Python 2, so I decided to use xrange instead of range. If I were to use range when I call sum_of_multiples_of_3_and_5(1000), range would make a list with 1000 items. If I use xrange, I won’t make a list but instead create an an object that functions like a list — this will help me use less memory as I pass larger numbers to my functions.
def sum_of_multiples_of_3_and_5(number): sum = 0 for i in xrange(number): if i % 3 == 0 or i % 5 == 0: sum += i return sum
>>> sum_of_multiples_of_3_and_5(1000) 233168
This was somewhat difficult to construct, so I can only image what this might look like to a first time reader of a recursive method. Though this method passes my unit tests, it actually barfs when I attempt to use it with large numbers.
def sum_of_multiples_of_3_and_5(number): number -= 1 if number == 0: return 0 elif number % 3 == 0 or number % 5 == 0: return number + sum_of_multiples_of_3_and_5(number) else: return sum_of_multiples_of_3_and_5(number)
>>> sum_of_multiples_of_3_and_5(1000) . . . RuntimeError: maximum recursion depth exceeded
Python constrains recursive methods to 1000 recursions — that’s exactly the number of recursions we need to compute the answer to this problem!
>>> import sys >>> sys.getrecursionlimit() 1000
The recursion limit is in place to make sure a single program does not chew up too much stack and hobble your system. So, it’s actually a good thing that the limit kicked in. We could increase the recursion limit, but instead I think we should count this as a major strike against this implementation. Recursion is not always a bad technique in Python, but it seems to be an inappropriate solution for this particular problem where we are using recursion to replace a large list. For more on recursion, read Ned Batchelder’s article ‘Recursive Dogma’.
This is my favorite implementation. Here, we make a list that contains only the numbers that are a multiple of 3 or 5. I then add all of the digits in the list together. Pretty neat, huh? It passes unit testing and returns the desired result.
def is_multiple_of_3_or_5(number): return number % 3 == 0 or number % 5 == 0 def sum_of_multiples_of_3_and_5(number): multiples = filter(is_multiple_of_3_or_5, xrange(number)) return sum(multiples)
>>> sum_of_multiples_of_3_and_5(1000) 233168
Seeing different implementations is interesting but, how do they really perform? Let’s take a look by using timing code to test each of these functions.
import timeit iterative_100_timer = timeit.Timer("iterative.sum_of_multiples_of_3_and_5(100)", "import sum_of_multiples_of_3_and_5_iterative as iterative") recursive_100_timer = timeit.Timer("recursive.sum_of_multiples_of_3_and_5(100)", "import sum_of_multiples_of_3_and_5_recursive as recursive") functional_100_timer = timeit.Timer("functional.sum_of_multiples_of_3_and_5(100)", "import sum_of_multiples_of_3_and_5_functional as functional") #timeit runs 1000000 passes of each timed method by default. #To get the average, we have to divide the the result by 1000000 print "time for iterative.sum_of_multiples_of_3_and_5(100)" print str(iterative_100_timer.timeit() / 1000000) + " seconds" print print "time for recursive.sum_of_multiples_of_3_and_5(100)" print str(recursive_100_timer.timeit() / 1000000) + " seconds" print print "time for functional.sum_of_multiples_of_3_and_5(100)" print str(functional_100_timer.timeit() / 1000000) + " seconds"
time for iterative.sum_of_multiples_of_3_and_5(100) 1.8330799818e-05 seconds time for recursive.sum_of_multiples_of_3_and_5(100) 3.64456930161e-05 seconds time for functional.sum_of_multiples_of_3_and_5(100) 2.27424471378e-05 seconds
The iterative solution is the fastest! That makes sense. In the iterative solution, we iterate once through all numbers less than 100, adding to the sum as we iterate. We also use only one stack frame to do it.
In the recursive function, we create one stack frame each time we recur. This creates a lot of context switching or a need to preserve state as each stack frame is created and executed. That state preservation comes at a performance cost. Yep, that method is ugly both in terms of readability and performance.
Though the functional solution is more elegant (IMHO) it is still not as fast as the iterative solution. This also makes sense. The functional solution executes in two steps: rather than add to the sum as the range is traversed like the iterative solution, the functional method traverses the range to make a list then adds the list elements together. The functional implementation takes longer because the work is split into two steps. So, iteration wins!