Sentinels

As I mentioned earlier, one of the dangers of using an Until loop is that it assumes that the test expression will eventually become logic True. That's not always the case, however. How can you address this problem and still use the Until loop?

One way is to know the size of the list you're searching before entering the loop. Often, this isn't a problem. For example, if you're searching a list of names , they might be stored in a String array. You can then use the UBound() function to find out how large the array is. You might use code like that shown in Listing 13.6.

Listing 13.6 Using a Do Until to Search for a Name

 Dim i, ListSize as Integer ListSize = UBound(Names) Do Until Names(i) = LookingFor  If i = ListSize then   Exit Do  End If  i += 1 Loop 

In this code, we march through the list of names looking for a match. However, because we've set ListSize to the number of names in the list, the If statement with its Exit Do guarantees that we won't have an infinite loop. The loop will terminate even if the person's name isn't in the list.

Although the code in Listing 13.6 works, it can be improved. It's not uncommon for today's databases to have several million names in them. Anything we can do to speed up things in loops that might execute millions of times will improve the program. Consider the changes reflected in Listing 13.7.

Listing 13.7 Using a Sentinel in a Do Until

 Dim i, ListSize as Integer ListSize = UBound(Names) ReDim Preserve Names(ListSize + 1)  ' Make room for 1 more Names(ListSize + 1) = LookingFor Do Until Names(i) = LookingFor  i += 1 Loop If i <= ListSize Then  MessageBox.Show("Found it!") Else  MessageBox.Show("Name not in list.") End If 

Let's see what the impact of our changes is. First, we set LimitSize to the current size of the list. Let's assume that LimitSize is 50,000. We then use ReDim to resize the array for one more name. (We use the Preserve keyword so the existing list of names remains intact.) The next statement assigns the name we're looking for into this last empty slot in the Name() array. This entry is called a sentinel. Therefore, element 50,001 in the Name() array becomes our sentinel. The sentinel guarantees that the Name() array now contains the name we're looking for.

Now look at the loop statement block. It no longer contains the If statement to check whether we're at the end of the array. Why bother? We know we will at least find a match on the sentinel at element 50,001 and exit the Do Until loop. The sentinel guarantees that we'll exit the loop.

Once we're finished executing the loop, all we have to do is decide whether we really did find a match, or if it was the sentinel that terminated the loop. If i is less than or equal to ListSize , we must have found a real match in the list of names. That is, if i is less than 50,001, the Do Until loop terminated because it found a match in the list of names. If i equals 50,001, we know we found the sentinel, which means the name was not in the list. The If statement at the bottom of Listing 13.7 shows how you might handle the decision as to which match was found.

The improvement is that we've added a few new statements outside the loop to get rid of an If statement inside the loop. If we're searching a list with thousands of names in it, we avoid executing that If statement on each pass through the loop. A thousand here, a thousand there, and pretty soon the time savings starts to add up.

In certain situations, sentinels can make a big difference in the performance of a program. One of the most time-consuming aspects of a program's execution time is executing program loops. Loops are frequently a major cause of poor performance, or bottlenecks, in a program. If you're unhappy with the time it takes for your program to execute, loops are often a fruitful place to start looking for bottlenecks. In some cases, a sentinel might just be the solution you need to break the bottleneck.