The Marriage of Theory and Practice

This section introduces two techniques for providing efficiency information on algorithms. The first technique is a theoretical description of the complexity of an algorithm, the O(n) notation. It can be used to compare the merits of underlying concepts of algorithms. This can be done without doing any implementation. The second technique introduced in this section is a timing function that can be used to time implemented code. It is used throughout this book to time suggested coding solutions.

Algorithm Complexity (the O Notation)

The O notation is used to compare the efficiency of different algorithms. This notation expresses the mathematical complexity of an algorithm. It tells you, for example, how the number of elements that is stored in a database influences the amount of time that sorting the data base will take. So, by looking at the O notation of a sorting algorithm, you can determine the impact on sorting time when the number of elements increases. In the O notation the letter O is followed by an expression between brackets. This expression contains the letter n which denotes the number of elements on which the algorithm is to be unleashed.. Here are some example complexities:

• O(n)

• O(n^2)

In the first example—O(n)—the algorithm complexity is a direct function of the number of elements on which the algorithm will be unleashed. This means, for example, that if searching through a database of 1,000 elements takes one second, it will take two seconds to search through a database of 2,000 elements. It also means that three times the number of elements to search will take three times as long. An example of an O(n) algorithm is an algorithm that handles each element the same number of times during processing. Traversing a linked list or an array from beginning to end is an example of this.

In the second example—O(n^2) —the time taken by an algorithm increases with the square of the number of elements; twice as many elements to handle will take four times as long and so on.

Of course these notations can only serve as indications, the exact amount of time that an algorithm will take depends on many variables. Think of how close a base of information already is to being sorted. Also, some searching algorithms use starting assumptions; the closer these are to the actual truth, the faster searching will be. The O notation is therefore used to express general characteristics of algorithms: worst case time, best case time, average time.

So how can you use this notation? Think of a sorting algorithm: When sorting small bases of information you will hardly notice any difference between the performance of different sorting algorithms. However, as data size increases, choosing the right sorting algorithm can easily mean the difference between waiting 500 seconds or 24 hours. This may sound extreme but it can and does happen. The following table demonstrates this by comparing five different complexities found in sorting algorithms (For examples of algorithms refer to Chapter 10):

Elements    O(log2 n)    O(n)      O(n log2 n)    O(n^2)         O(2^n)
10          3            10        33             100            1024
100         7            100       664            10,000         too large
1000        10           1000      9966           1,000,000      too large
10,000      13           10,000    132,877        100,000,000    too large

The first column of the previous table indicates the number of elements to sort. The remaining columns represent worst-case sorting times for algorithms with different complexities. Let's say the base time is one minute. This means that sorting 10,000 elements with an algorithm with an O(log2 n) complexity takes 13 minutes. Sorting the same number of elements with an algorithm with an O(n^2) complexity takes 100,000,000 minutes, which is over 190 years! That is something you probably do not want to wait for. This also means that choosing the right algorithm will improve performance far greater than tweaking the wrong algorithm ever could. What you do when tweaking an algorithm is changing its base time, but not the number of algorithmic steps it needs to take. In the example given by the previous table, this could mean optimizing the O(n^2) algorithm to perform sorting in 100,000,000 * 30 seconds instead of 100,000,000 * 60 seconds. Which means the new implementation is twice as fast, but sadly, it still takes over 80 years to complete its task in worst case, and it still does not compare to the 13 minutes of the O(log2 n) algorithm. What you are looking for is thus an algorithm with as low a complexity as possible.

You have already seen an example of an algorithm with O(n) complexity. But what about those other complexities? Algorithms with O(n^2) complexity are those which, depending on the number of elements, need to do some processing for all other elements. Think of adding an element to the back of a linked list. When you have no pointer to the last element, you need to traverse the list from beginning to end each time you add an element. The first element is added to an empty list, the fifth element traverses the first four, the tenth element traverses the first nine, and so on.

Other complexities you are very likely to come across in software engineering are O(log2 n) and O(n log2 n). The first n in nlog2 n is easy to explain; it simply means that something needs to be done for all elements. The log2 n part is created by algorithmic choices that continuously split in half the number of data elements that the algorithm is interested in. This kind of algorithm is used, for instance, in a game in which you have to guess a number that someone is thinking of by asking as few questions as possible. A first question could be, Is the number even or odd? When the numbers have a limited range, from 1 to 10 for instance, a second question could be, Is the number higher than 5? Each question halves the number of possible answers.

Algorithms with O(1) complexity are those for which a processing time is completely independent of the number of elements. A good example of this is accessing an array with an index: int a = array[4]; no matter how many elements are placed into this array, this operation will always take the same amount of time.

Final remarks on the O notation:

• Constants prove to be insignificant when comparing different O(n) expressions, and can be ignored; O(2n^2) and O(9n^2) are both considered to be O(n^2) compared to O(n) and so on.

• Linking algorithms of different complexities creates an algorithm with the highest of the linked complexities; when you incorporate a step of O(n^2) complexity into an algorithm with O(n) complexity the resulting complexity is O(n^2).

