Chapter 21: Searching 297

Picking a Searching Algorithm

Sequential searching is the easiest search method to implement and is the fastest for small lists, but for larger lists, sequential searching takes too long. For general use, binary searching is usually faster than sequential searching. The main drawback is that binary searching works only on data that’s already sorted.

Hashing is best for large amounts of data, but it’s more complicated to implement because you need to calculate a hash function to store each item in a specific location in a data structure. Then you face the additional problem of dealing with collisions (if two items share the same hash function).

As a general rule, use sequential searching for small lists or unsorted lists; binary searching for larger, sorted lists; and hashing if you don’t mind calculating hash functions for each item.

298 Part V: Algorithms: Telling the Computer What to Do

Chapter 22

Optimizing Your Code

In This Chapter

Choosing the right data structure

Choosing the right algorithm

Fine-tuning the source code

Using a faster language

Optimizing your compiler

Getting a program to work correctly is often a miracle in itself. But after you do get a program to work and eliminate as many bugs as possible,

the next question is whether to use (or release) the program right away or take some time to optimize it.

Optimization means trying to meet the following three goals (without introducing bugs into the program in the process):

Make the program faster.

Make the program smaller.

Make the program require less memory to run.

As a general rule, software companies rush the new version (such as version 1.0 or version 4.0) of any program out the door just to grab market share. Within a few months, companies usually release slightly modified versions (such as version 1.01 or version 4.1), which fix some bugs (and usually introduce some new ones as well) and optimize the program in some way. In the commercial software market, optimization is usually a luxury, which is why so many programs are known as bloatware — they require globs of memory and hard drive space.

300 Part V: Algorithms: Telling the Computer What to Do

Choosing the Right Data Structure

Every program needs to store data, so you need to choose the right data structure for holding information in your program. An array may seem easy to create, but you must know the number of items that the array needs to hold ahead of time. Make an array too small and your program runs out of space to store additional data, possibly crashing your program. Make an array too large and you risk allocating space for storage that you don’t need, which can cause your program to gobble up more memory than necessary.

More important, the data structure that you choose can affect the efficiency of the sorting and searching algorithms in your program. Compared with sorting items in an array, a sorting algorithm runs much faster rearranging pointers in a linked list.

To find out more about different types of data structures, see Chapters 16 through 19. To learn more about pointers and linked lists, see Chapter 18.

Choosing the Right Algorithm

An algorithm tells the computer how to accomplish a specific task. Think, for example, about all the different ways you can tell your friends to get to your house from downtown. You can tell them to take the highway, which is easier but may take longer. Or you can tell them to take a variety of side streets that ultimately make the trip shorter but make your directions harder to follow.

Deciding which set of directions to give to someone is much like deciding which algorithm to use in your program. If you need to sort a list containing 30,000 names, for example, the bubble-sort algorithm sorts that list much slower than the Quicksort algorithm sorts the same list. (See Chapter 20 for explanations on the bubble-sort and Quicksort algorithms.) After you sort 30,000 names, using a sequential-search algorithm to find a name is much slower than using a binary-search algorithm. (See Chapter 21 for explanations on sequentialand binary-search algorithms.)

For another example of choosing the right algorithm, think of a video game that displays the ten highest scores. Before anyone plays the game, the ten highest scores are all zero. The first time that a person plays the game, the video game lists that person’s score as number one. Each time that someone plays the game again, the video game must sort the scores to display the highest to the lowest ten scores.

For this video game example, the insertion-sort algorithm is most efficient. After the video game shows two scores, the insertion-sort algorithm sorts those two scores from highest to lowest. The third time that someone plays the video game, the insertion-sort algorithm compares the third score with