18.4. Stair-Step Access Tables

 < Free Open Study > 

Yet another kind of table access is the stair-step method. This access method isn't as direct as an index structure, but it doesn't waste as much data space.

The general idea of stair-step structures, illustrated in Figure 18-5, is that entries in a table are valid for ranges of data rather than for distinct data points.

Figure 18-5. The stair-step approach categorizes each entry by determining the level at which it hits a "staircase." The "step" it hits determines its category


For example, if you're writing a grading program, the "B" entry range might be from 75 percent to 90 percent. Here's a range of grades you might have to program someday:

90.0%

A

< 90.0%

B

< 75.0%

C

< 65.0%

D

< 50.0%

F


This is an ugly range for a table lookup because you can't use a simple data-transformation function to key into the letters A through F. An index scheme would be awkward because the numbers are floating point. You might consider converting the floating-point numbers to integers, and in this case that would be a valid design option, but for the sake of illustration, this example will stick with floating point.

To use the stair-step method, you put the upper end of each range into a table and then write a loop to check a score against the upper end of each range. When you find the point at which the score first exceeds the top of a range, you know what the grade is. With the stair-step technique, you have to be careful to handle the endpoints of the ranges properly. Here's the code in Visual Basic that assigns grades to a group of students based on this example:

Visual Basic Example of a Stair-Step Table Lookup
' set up data for grading table Dim rangeLimit() As Double = { 50.0, 65.0, 75.0, 90.0, 100.0 } Dim grade() As String = { "F", "D", "C", "B", "A" } maxGradeLevel = grade.Length -- 1 ... ' assign a grade to a student based on the student's score gradeLevel = 0 studentGrade = "A" While ( ( studentGrade = "A" ) and ( gradeLevel < maxGradeLevel ) )    If ( studentScore < rangeLimit( gradeLevel ) ) Then       studentGrade = grade( gradeLevel )    End If    gradeLevel = gradeLevel + 1 Wend

Although this is a simple example, you can easily generalize it to handle multiple students, multiple grading schemes (for example, different grades for different point levels on different assignments), and changes in the grading scheme.

The advantage of this approach over other table-driven methods is that it works well with irregular data. The grading example is simple in that, although grades are assigned at irregular intervals, the numbers are "round," ending with 5s and 0s. The stair-step approach is equally well suited to data that doesn't end neatly with 5s and 0s. You can use the stair-step approach in statistics work for probability distributions with numbers like this:

Probability

Insurance Claim Amount

0.458747

$0.00

0.547651

$254.32

0.627764

$514.77

0.776883

$747.82

0.893211

$1,042.65

0.957665

$5,887.55

0.976544

$12,836.98

0.987889

$27,234.12

 


Ugly numbers like these defy any attempt to come up with a function to neatly transform them into table keys. The stair-step approach is the answer.

This approach also enjoys the general advantages of table-driven approaches: it's flexible and modifiable. If the grading ranges in the grading example were to change, the program could easily be adapted by modifying the entries in the RangeLimit array. You could easily generalize the grade-assignment part of the program so that it would accept a table of grades and corresponding cut-off scores. The grade-assignment part of the program wouldn't have to use scores expressed as percentages; it could use raw points rather than percentages, and the program wouldn't have to change much.

Here are a few subtleties to consider as you use the stair-step technique:

Watch the endpoints Make sure you've covered the case at the top end of each stair-step range. Run the stair-step search so that it finds items that map to any range other than the uppermost range, and then have the rest fall into the uppermost range. Sometimes this requires creating an artificial value for the top of the uppermost range.

Be careful about mistaking < for <=. Make sure that the loop terminates properly with values that fall into the top ranges and that the range boundaries are handled correctly.

Consider using a binary search rather then a sequential search In the grading example, the loop that assigns the grade searches sequentially through the list of grading limits. If you had a larger list, the cost of the sequential search might become prohibitive. If it does, you can replace it with a quasi-binary search. It's a "quasi" binary search because the point of most binary searches is to find a value. In this case, you don't expect to find the value; you expect to find the right category for the value. The binary-search algorithm must correctly determine where the value should go. Remember also to treat the endpoint as a special case.

Consider using indexed access instead of the stair-step technique An index-access scheme such as the ones described in Section 18.3 might be a good alternative to a stair-step technique. The searching required in the stair-step method can add up, and if execution speed is a concern, you might be willing to trade the space an extra index structure takes up for the time advantage you get with a more direct access method.

Obviously, this alternative isn't a good choice in all cases. In the grading example, you could probably use it; if you had only 100 discrete percentage points, the memory cost of setting up an index array wouldn't be prohibitive. If, on the other hand, you had the probability data listed earlier, you couldn't set up an indexing scheme because you can't key into entries with numbers like 0.458747 and 0.547651.

In some cases, any of the several options might work. The point of design is choosing one of the several good options for your case. Don't worry too much about choosing the best one. As Butler Lampson, a distinguished engineer at Microsoft, says, it's better to strive for a good solution and avoid disaster rather than trying to find the best solution (Lampson 1984).

Cross-Reference

For more on good approaches to choosing design alternatives, see Chapter 5, "Design in Construction."


Put the stair-step table lookup into its own routine When you create a transformation function that changes a value like StudentGrade into a table key, put it into its own routine.

 < Free Open Study > 


Code Complete
Code Complete: A Practical Handbook of Software Construction, Second Edition
ISBN: 0735619670
EAN: 2147483647
Year: 2003
Pages: 334

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net