• Nesting algorithms (in effect multiplying their impact) creates an algorithm with multiplied complexity; O(n) nested with O(log2 n) produces O(n log2 n).

The Timing Function

This section introduces a timing function which is used throughout this book to time different solutions to performance problems. It shows how and why it can be used. The source code for the timing function can be found in the accompanying files: BookTools.h and BookTool.cpp.

Consider the Mul/Shift example program in Listing 5.1:

Code Listing 5.1. Mul/Shift Example

#include <iostream.h>
#include "booktools.h"

long MulOperator()
{
    long i, j = 1031;

    for (i = 0 ; i < 20000000; i++)
    {
        j *= 2;
    }
    return 0;
}

long MulShift()
{
    long i,  j = 1031;

    for (i = 0 ; i < 20000000; i++)
    {
        j <<= 1;
    }
    return 0;
}


void main(void)
{
    cout << "Time in MulOperator:   "<< time_fn(MulOperator,5) << endl;
    cout << "Time in shiftOperator:  "<< time_fn(MulShift,5) << endl;
}

This Mul/Shift example program uses two different techniques for multiplying a variable (j) by two. The function MulOperator() uses the standard arithmetic operator *, whereas the function MulShift() uses a bitwise shift to the left <<. Performance of both multiplication functions is timed with a function called time_fn(). This function is explained later in this chapter.

You will agree that the choice between writing j *= 2 or j <<= 1 has no real impact on code reliability, maintainability, or complexity. However, when you write a program that at some point needs to do this kind of multiplication on a large base of data, it is important to know beforehand which technique is fastest (or smallest). This is especially true when multiplication is used widely throughout the sources you write for a certain target system.

So how does this test help you? The result expected of the Mul/Shift example by anyone with a technical background would be that the logical shift is much faster than the multiplication, simply because this action is easier for (most) microprocessors to perform. However, when you run this test using Microsoft's Developer Studio on an x86-compatible processor, you will see that both techniques are equally fast. How is this possible? The answer becomes clear when you look at the assembly generated by the compiler—how to obtain assembly listings is explained in Chapter 4.

The following assembly snippets show the translations of the two multiplication techniques for Microsoft's Developer Studio on an x86-compatible processor.

// Code for the multiplication:
; 16   :             j *= 2;
    shl    DWORD PTR _j$[ebp], 1

// Code for the shift:
; 36   :             j <<= 1;

    shl    DWORD PTR _j$[ebp], 1

Without even knowing any assembly, it is easy to see why both multiplication functions are equally fast; apparently the compiler was smart enough to translate both multiplication commands into a bitwise shift to the left (shl). So, in this situation, taking time out to optimize your data multiplication routines to use shifts instead of multipliers would have been a complete waste of time. (Just for fun, look at what kind of assembly listing you get when you multiply by 3; j *= 3;) Similarly, if you had run the Mul/Shift example on a MIPS, you would have noticed that for this particular processor the multiplication is in fact faster than the shift operator. This is why it is important to find out specific target and compiler behavior before trying to optimize in these kinds of areas.

The Mul/Shift example introduced a second method for you to time your functions (the first method, using profiling as a means of generating timing information, was introduced in Chapter 4.) The Mul/Shift example uses the function time_fn() . You can find the definition of this timing function in the file BookTools.h.

You can find the implementation of the timing function in Listing 5.2 and in the file BookTools.cpp.

The best way to use the timing function is to simply add both booktools files to the makefile of your software project.

Code Listing 5.2. The Timing Function

unsigned long time_fn(long (*fn)(void), int nrSamples = 1)
{
      unsigned long average = 0;
      clock_t tBegin, tEnd;

      for (int i = 0; i < nrSamples; i++)
      {
            tBegin = clock();
            fn();
            tEnd = clock();

            average += tEnd - tBegin;
      }
      return ((unsigned long)average / nrSamples);
}

The time_fn() function receives two parameters: The first is a pointer to the function which it has to time; the second is the number of timing samples it will take. In the Mul/Shift example, you see that the time_fn() function is called first with a pointer to the multiplier function, and then again with a pointer to the shift function. In both cases, five samples are requested. The default number of samples is just one.

The actual timing part of the function is done via the clock() function . This function returns the number of processor timer ticks that have elapsed since the start of the process. By not- ing the clock value twice—once before executing the function which is to be timed, and once after it is finished—you can approximate quite nicely how much time was spent. The following section explains how to minimize external influences to this timing. Note that the overhead created by the for loops in the MulOperator() and MulShift() functions of the MUL/Shift example is also timed. This is of no consequence to the timing results as you are interested only in the relation between the results of the two functions and both functions contain the exact same overhead.

The clock() function is not part of ANSI C++, so its usage can be slightly different per system. This is why several #ifdef compiler directives can be found in the booktools files. The example systems (Linux/UNIX and Windows 9x) used in this book are separated by the fact that the Developer Studio automatically creates a definition _MSC_VER. When using the time_fn() for systems other than the example systems used in this book, you should consult the relevant manuals to check whether there are differences in the use of the clock() function.