Measuring efficiency
... of an algorithm
Writing a effective program is one achievement but to make it efficient is another step forward.
In this tutorial we will write a program and then go through a series of steps to make it more efficient.
Let us write a program to check if the input is a prime number or not
num = int(input("Enter a number:"))
flag = 0
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
else:
for i in range(2, num):
if (num % i) == 0:
flag = 1
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
Output of this program will be
Enter a number:9 9 is not prime
Now Let us write some code which will help us check the efficiency of this program. Just add one more line at the end of the existing code.
num = int(input("Enter a number:"))
flag = 0
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
else:
for i in range(2, num):
if (num % i) == 0:
flag = 1
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Number of times the Loop ran = " + str(i))
Output of this program will be
Enter a number:9 9 is not prime Number of times the Loop ran = 8
Notice that the loop keeps on running even after it was clear that 9 is divisible by 3 in step 2 of the loop. That is very inefficient. We can avoid it using break command. We will now add another FOR loop with BREAK command and try to see how it increases the efficiency.
num = int(input("Enter a number:"))
flag = 0
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
else:
for i in range(2, num):
if (num % i) == 0:
flag = 1
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Loop ran without break = " + str(i))
for i in range(2, num):
if (num % i) == 0:
flag = 1
break
print ("Loop ran with break = " + str(i))
Output of this program will be
Enter a number:9 9 is not prime Loop ran without break = 8 Loop ran with break = 3
Clearly the loop run less number of times in the case where we used BREAK hence making the code more efficient.
We can get the same output as above by avoiding one of the FOR loops.
num = int(input("Enter a number:"))
flag = 0
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
else:
for i in range(2, maxRange):
if (num % i) == 0:
flag = 1
break
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Loop ran without break = " + str(num-1))
print ("Loop ran with break = " + str(i))
Output of this program will be
Enter a number:9 9 is not prime Loop ran without break = 8 Loop ran with break = 3
But in case the number is prime then the loop runs all the way. Which is one less than the number entered e.g. 16 times for entered number as 17. This is called worst case scenario.
Enter a number:17 17 is prime Loop ran without break = 16 Loop ran with break = 16
Now let us discuss one more aspect. If the entered number is, say 17, which is to be checked for prime. Then all we have to do is to check if it is divisible by any number up till the half of 17, that is maximum 9. There is no need to check by every number till the number.
num = int(input("Enter a number:"))
flag = 0
maxRange = int(num/2)
print ("Will check for divisibility up to " + str(maxRange))
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
else:
for i in range(2, maxRange):
if (num % i) == 0:
flag = 1
break
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Number of time the Loop ran = " + str(i))
Notice the output below. You will see that the efficiency in the case of worst case scenario has improved. Actually efficiency has almost doubled since the time consumed by loop has been reduced to half.
Enter a number:17 Will check for divisibility up to 8 17 is prime Number of times the Loop ran = 7
Let us discuss one more aspect. If we have checked for divisibility by 2 then there is no point to check for divisibility by even numbers (4,6,8...). Let us see if they can be avoided.
num = int(input("Enter a number:"))
flag = 0
maxRange = int(num/2)
print ("Will check for divisibility up to " + str(maxRange))
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
elif (num % 2) == 0:
print (str(num) + " is not prime")
else:
for i in range(3, maxRange, 2):
if (num % i) == 0:
flag = 1
break
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Number of times the Loop ran = " + str(i))
The output is shown below if the user enters 17. You will see that the efficiency in the case has not improved
Enter a number:17 Will check for divisibility up to 8 17 is prime Number of times the Loop ran without break = 7
The output is shown below if the user enters 16. You will see that the efficiency in the case has improved drastically as the program completely avoids the loop section
Enter a number:16 will check for divisibility up to 8 16 is not prime
Let me now introduce one more aspect. We should not set variable or do calculations until they are required. The line 2 to 4 can be displace to appropriate place.
num = int(input("Enter a number:"))
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
elif (num % 2) == 0:
print (str(num) + " is not prime")
else:
flag = 0
maxRange = int(num/2)
print ("Will check for divisibility up to " + str(maxRange))
for i in range(3, maxRange, 2):
if (num % i) == 0:
flag = 1
break
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Number of times the Loop ran = " + str(i))
The output is shown below if the user enters 16. You will see that the efficiency in the case has improved a bit as the program avoids a print statement which also shows that it has avoided the allocation and calculation steps.
Enter a number:16 16 is not prime
Cool! Let us go a step further. You would have noticed that our loop runs up to half of the value entered by user. (for example if user enters 17 then the loop runs up to 8 ). Actually there is no need to go till half way also. Just running the loop up to the square root value will be sufficient. So for user entry of 23 we will check up to max 5. So the loop runs for only two times! but now we have another challenge. We will have to write a program to find square root or at least the approximate value.
num = int(input("Enter a number:"))
if num == 0 or num == 1:
print ("Leave 0 and 1 alone")
elif (num % 2) == 0:
print (str(num) + " is not prime")
else:
flag = 0
maxRange = int(round(num**0.5))
myCount = 0
for i in range(3, maxRange, 2):
myCount = myCount + 1
if (num % i) == 0:
flag = 1
break
if flag == 1:
print (str(num) + " is not prime")
else:
print (str(num) + " is prime")
print ("Checked up to %s. Loop ran for %s times" %(str(maxRange),str(myCount)))
Let us consider that the user enters 79 now. The loop will run for 3, 5, 7, 9
But again we do not want the program to check the divisibility by 9 if divisibility by 3 is already checked.
Clearly, all we need to check is divisibility by prime numbers.
The list of primes up to 100 are ... 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
As a mathematics students you may know that but computer does not know that as it needs a program to find primes and that is what our current program is doing.
You can still make this program more efficient by thinking about this problem from a different view point.
There is a limit to which you SHOULD make a program efficient. After that you are spending more than EXPECTED time in making the program more efficient hence the whole process is not EFFICIENT any more.
Keep this trade off in mind always. You should know when to stop! But sometimes stopping is not an option!
Sp here we go...
Prime sieves are faster algorithms used to find primes numbers. Most common of these are...
Sieve of Eratosthenes (250 BC)
Sieve of Sundaram (1934)
Sieve of Atkin (2004)
You are encouraged to research about them and write programs for them. Who knows? you will find a new Sieve this year!
A Sieve program to keep your mind ticking
num = int(input("Enter a number:"))
def sieve(n):
np1 = n + 1
s = list(range(np1))
s[1] = 0
sqrtn = int(round(n**0.5))
for i in range(2, sqrtn + 1):
if s[i]:
s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
return filter(None, s)
print (list(sieve(num)))
print ("%s primes were found up %s" %(str(len(list(sieve(num)))), str(num)))
primes = set(sieve(num))
if num in primes:
print (str(num) + " is a prime number")
The output is shown below .
Enter a number:23 [2, 3, 5, 7, 11, 13, 17, 19, 23] 9 primes were found up to 23 23 is a prime number
I liked the discussions on the following links http://stackoverflow.com/questions/19345627/python-prime-numbers-sieve-of-eratosthenes and PDF ... https://programmingpraxis.files.wordpress.com/2012/09/primenumbers.pdf available on... https://programmingpraxis.com/essays/