There are various methods to access information in a table “lookup” structure. Indexed access, sequential access, etc but the type of access you go with always depends on the data. Many times on the board I have noticed people asking about setting up some type of scale. Most of them are usually working on a grading program of some sort. How does someone determine if the student got an A or an F and how can a person extend scales to include finer granularity? Well one method is to use what is called a stair-step table access approach. We cover this topic and extending it in this entry of the Programming Underground!
Now most programmers will implement such a grading scale with a simple switch statement (select case in VB) or perhaps a series of if-else statements. That is fine for data that is very regular, and limited to something like 5 grades. How about extending it to a range of 30 grades? How about 100? And you quickly see you will need to go with an approach that involves some sort of search looping scheme. While the example we will show in this entry is the simple grade setup, I have demonstrated this only for simplicity sake. The one great thing about it is that we can easily plug in extra features to super charge it when needed.
The idea behind the stair step approach is that we take in a percentage, check it against one range, if it doesn’t fit, go to another range and test it again. This is usually done sequentially. However, we can easily plug in our own search algorithms to make accessing a table which has 100,000 ranges much faster. Rather than making a possible 100,000 comparisons, we could plug in a semi-binary search (explained in a minute) and use the found value to find the corresponding grade.
This approach is great for irregular data such as statistics. But what do I mean by irregular data? I am talking about data by which the ranges may not be even. For instance… in a grading scheme where an F might be between 1% and 65% a D is between 66% and 68% and a C is between 69% and 75% and a B is 76% to 77% and anything greater is an A. It is not your classic grading scale because F covers 65 percentage points when B covers only 2.
Again this is very easy in something which has only 5 grades. But when the ranges are radical and numerous, a simple if statement or switch just won’t cut it. Then on top of it, if the grading scale changes, readjusting the entire scale to compensate can be a tedious task in a switch.
So how does the stair-step approach help? Lets go with our example.
' Function illustrates stair-step table access approach for irregular data
Private Function findGrade(ByVal percentage As Double) As String
' Create parallel arrays for stair-step approach
' As you can see values map across arrays
Dim ranges() As Double = {50.0, 65.0, 75.0, 90.0, 100.0}
Dim grade() As String = {"F", "D", "C", "B", "A"}
Dim maxGradeLevel As Integer = grade.Length - 1
Dim gradeLevel As Integer = 0
' Sequential search through rangelimits array
' Plucking out matching letter grade if percentage fits
While (gradeLevel < maxGradeLevel)
If (percentage < ranges(gradeLevel)) Then
Return grade(gradeLevel)
End If
gradeLevel += 1
End While
' If not matches were found, then they were greater than 100% so it is an "A"
Return "A"
End Function
In good programming fashion, I have made this into its own separate function. Since it is designed to do one thing (return a letter grade) and do it well, it is perfect for a modular design and for optimal maintainability.
As you can see we start out with two parallel arrays. One which shows the upper most value of each letter grade. The limits of the range if you will. For instance, anything less than 50 is an F and anything less than 75 is a C. We make a matching array which maps the percentage to a letter. The beauty of this setup is that whenever we want to add more limits, we modify the two arrays. If we want to change the grade letter to “P” for pass we can change the letter array without having to manipulate limits. If the limits change, no longer do we have to sift through a ton of if else or switch statements to do so. It also allows us to easily see the limits of each range and how they relate to one another. Again it is great for irregular data. If I want to adjust the limit for B to 95.0, I can change the one limit in the array and we are done.
After our two parallel arrays we go into a while loop which takes an incoming percentage and matches it against the range limits array. Once we find a range which the students percentage fits, the inner if statement will then use the index to access the letter grade and return it. This is why it is important that the arrays be parallel.
Now these arrays could have been setup elsewhere with loops or functions of some sort, but the basic idea is to keep them parallel which is essential to a stair-step approach.
Now that we have the main guts of the function explained, how do we super charge it? Well instead of a sequential search using a while loop, we could modify it to use a semi-binary search on the range limit array. I say semi because while a binary search is designed to find a specific value, your search algorithm would be designed to find the range. This most likely would be a separate search function. Using a binary search will greatly increase the speed of finding the appropriate range value which can then be used to access the corresponding letter grade. Such an algorithm would work best on large arrays where the extra processing power is needed. In theory you could pretty much use any search algorithm modified to find the best range value and once you found the index in the range, use it to fetch the letter.
In our example we also use double data types with nice even .0 endings, but if your data was something like probability statistics where the numbers appear to be something like… .957655 which corresponds to an a tax refund amount of $34,598.76 you can quickly see the advantage of this method.
In most cases an index access approach would be better because this method does incur a bit of a performance hit from a search, but for complex data like presented above with the probabilities, you can’t exactly use an index access approach because you can’t key in entries with numbers like .957655.
This approach, like others, is completely dependent on the data and it is up to you as a programmer to decide if this best matches the type of data you want to map. Obviously if you are going to do only the 5 grades with standard percentages, the stair-step might be a bit of over kill… but if you are indexing and mapping screen coordinates, tables of complex values, or financial information etc, a stair-step technique may help.
So in conclusion a stair step approach is great for lengthy irregular data tables which may require a fine granularity in ranges. The heart of it is to step parallel arrays which map across, search through the range limits, and pull the value from the corresponding index of the other array. It is recommended to use your own search algorithm for extra speed and that it be contained in its own function for easy maintenance. If you have data that may be better served with an index access approach, it would be recommended to use that instead since this technique will incur a bit of a performance hit due to searching. But for data that is not indexable then this is a great alternative.
I hope you have enjoyed this entry. Thanks for reading. 🙂
