CMPT
225 Lab - Profiling
In this lab, you will investigate the amount
of work performed by the insert method of a sorted array class. This class maintains
a sorted array by finding the correct index for insertion and moving the values
above that index up one position. As we will see later in the course there are
much better data structures for storing data in order.
Getting
Started
Copy and paste the code provided for you at
the end of this document into the three files - SortedList.h,
SortedList.cpp and ProfileLab.cpp. Then download the text three files (the
links to them are just above the code) into the directory with your source code
files. Build and run the project to make sure that everything is working
correctly; the program should read the animals_rand.txt
file into a SortedList
object and print each string as it is inserted.
Part 1 -
Counting Operations
Modify the
insert method of the FixedSortedList
class to count and print the number of operations that the method performs.
The insert method is shown below.
void SortedList::insert(string
s)
{
// Throw an
error if the array is full
if(current >= max){
throw runtime_error("list is full");
}
// Find
insertion point for item
int pos = current; //insertion point
while(pos > 0 && s
< arr[pos-1]){
arr[pos] = arr[pos-1];
pos--;
}
// Insert new
string
arr[pos] = s;
current++;
return 0;
}
The method contains a single while loop and some statements outside
the loop. The while loop moves every string currently in the array that comes
after the item to be inserted up one position. When the loop terminates the
position variable (pos) contains the
index at which the new string should be inserted.
The goal is to count the amount of work that
the method performs. We will start by printing two separate counts: the count
of the operations that are related to the loop and the count of the operations that
are outside the loop. Each statement (however complex it is) is to be counted
as one operation.
Here is the modified method.
void SortedList::insert(string
s)
{
int count1 = 0;
int count2 = 0;
// Throw an
error if the array is full
count1++;
if(current >= max){
throw runtime_error("list is full");
}
// Find
insertion point for item
int pos = current; //insertion point
count1++;
while(pos > 0 && s
< arr[pos-1]){
arr[pos] = arr[pos-1];
pos--;
count2 += 3;
}
// Insert new
string
count1 += 2;
arr[pos] = s;
current++;
cout << count1
<< " + " << count2;
}
Once you've altered the insert method, the program's
output should look like this:
...
insert bear: 4 + 453
insert mouse: 4 + 180
insert grizzly: 4 + 297
insert dormouse: 4 + 363
insert steer: 4 + 53
insert chimpanzee: 4 + 417
insert okapi: 4 + 165
insert weasel: 4 + 27
If you review the output you can see that the
number of operations tends to increase as the array contains more items,
however the number of insertions is also dependent on which string is being
inserted. We will now investigate this farther while simplifying the
measurement of how much work the insert
method performs.
Barometer
Operations
It should be obvious that as more and more
items are inserted into a FixedSortedList object the number of iterations of the while loop increases (although it varies
dependent on what word is inserted). The other thing that is worth noting is
that the amount of work that the while
loop does is related to the current size of the list (that is, the number of
items currently in the list), whereas the amount of work performed by the
statements outside the loop never changes - it is constant. We can use the while loop comparison as an estimate of
how much work the method is doing, and can therefore refer to it as the
method's barometer operation.
Counting Iterations
Rewrite the insert method so that it returns the number of times that the while
loop's body is executed. Remove the print statement and all the counts except
for the count of the number of times that the while statement is called.
int SortedList::insert(string
s)
{
int count = 0;
// Throw an
error if the array is full
if(current >= max){
throw runtime_error("list is full");
}
// Find
insertion point for item
int pos = current; //insertion point
while(pos > 0 && s
< arr[pos-1]){
arr[pos] = arr[pos-1];
pos--;
count++; //just count number of time while loop iterates
}
// Insert new
string
arr[pos] = s;
current++;
return count;
}
Don't forget
to change the return type of the insert
method in the header file
Comment out the call to profileList. Then remove the
comments from the call to barometer
in the main function and from the call to insert
in the insertCost
function's while loop -- line 74: ops = list.insert(s);. The number of
iterations of the while loop for each call to insert will be printed. Think about the results and try to
determine why the number of operations is so different for the three files.
Once you've done this you've completed the lab!
Files
These are the
files that you will need for the lab
Program
Files
The files for the main program and the SortedList class
are provided below.
John Edgar (johnwill@sfu.ca)