Chapter 22: Optimizing Your Code 301
the previous two scores and inserts the third score in its correct place. Each additional time that someone plays the video game, the insertion-sort algorithm compares the new score with the previous high scores to determine where to insert the new score in the top-ten list of scores (assuming that it ranks that high, that is).
If you use a bubble-sort algorithm to sort the top-ten scores, the bubble-sort algorithm needs to examine the list multiple times and compare each score with its neighbor — taking more time than the insert-sort algorithm as a result. In this particular case, you can see how the insert sort-algorithm is more efficient than the bubble-sort algorithm.
As you write your own programs, remember that different algorithms are available for you to use to accomplish identical tasks for your program. Choose the algorithm that runs the fastest for your program.
Fine-Tuning the Source Code
Even if you choose data structures and algorithms with care, you can still optimize your program by fine-tuning the source code. This phrase means that you rewrite portions of your program to make it run faster or require less memory.
Put the condition most likely to be false first
When you use the AND operator in an IF THEN statement, you combine two or more conditions, as follows:
IF (Boolean expression 1) AND (Boolean expression 2) THEN ‘ Follow one or more instructions listed here
END IF
See Chapter 9 for more information about Boolean expressions.
This IF THEN statement runs only after the computer takes time to verify that both Boolean expression 1 and Boolean expression 2 are true. If either one of these Boolean expressions is false, the instructions inside the IF THEN statement don’t run.
So if you intend to use the AND operator, put the expression that’s most likely false in the first part of the AND operation. For example, if Boolean expression 1 is false, the computer doesn’t bother checking to see whether
Boolean expression 2 is true because one false Boolean expression always makes the entire AND operation false.
302 Part V: Algorithms: Telling the Computer What to Do
The moment that the computer determines that the first Boolean expression in an AND operation is false, it doesn’t check the second Boolean expression, thus saving time and helping make your program run just a little bit faster.
Put the condition most likely to be true first
The IF THEN ELSEIF and SELECT CASE statements often need to check several conditions to make a decision, as the following code shows:
IF (Boolean expression 1) THEN
‘Follow one or more instructions listed here ELSEIF (Boolean expression 2) THEN
‘Follow one or more instructions listed here END IF
In this IF THEN ELSEIF statement, the computer first checks to see whether Boolean expression 1 is true. If not, it checks to see whether Boolean expression 2 is true.
But what if Boolean expression 1 is false most of the time and Boolean expression 2 is true most of the time? Then the program wastes time always checking Boolean expression 1 (which is usually false) before it can get to Boolean expression 2 (which is usually true).
To keep your program from wasting time checking a Boolean expression that’s usually false, put the Boolean expression that’s most likely true at the front and the Boolean expression that’s least likely true at the end of the IF THEN ELSEIF statement, as follows:
IF (Boolean expression 2) THEN
‘Follow one or more instructions listed here ELSEIF (Boolean expression 1) THEN
‘Follow one or more instructions listed here END IF
By placing the Boolean expression that’s most likely true at the beginning, you save the computer from wasting time checking one or more additional Boolean expressions that’s usually going to prove false anyway.
Liberty BASIC doesn’t support the IF THEN ELSEIF statement.
This technique also works for SELECT CASE statements, as in the following example:
Chapter 22: Optimizing Your Code 303
SELECT CASE Variable
CASE Value1
‘Follow these instructions if the Variable = Value1 CASE Value2
‘Follow these instructions if the Variable = Value2 END SELECT
SELECT CASE statements check to see whether a variable equals one value (such as Value1). If you put the values most likely to match the SELECT CASE variable up front, you avoid forcing the computer to check a long list of values that are least likely to match anyway.
Although the technique of putting the conditions that are most likely true first may seem trivial, every little bit of time that you save can add up to make a faster and more responsive program.
Don’t run a FOR-NEXT loop needlessly
Loops can gobble up time, so make sure that you choose the right loop. If you’re using a sequential search to find an item in an array, for example, you can use a FOR-NEXT loop. The FOR-NEXT loop can count to make the computer check every position in the array to look for a specific item.
The FOR-NEXT loop runs a specific number of times. What do you think happens if it finds the item that it’s looking for on the first try? The FOR-NEXT loop doesn’t care; it continues looping a fixed number of times anyway, thereby wasting time.
If you use a FOR-NEXT loop, make sure that you absolutely need the program to loop a fixed number of times; otherwise, use the EXIT FOR command to exit the FOR-NEXT loop as soon as possible.
The following BASIC example uses the EXIT FOR command to exit from the FOR NEXT loop at the moment that it finds what it’s looking for. Without the EXIT FOR command, the FOR-NEXT loop always repeats itself 30 times, regardless of whether it needs to loop all 30 times, as the following code shows:
FoundIt = 0
FOR J = 1 TO 30
PRINT “Checking array location”; J
IF MyArray(J) = FindMe THEN
FoundIt = 1
EXIT FOR
END IF
NEXT J
304 Part V: Algorithms: Telling the Computer What to Do
Clean out your loops
You must absolutely place all instructions that you cram inside a loop . . . well, inside the loop. If you put an instruction inside a loop that serves no purpose in the loop, you force the computer to keep running that instruction repeatedly, thereby slowing down your loop and ultimately your program as well.
Consider, for example, the following loop:
FOR J = 1 TO 5000
I = 0
IF MyArray(J) = 55 THEN
PRINT MyArray(J)
END IF
NEXT J
The preceding FOR-NEXT loop repeats itself 5,000 times, but the program never uses the I = 0 instruction inside the FOR-NEXT loop. It forces the computer to run the I = 0 instruction 5,000 times for no reason. To avoid this problem, simply remove the I = 0 instruction from the loop, as follows:
I = 0
FOR J = 1 TO 5000
IF MyArray(J) = 55 THEN
PRINT MyArray(J)
END IF
NEXT J
In the programming world, nesting occurs if you cram one type of control or loop structure inside another one. In the preceding Liberty BASIC program example, an IF THEN statement nests inside a FOR-NEXT loop.
Be especially wary of nested loops. If you nest one loop inside the other, the inner loop runs more often than the outer loop. By ridding the inner loop of any instructions that don’t need to be inside that loop, you avoid forcing the computer to repeat an instruction needlessly.
Use the correct data types
To save memory, use the correct data types. Many versions of BASIC, such as Visual Basic, enable you to declare your variables as integers (as in DIM Num AS INTEGER) or as long integers (as in DIM Num AS LONG). Long integers can range in value from –2,147,483,648 to 2,147,483,647; ordinary integers can range in value only from –32,768 to 32,767.
Chapter 22: Optimizing Your Code 305
A long integer variable, however, gobbles up more memory if you need to stuff a really large number into it, such as 2,147,483,647. If your variables never need to hold such a large number, a smaller data type (such as an integer) works just as well and requires less memory.
Why C/C++ programs can be hard to understand
Programs that you write in C/C++ usually run faster and more efficiently than identical programs written in other languages, such as Pascal or BASIC. But C/C++ has developed a well-deserved reputation for allowing programmers to create cryptic code. One reason is that C/C++ allows a variety of shortcuts that can make your program run faster — but at the sacrifice of readability.
Rather than type x = x + 5 or y = y – 23, for example, C/C++ enables you to use shortcuts, as in the following examples:
x += 5; /* equivalent to x = x + 5 */
y -= 23; /* equivalent to y = y - 23 */
C/C++ also includes something called a prefix or postfix operator that can increment or decrement a variable by one. The following are examples of postfix operators:
x++; /* equivalent to x = x + 1 */
y--; /* equivalent to y = y - 1 */
The prefix operators that are equivalent to the preceding postfix operators are as follows:
++x; /* equivalent to x = x + 1 */
--y; /* equivalent to y = y - 1 */
If you think they look and act alike, you’re almost right. The big difference occurs if you combine postfix or prefix operators into a formula, as follows:
x = y + z++
The preceding formula is actually equivalent to the following two instructions:
x = y + z z = z + 1
You can use the following prefix operator instead:
a = b + --c
This line is equivalent to the following two instructions:
c = c - 1 a = b + c
C/C++ even offers a strange shortcut for an IF ELSE statement that uses a combination of a question mark and a colon, as follows:
printf(“This number is bigger = %d\n”, (x > y) ? x : y);
This line is equivalent to the following normallooking IF ELSE statement:
if (x > y)
printf(“This number is bigger
=%d\n”, x);
else
printf(“This number is bigger
=%d\n”, y);
The shorter, more cryptic version of the IF ELSE statement may take up less space and run faster, but it’s harder to understand at first glance. In using shortcuts, be aware that they can make your program harder to read.