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 have not been coding in Python for close to two years. In fact I have not been coding much for the past two years in any language apart from a few Java utilities and the odd shell scripts to help me get things done in a predicable and automated manner. Hence this is not a post about
how to create good algorithms, but rather some reflections on code performance during my re-entry to Python programming. So please forgive me for any false assumptions and poor code quality.
While reading a book on Python 3 recently, 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 + 49
And since he had not included the number 50 yet, the answer was (50 pairs * 100) + 50 = 5050
So 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.
Naturally I needed to test the same logic on a computer, so I wrote a small Python script to check the human way of thinking (the count()method) and the young Carl Friedrich' way of thinking (the f_count() method):
import time
class FunnyMath(object):
def __init__(self,num=0):
self.num = num
def count(self,num=0):
start = time.time()
self.num = num;
for i in range(1,num):
self.num += i
end = time.time()
print("Traditional approach took {} seconds to get the result: {}".format(round((end-start),2),int(self.num)))
def f_count(self,num=0):
start = time.time()
self.num = num**2/2.0 + num/2.0
end = time.time()
print("Creative approach took {} seconds to get the result: {}".format(round((end-start),2),int(self.num)))
def main():
fm = FunnyMath()
num = 100000000
fm.f_count(num)
fm.count(num)
if __name__ == "__main__":
main()
How long it takes to run will of course depend on your hardware resources. I tested this script on two different laptops.
On the "fast" laptop I got the following output:
Creative approach took 0.0 seconds to get the result: 5000000050000000
Traditional approach took 14.88 seconds to get the result: 5000000050000000
On the "slow" laptop I got the following output:
Creative approach took 0.0 seconds to get the result: 5000000050000000
Traditional approach took 27.76 seconds to get the result: 5000000050000000
So it is an interesting example that shows that some algorithms can and should be optimized. Not only did f_count() perform better. It also had fewer lines of code.
But with a rewrite I could also optimize the slow count() method:
import time
class FunnyMath(object):
def __init__(self,num=0):
assert type(num) is int, "num was not an integer {}".format(num)
self.num = num
def count(self):
num = self.num
for i in range(1,num):
num += i
return int(num)
def f_count(self):
return int(self.num**2/2.0 + self.num/2.0)
def main():
fm = FunnyMath(num = 100000000)
start = time.time()
num = fm.f_count()
end = time.time()
print("Creative approach took {} seconds to get the result: {}".format(round((end-start),2),num))
start = time.time()
num = fm.count()
end = time.time()
print("Traditional approach took {} seconds to get the result: {}".format(round((end-start),2),num))
if __name__ == "__main__":
main()
Then I ran it on the "fast" laptop and got the following output:
Creative approach took 0.0 seconds to get the result: 5000000050000000
Traditional approach took 5.98 seconds to get the result: 5000000050000000
A full rewrite was not really necessary, but I wanted a cleaner and more compact code for my class. The observant reader might have spotted the real problem with the first definition of the count() method:
def count(self,num=0):
start = time.time()
self.num = num;
for i in range(1,num):
self.num += i
end = time.time()
print("Traditional approach took {} seconds to get the result: {}".format(round((end-start),2),int(self.num)))
For each iteration in the loop I was updating the
class variable num instead of just using a
local variable called num, so the same performance gain for the count() method could have been achieved with a small rewrite:
def count(self,num=0):
start = time.time()
num = num;
for i in range(1,num):
num += i
end = time.time()
print("Traditional approach took {} seconds to get the result: {}".format(round((end-start),2),int(num)))
When I ran that on the "fast" laptop I got the the following output:
Traditional approach took 5.92 seconds to get the result: 5000000050000000
The reason for this performance gain is explained in the
Python wiki.
Still, the count() method would always be slower than the f_count() method.
