The art of creating efficient algorithms
How often do we think outside the box to create a creative and efficient algorithm when we develop software? I bet answer is “probably not often enough”.
I use Python for Test Driven Development of Ansible roles, but I don’t get to code as much Python as I would like. It’s one of many tools I use, but not my daily driver. Hence this example is not about how to create good algorithms in general, but rather a reflections on how algorithms affects code performance. So please forgive me for any false assumptions and poor code quality.
While reading a book on Python 3 a few years ago, I came across an interesting anecdote about the German mathematician Carl Friedrich Gauss, who at the age of 8 was given a homework assignment to sum up all the numbers between 1 and 100. To his teacher’s astonishment Carl Friedrich answered 5050 a few seconds later, and it was the teacher had to go home and check if the answer was correct.
Instead of adding every number between 1 and 100, the young Carl Friedrich quickly realized that there were 50 pairs of unequal numbers that would sum up to 100:
99 + 1
98 + 2
And so on, all the way down to 51 + 49And since he had not included the number 50 yet, the answer was:
(50 pairs * 100) + 50 = 5050So the youngster had by himself discovered a pretty efficient algorithm for summing up integers. Not bad for an 8 year old! According to Wikipedia this story is contested, but nevertheless it is a very good example of a creative solution for optimizing an algorithm.
So I decided to put this to the test in Python by creating three different methods in a class I called FynnyMath. Two of these functions very slow on purpose:
Slow due to design issue:
The observant reader will see that the major problem in the code block below is that for each iteration I increment the class variable self.num
def slowest(self, num=0):
for i in range(1, self.num):
self.num += i
return int(self.num)This is documented in the Python Wiki as a poor way to use variables. Reference: https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Local_Variable
Slow due to traditional thinking
The method below looks fine from a traditional approach of summing up number. For each iteration a local variable is update by incrementing the value by 1.
def faster(self, num=0):
num = self.num
for i in range(1, num):
num += i
return int(num)The Gauss formula
By creating the formula discovered by young Carl Friedrich Gauss, we get the following method:
def fastest(self, num=0):
return int(self.num**2/2.0 + self.num/2.0)Testing the 3 methods
In order to see a significant benefit of using the Gauss formula, we need to test with a high number, so let’s try summarize all numbers between 1 and 100 millions.
$ python FunnyMath.py
Slowest approach took 10.85 seconds to get the result: 5000000050000000
Faster approach took 4.44 seconds to get the result: 5000000050000000
Fastest approach took 0.0 seconds to get the result: 5000000050000000So this is just one example how it matters to thing outside the box when creating algorithms. The full source code can be seen at https://github.com/avnes/perftest/