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 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.