查看原文
其他

表驱动法

架构精进之路 架构精进之路 2022-09-05

什么是表驱动法?

是一种编程模式,从表里查找信息而不使用逻辑语句(if 和case)。事实上,凡是能通过逻辑语句来选择的事物,都可以通过查表来选择。对简单的情况而言,使用逻辑语句更为容易和直白,但随着逻辑链的越来越复杂,查表法也就愈发显得更具有吸引力。

使用总则

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


用一个例子来说明下:

假设你需要把字符划分为字母、标点符号和数字三类。

使用复杂的逻辑对字符进行分类

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;}

假设用一个查询表(lookup table),就可以把每一个字符的类型保存在一个用字符编码访问的数组里,那上述复杂代码块可以替换为如下:

使用查询表对字符分类

charType = charTypeTable[inputChar];


使用表驱动法的两个问题

1)如何从表中查数据?

  • 直接访问

  • 索引访问

  • 阶梯访问

2)在表里存些什么?

  • 数据

  • 动作(action)-描述该动作的代码/该动作的子程序的引用。



1、直接访问

和所有直接查询表一样,直接访问代替了更为复杂的逻辑控制结构。之所以说他们是“直接访问”的,是因为你无须绕很多复杂的圈子就能够在表里面找到想要的信息。


例子:

假设你需要计算每个月中的天数。

常规笨方法如下:

if(month == 1) { days = 31;} else if (month = 2){ days = 28;} else if (month = 3){ days = 31;} else if (month = 4){ days = 30;} else if (month = 5){ days = 31;} else if (month = 6){ days = 30;} else if (month = 7){ days = 31;} else if (month = 8){ days = 31;} else if (month = 9){ days = 30;} else if (month = 10){ days = 31;} else if (month = 11){ days = 30;} else if (month = 12){ days = 31;}

把这些数据存到一张表里,创建这张表:

[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

这样就只需一条简单的数组访问语句就可以了:

days = daysPerMonth(month - 1);


当然,我们希望能够将数据作为键值直接访问表,这样既简单又快速,但是问题或者数据通常并不是这样友好。引出了构造查询键值的方法:

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

      使age能像键值一样用于费率表的种查询方法是将1-17岁之间的年龄都复制一份18岁以下的费率,然后直接用该age键值来访问表。同样也可以用同样的方法来处理66岁以上的情况。

这样优点在于表自身结构非常简单那,访问表的逻辑也很简单;缺点在于复制生成的冗余信息会浪费空间,也即是利用空间换效率。


2)转换键值以使其能够直接使用

      使age能像键值一样用于费率表查询的第二个方法是用一个函数将age转换为另一个数值。在此例子中,该函数必须把所有介于1-17直接的年龄转换成一个键值,例如17,同时把所有超过66的年龄都转换成另一个键值,例如66。

这样在检索前可以用min()和max()函数来做这一转换。例如,你可以用下述表达式:max(min(66, age), 17) 来生成一个介于17-66之间的表键值。

3)把键值转换提取城独立子程序

      如果你必须要构造一些数据来让它们像表键值一样使用,那就把数据到键值的转换操作提取成独立的子程序。这样可避免在不同位置执行了不同的转换,也使得转换操作修改起来更加容易。

如在程序语言中编写逻辑函数 KeyFromAge(),甚至使用HashMap来定义好逻辑上的键值映射关系也是OK的。

2、索引访问

有时只用一个简单的数学运算还无法把age这样的数据转换成为表键值,这种情况可以通过索引访问的方法加以解决。

索引应用:先用一个基本类型的数据从一张索引表中查出一个键值,然后在用这一键值查出需要的主数据。

举例:

有百余件商品,商店物品编号(范围0000-9999)

创建两张表:索引表(0-9999),物品(查询)表(0-100)

索引表与查询表

索引访问有两个优点:

  • 如果主查询表的每条记录都很大,那创建一个浪费了很多空间的数组所用的空间,要比建立主查询表所用的空间小得多。

  • 操作索引中的记录比操作主查询表的的记录更方便,编写到表里面的数据比嵌入代码的数据更容易维护。

例如:有一张员工姓名、雇佣时间和薪水的表,你可以生成一个索引按照员工姓名访问该表;生成另一个索引表按照雇佣时间来访问该表;以及生成第三个索引按照薪水来访问该表。
3、阶梯访问

这种访问方法不像索引结构那样直接,但是它要比索引访问方法节省空间。

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

通过命中的阶梯层次确定其归类


举例:

一个等级评定的应用程序,其中“B”记录所对应的范围是75.0%-90.0%

>= 90.0%      A

<90.0%         B

<75.0%         C

<65.0%         D

<50.0%         F


这种划分范围用在查询表中是不合适的,因为你不能用简单的数据转换函数来把表键值转换成A-F字母所代表的等级。用索引也不合适,因为这里用的是浮点数。

使用阶梯方法,把每一区间的上限写入一张表里,然后写一个循环,按照各区间的上限来检查分数。当分数第一次超过某个区间的上限时,你就知道相应的等级了。

在应用阶梯方法的时候,必须谨慎的处理范围的端点。

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 grad to a student based on the student's scoreGradeLevel= 1 StudentGrade = ”A" while( StudentGrade = "A" and GradeLevel < MaxGradeLevel ) if( StudentScore < RangeLimit( GradeLevel ) ) then StudentGrade = Grade ( GradeLevel) end if GradeLevel = GradeLevel + 1 Wend

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

在使用阶梯访问时需要注意的一些细节:

1)留心边界端点

注意边界:< 与 <=,确认循环能够在找出最高一级区间后恰当地终止。

2)考虑用二分查找取代顺序查找

如果列表很大,可以把它替换成一个准二分查找法,从头查找是很耗费性能的

3)考虑用索引访问来取代阶梯访问

阶梯访问中的查找操作可能会比较耗时,如果执行速度很重要,那可以考虑用索引访问来取代阶梯查找,即以牺牲存储空间来换取速度。


总结
  1. 表驱动法提供了一种复杂的逻辑和继承结构的替换方案。如果你发现自己对某个应用程序的逻辑或者继承关系感到困惑,那是否可以通过一个查询表来加以简化。

  2. 使用表的关键决策是决定如何去访问表,可以采取直接访问、索引访问或阶梯访问

  3. 使用表的另一项关键决策是决定如何去把什么内容放入表中

  4. 需要保存浮点数和范围数时,使用阶梯访问的形式。




往期热文推荐:







「技术架构精进」专注架构研究,技术分享


Thanks for reading!

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存