Programming

Code Complete 2 – Steve McConnell – Table-Driven Methods

I just love Steve McConnell’s classic book Code Complete 2, and I recommend it to everyone in the Software ‘world’ who’s willing to progress and sharpen his skills.

Other blog posts in this series:

Table-driven code can be simpler than complicated logic using ifs. Suppose you wanted to classify characters into letters, punctuation marks, and digits; you might use a logic like this one (Java):

if ( ( ( 'a' <= inputChar ) && (inputChar <= 'z' ) )  || ( ( 'A' <= inputChar ) && (inputChar <= 'Z' ) ) ) {
    charType = CharacterType.Letter;
}
else if ( ( inputChar == ' ' ) || ( inputChar == ',' ) ||( inputChar == '.' ) || ( inputChar == '!' ) || 
    ( inputChar == '(' ) || ( inputChar == ')' ) || 
    ( inputChar == ':' ) || ( inputChar == ';' ) ||
    ( inputChar == '?' ) || ( inputChar == '-' ) ) {

    charType = CharacterType.Punctuation;
} else if ( ( '0' <= inputChar ) && ( inputChar <= '9' ) ) {
    charType = CharacterType.Digit;
}

Two Issues in Using Table-Driven Methods:

  • how to look up entries in the table
  • what to store in the table
    • the result of table lookup can be data, but also an action. In such case, you can store a code that describes the action, or in some languages, you can store a reference to the routine that implements the action. In either of these cases, tables become more complicated.

How to look up entries in the table

You can use some data to access a table directly. If you need to classify the data by month, for example, you can use an array with indexes 1 through 12.

Other data is too awkward to be used to look up a table entry directly. If you need to classify data by Social Security Number, for example, you can’t use the Social Security Number to key into the table directly unless you can afford to store 999-99-9999 entries in your table. You’re forced to use a more complicated approach. Here’s a list of ways to look up an entry in a table:

  • Direct access
  • Indexed access
  • Stair-step access

Direct Access Tables

Suppose you need to determine the number of days per month (forgetting about leap year, for the sake of argument). A clumsy way to do it, of course, is to write a large if statement:

if ( month == 1 ) {
    days = 31;
} else if ( month == 2 ) {
    days = 28;
}
// ...for all 12 months, you get the point
else if ( month == 12 ) {
    days = 31;
}

An easier and more modifiable way to perform the same function is to put the data in a table:

int daysPerMonth [12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

Now, instead of using the long if statement, you can just use simple array access to find out the number of days in a month:

days = daysPerMonth[ month - 1 ];

Indexed access Tables

Sometimes a simple mathematical transformation isn’t powerful enough to make the jump from data like Age to a table key.

Suppose you run a warehouse and have an inventory of about 100 items. Suppose further that each item has a four-digit part number that ranges from 0000 through 9999.

First, if each of the entries in the main lookup table is large, it takes a lot less space to create an index array with a lot of wasted space than it does to create a main lookup table with a lot of wasted space.

For example, suppose that the main table takes 100 bytes per entry and that the index array takes 2 bytes per entry. Suppose that the main table has 100 entries and that the data used to access it has 10,000 possible values.

In such a case, the choice is between having an index with 10,000 entries or the main data member with 10,000 entries. If you use an index, your total memory use is 30,000 bytes. If you forgo the index structure and waste space in the main table, your total memory use is 1,000,000 bytes.

That means you waste 97% less memory with indexed access tables.

Stair-Step Access Tables

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 is that entries in a table are valid for ranges of data rather than for distinct data points.

For example, if you’re writing a grading program, here’s a range of grades you might have to program:

> 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 points. 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.

Here’s the code in Visual Basic that assigns grades to a group of students based on this example.

' 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, 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 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.456935 $0.00
0.546654 $254.32
0.627782 $514.77
0.771234 $717.82

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.

⚠️ Tables can provide an alternative to complicated logic, so ask yourself whether you could simplify by using a lookup table.

Written by Nikola Brežnjak