- [Craig] In this video,
we take another look at how we evaluate a program's fitness for purpose and efficiency.
We first covered this topic in a more abstract way back under topic one.
(uplifting piano jingle)
So we've covered already the different searching and sorting algorithms.
You have to know two for searching,
binary and linear,
and two for sorting, merge and bubble.
But which version of each of these algorithms is more efficient?
And what do we even mean by the efficiency of an algorithm?
Well, we introduced this topic back under the video called algorithm efficiency under topic 1A.
But now we're going to look at it with some actual examples of Python programs.
So in the paper two on-screen exam,
you need to be able to use logical reasoning and test data
to evaluate a program's fitness for purpose and efficiency;
for example, the number of compares or the number of passes through a loop, et cetera.
So we're going to use the test data above.
So this is an array,
or more appropriately, a list in Python.
It's called items, and it contains 20 data items.
And we want to find the number 37, which exists in the 12th location,
or should I say the 13th location but at index 12
because of course, we start at zero.
And we're going to try and find it using a linear search and a binary search
and prove which one is better and more efficient by actually writing some code in the algorithms.
So here is the code for a linear search.
You can see I've hard-coded the test data we're using for the items list at the top there.
And the next line says items to find,
and the user enters a number and we're going to get them to enter 37.
Now I'm not going to walk through the details of this algorithm,
we covered that in a previous video, which you can see on the screen.
And likewise, here's the code for a binary search.
Again we've hard-coded our test data, our items list,
and again, I'm asking the user to enter a number and we'll get them to enter 37.
And likewise, you can watch a previous video if you need a refresh on how binary search works.
So first of all, you can see I've actually altered the original linear search program slightly here
and added three extra lines of code,
and this is for testing purposes.
So study the three extra lines of code.
Can you work out what their purpose is?
When you think you know, unpause the video.
So they're keeping track of how many times we iterate or go through the while loop.
In other words, how many compares the algorithm has to do.
Every time we go around that while loop,
we're comparing another element or index in our items array.
At the end of the program,
as well as printing out that we've found the number we're after and the position,
we're also going to print out the total value for compares,
which has been going up by one each time
so we can actually see and prove with these lines of test code how long it's taking
or how many iterations through the loop it's taking to find the value 37.
We've added the same three lines to our binary search algorithm,
so again, we can see how many times we're going through the loop.
Now, when adding additional lines of code like this to a program
for the purpose of testing, tracking and debugging,
you've got to think carefully about where those actual lines of code go,
especially ones that increment any values.
Having done this though,
you can see that with the linear search,
we enter the number 37, it's found at index position 12,
which of course is the 13th position,
and we correctly get told the item was found after 13 compares.
When we run the binary program with the same additional lines of code,
we can see again it finds it in position 12,
but it's found it only after four iterative comparisons
or four passes through the while loop.
So we've managed to prove here with some extra lines of code in our Python program
which of the algorithms was more efficient in this situation
using the test data that we provided.
So we're going to return to this example,
which we first used back in the video where we covered algorithm efficiency in topic one.
We have two functions called sum integers, and they both take a single parameter,
n, which is a number.
No matter what number is passed in,
they add up that many numbers.
So if 10 is passed in, it adds up the numbers 1 plus 2 plus 3 plus 4, up to 10.
So they return 55.
So both of these algorithms do exactly the same thing.
The question is, which one is more efficient?
Okay, so because these videos are purely focusing on paper two, which you'll be doing in Python,
we're going to ditch the pseudocode and actually write this out in syntactically correct Python.
So there's our first function for sum integers,
and this one's using a loop.
So I've written a function there called sum integers loop,
and you can see it takes in a single parameter
and then it performs the calculation from the pseudocode.
And at the end, I've added a print line that says sum integers loop used this many iterations.
So again, I'm using a similar technique to track how many times it goes through.
There's the second example of sum integers.
Now remember, this one's not using a loop at all.
And if you remember back to the original video, this just performs the single calculation,
so we know this is going to run in a single line of code, but I've coded it up there.
And finally at the end,
I've got two print statements,
they simply print out the name of the function that they're calling,
and then it calls the function and returns the value to get put onto the screen.
So here's the program running in its entirety,
you can see it outputs sum integers loop used 10 iterations,
so that's obviously because the top function,
sum integers loop,
went around that for loop 10 times,
and then it outputs the result of that function, which is 55.
It then executes the second function,
sum integers, which gets printed to the screen
and of course, that outputs the value 55 as well
because they do the same thing.
But we can see that the bottom function, sum integers,
is more efficient because only one sequence of two instructions are required
compared to the 10 iterations in the sum integers loop version.
(uplifting piano jingle)