*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

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()

for i in range(1,num):

end = time.time()

print("Traditional approach took {} seconds to get the result: {}".format(round((end-start),2),int(

For each iteration in the loop I was updating the

def count(self,num=0):

start = time.time()

for i in range(1,num):

end = time.time()

print("Traditional approach took {} seconds to get the result: {}".format(round((end-start),2),int(

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.

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.

## No comments:

## Post a Comment