使用表驱动法代替复杂的逻辑代码

表驱动法

表驱动法是一种编程模式——从表里面查询信息而不使用逻辑语句(if和case)

使用表驱动法的好处

在适当的环境下,采用表驱动法,所生成的代码会比复杂的逻辑代码更简单、更容易修改,而且效率更高。

举个例子:

假设你希望把字符划分成字母、标点符号和数字三类,也许会用到下面的逻辑链

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

另一方面,如果用一个查询表,就可以把每一个字符的类型保存在一个用字符编码访问的数组里,那么上述的复杂代码片段就可以替换为:

1
charType = charTypeTable(inputChar);

怎么使用表驱动法

需要注意2个问题

  • 怎么从表中查询条目
  • 应该往表里面存什么
    • 数据
    • 动作
      • 用决策表代替复杂的条件
      • 用刚查询表代替复杂表达式

查询表的方式

直接访问表

也就是直接从表里拿对应的数据。

示例:一个月中的天数

假设你需要计算每个月中的天数(为了说明起见,这里不考虑闰年)。笨做法是写个大的if语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
if (month = 1) then
days = 31
else if (month = 2) then
days = 28
else if (month = 3) then
days = 31
else if (month = 4) then
days = 30
else if (month = 5) then
days = 31
else if (month = 6) then
days = 30
else if (month = 7) then
days = 31
else if (month = 8) then
days = 31
else if (month = 9) then
days = 30
else if (month = 10) then
days = 31
else if (month = 11) then
days = 30
else if (month = 12) then
days = 31
end if

实现同样功能的一种更简单的、更容易修改的方法是把这些数据存到一张表中

1
2
dim daysPerMonth() as integer = _
{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}

然后,只需一条语句就可以得出每个月中的天数

1
days = daysPerMonth(month - 1)

如果想在查表版本中考虑闰年,那么代码仍然会很简单,假设leapYearIndex()的取值要么为0,要么为1

1
days = days(month - 1, leapYearIndex())

示例:保险费率

假设需要写一个计算医疗保险费率的程序,这些费率随着年龄、性别、婚姻情况以及吸烟与否的不同情况而变化的。

用逻辑控制结构表示的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
if (gender == Gender.Female) {
if (maritalStatus == MaritalStatus.Single) {
if (smokingStatus == SmokingStatus.NonSmoking) {
if (age < 18) {
rate = 200.00;
}
else if (age == 18) {
rate = 250.00;
}
else if (age == 19) {
rate = 300.00;
}
...
else if (65 < age) {
rate = 450.00;
}
}
else {
if (age < 18) {
rate = 250.00;
}
else if (age == 18) {
rate = 300.00;
}
else if (age == 19) {
rate = 350.00;
}
...
else if (65 < age) {
rate = 575.00;
}
}
}
else if (maritalStatus == MaritalStatus.Married)
...
}

这是简化的逻辑结构,应该已经能让你对事情的复杂度有足够的了解了。

更好的做法是,把这些费率存入所有因素索引的数组里:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public enum SmokingStatus
SmokingStatus_First = 0
SmokingStatus_Smoking = 0
SmokingStatus_NonSmoking = 1
SmokingStatus_Last = 1
end enum

public enum Gender
Gender_First = 0
Gender_Male = 0
Gender_Female = 1
Gender_Last = 1
end enum

public enum MaritalStatus
MaritalStatus_First = 0
MaritalStatus_Single = 0
MaritalStatus_Married = 1
MaritalStatus_Last = 1
end enum

const MAX_AGE as integer = 125

dim rateTable (SmokingStatus_Last, Gender_Last, MaritalStatus_Last, _
MAX_AGE) as double

声明了这个数组后,还需要找一种把数据存进去的方法。你可以使用赋值语句、从磁盘文件中读取数据、计算出这些数据,或者执行任何合适的操作。一旦备好了这些数据,在需要计算费率时,你就可以直接获取结果了:

1
rate = rateTable(smokingStatus, gender, maritalStatus, age)

这种查表操作可读性更好,也更容易修改。

构造查询键值

能直接得到访问表的键值当然好,但是有时候数据并不是那么配合,比如保险费率例子中,原本逻辑为18岁以下的设置了一个费率,为18至65岁之间的人设置了不同费率,为65岁以上的人设置了一个费率。这就意味着,对于17岁以下或者66岁以上的人,你不能直接把年龄用作表的键值,这张表只为一些年龄保存了一些费率。

这就引出了构造查询表键值的问题。你可以用集中不同的方法来构造这些键值:

  • 复制信息从而能够直接使用键值

    为0至17岁之间的每个年龄都复制一份18岁以下的费率,然后直接用age键值访问表,超过66岁的也可以同样处理

    • 优点
      • 表自身结构简单
      • 访问表的操作简单
    • 缺点
      • 冗余信息浪费空间
      • 存在错误的可能性增加
  • 转换键值以使其能够直接使用

    用一个函数将age转换为另一个数值,从而使其能像键值那样使用,比如这个例子,函数可以把0-17岁的都转换成17,超过66的转换成66

  • 将键值转换提取成子程序

索引访问表

有时只用一个简单的数学运算没法把age这样的数据转换成表键值。这类情况中的一部分可以通过使用索引访问的方法加以解决。

使用索引的时候,先用一个基本类型的数据从一张索引表中查询一个键值,然后再用这一键值查出你感兴趣的主数据。

优点在与:

  • 如果主查询表每一条记录都很大,那么创建一个浪费了很多空间的索引数组所用的空间就会更小
  • 即使你用了索引以后没有节省内存空间,操作位于索引中的记录有时也要比操作位于主表中的记录更方便廉价

阶梯访问表

阶梯结构的基本思想是,表中的记录对于不同的数据范围有效,而不是对不同的数据点有效。

比如下面为一组学生评判等级的代码

1
2
3
4
5
6
7
8
9
10
11
12
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

gradeLevel = 0
studentGrade = "A"
while ((studentGrade = "A") and (gradeLevel < maxGradeLevel))
if (studentScore < rangeLimit(gradeLevel)) then
studentGrade = grade(gradeLevel)
end if
gradeLevel = gradeLevel + 1
wend

与其他表驱动法相比,这种方法的优点在于它很适合处理那些无规则的数据。

使用阶梯技术时,需要注意一些细节:

  • 留心端点

    确认你已经考虑到每一个阶梯区间的上界

  • 考虑用二分查找取代顺序查找

    如果查找的列表很大,可以考虑用二分查找替换顺序查找

  • 考虑用索引访问来取代阶梯技术

    如果查找操作比较好使,而且执行速度很重要,那么可以用索引访问法取代阶梯法,即牺牲存储空间来换取速度

参考

  • 《代码大全2》第18章——表驱动法