Big Oh allows us to group routines based on their projected performance under different conditions (best case, worst case, etc). Remember that Big Oh is only an estimate. It does not take into account factors specific to a particular environment, such the specific implementation, the type of computer system we are using, and the data that we are processing.
To determine how well or poorly a routine will perform in a particular environment, we need to evaluate the routine in that environment.
In "Part 1" of the laboratory exercise, you will measure the performance of three search routines:
In summary, for the binary search, you are given a sorted array. The idea is to divide the array into two equal parts and narrow down the range of the array to be searched either to the low part of the array or high part of the array. We will continue narrowing down the range until the value is located, or until we realize that the value searched for is not in the array.
The linear search is also known as the sequential search. The idea is start with the first element, and sequentially search through the array until we find a match.
Before we can measure the performance of these routines, we must first develop a set of tools that allow us to measure the execution time.
The general approach will be the following:
The three files are :
| This is the main program. | |
| This is the implementation of the Timer module. It can be compiled into a library once it is bug-free. | |
| This is the header file of the Timer module |
Store the three files on your local PC:
D:\Workarea
Using the procedures discussed in Lab 1 do the following:
A library is a collection of functions or classes. Unlike an object file, a library file stores each function or class, individually. When your program references a function or class contained in a library, it links that function or class and adds its code to your program. This way only functions or classes that you actually use in your program are added to the executable file.
Each function or class defined in the C or C++ standard library
has a header file associated with it.
The header files that relate to the functions that you use in your
programs should be included (using #include)
in your program.
There are two reasons for this:
Libraries can be regarded as pre-compiled functions or classes that do not need to be re-compiled if other parts of your project change. If you have a "bug-free" module (a piece of self-contained code) that could be reused with other projects, you can compile this module to a library. After you link this library to your new project, you will then be able to use any of the functions or classes in this library as if they are defined locally in your project.
One major advantage is that the functions or classes in the library will not be recompiled, which saves time compiling your entire project.
In our example, "timer" is a perfect candidate: it does not contain any bugs and we can use it again in other projects.
In this program, timer.h and timer.cpp define and implement a time measuring class Timer. This class is independent of the kind of program it is measuring. In other words, we can reuse this Timer class to measure the running time of other programs. It naturally follows that once we make this class bug-free, we can compile it into a library. To use this time-measuring class, we simply include the header file (i.e.timer.h) in the program and link the library to this program.
The following shows you how we do this:
Step 1. Create the library
Step 2. Add the necessary files to mylibrary and build the library
Step 3. Build mylibrary
The following message should be displayed in the output area:
------ Build started: Project: mylibrary, Configuration: Debug Win32 ------
Compiling...
timer.cpp
Creating
library...
Build log was saved at "file://d:\Workarea\mylibrary\Debug\BuildLog.htm"
mylibrary - 0 error(s), 0 warning(s)
---------------------- Done ----------------------
Build: 1 succeeded, 0 failed, 0 skipped
Let's just stop for a second. We've created a libray with timer.cpp and timer.h. The library is stored in a file called mylibrary.lib, under the D:\Workarea\mylibrary\Debug folder.
We've got this library, but what do we do with it? It has member functions and data members, but we aren't making use of them--we are just defining them.
Step 4. Link the library to your project
------ Build started: Project: lab4, Configuration: Debug Win32 ------
Compiling...
complexity.cpp
Linking...
Build log was saved at "file://d:\Workarea\lab4\Debug\BuildLog.htm"
lab4 - 0 error(s), 0 warning(s)
---------------------- Done ----------------------
Build: 1 succeeded, 0 failed, 0 skipped
Finally, click on Debug->Start Without Debugging to run
your program.
Your output should look like the following:
Click here To get the zipped files for this exercise
Your primary tasks for this exercise are:
Steps include:
Enter the number of keys (must be at least 1000) : 1000
Search Time per search (secs.)
-------------- -----------------------
linearSearch 2.5e-006
binarySearch 3.1e-007
unknownSearch 4.85e-006
Press any key to continue
The 2.5e-006 is equivalent to 2.5*10-6 or 0.0000025.
Suggestion: The increments for the "Search time" axis have been left up to you. First, write everthing as 10-6 seconds. Then, create five tick marks along the y-axis: 10, 20, 30, 40, and 50.
Click here To get the zipped files for this exercise
Your primary tasks for this exercise are:
Suggestion: The increments for the "Search time" axis have been left up to you. First, write everthing as 10-4 seconds. Then, create six tick marks along the y-axis: 300, 600, 900, 1200, 1500, and 1800.
|
[an error occurred while processing this directive] |
|
| |
|
|
Copyright: Department of Computer Science, University of Regina.