维基百科

控制表

控制表是一个决定控制流程或是主要影响控制流程的表。关于控制表的结构或内容没有硬性的规定，其特点是其可以影响控制流程的能力。这类表格的设计有时称为“表格驱动设计”[1][2]（不过后者多半是指由外部的表格自动生成代码，而不是在程序中的表格）。以有限状态机为基础的自动机编程有时会用控制表为其实现方式。若控制表有几个不同的层次，其行为就类似UML状态机（英语：UML state machine）。

一个简单的控制表，依单一输入变量决定程序流程，每个表格项目包括一个可能的输入数值，及对应动作的副程序，若编程语言不支持指向副程序或函数的指针，也可以用副程序的编号代替

控制表有时会以关系表（英语：association list）的方式表示，其中会有对应的条件表示式及子程序。控制表可以简化一些类似的程序叙述，而且若是二维的控制表，在阅读及更新上都比一维特性的代码要容易维护，有时控制表甚至可以让非程序员来维护。计算机科学家高德纳在1974年提出的论文《Structured Programming with go to Statements》中就提到“多路分支是一种重要的程序设计技术，但常常被一些数量不足的if指令取代”[3]。

一般使用方式

编辑

高级使用方式

编辑
类似字节码，但常会配合控制表的结构中隐含的动作而运作。

表格结构

编辑

控制表可以是多维的，可以是固定长度或是可变长度（英语：variable length code），而且具有可在不同系统平台之间使用的可携性，系统平台变动时只针对解释器修改软件，不会变动隐含在控制表的结构及其内容中的算法。控制表的结构可能类似一个multimap的关系表，会将资料值（或资料值的结合）映射到一个或多个要进行的函数。

一维表格

编辑

控制表可以是一维表格的形式，这可能也是最简单的控制表。一维表格的控制表将原始数据转换为副程序的偏移值、编号或是指针，转换方式可能是直接以原始数据（英语：raw data）为索引进行查表，或是将原始数据进行简单的数学处理后再作为表格的索引。查表的过程不会用到线性搜索或是二分搜索，可以在常量时间内完成。对于大部分的计算机体系结构而言，上述处理可以利用二或三个机器语言的指令来达成，不需进行比较或是循环处理。此技术一般称为“Trivial hash function”，若特别用在分支表中，则称为双重分派（英语：double dispatch）。若要使用一维表格的控制表，数据的可能范围需要很小，像ASCII或EBCDIC字符都只有255个可能资料，符合此条件，若数据是用ASCII字符表示，且可以确认其中有些数据不可能出现，其对应的控制表会更小。

以下是将ASCII的资料（A,D,M,S）转换为副程序编号（1,2,3,4）的控制表，此控制表为一维数组，可以在常量时间内完成转换。

（下表只列出有使用的部分，中间副程序编号为0的部分省略，下表中的前二栏只作说明用，只有第三栏才是控制表）

ASCII 十六进制 Array
空字符 00 00
.. .. 00
@ 40 00
A 41 01
.. .. 00
D 44 04
.. .. 00
M 4D 03
.. .. 00
S 53 02

在自动机编程及伪会话交易（英语：pseudoconversational transaction）程序中，若相异程序状态的个数不多，可以有效的用控制变量来建立整个程控流程的模型。

上述一维的控制表可以视为将原始资料直接翻译为对应副程序的数值，只是原始资料的种类不多，或者有够快的存储器时，此作法可以快速的进行资料验证及对应副程序数值的转换。

分支表

编辑

分支表（英语：branch table）是由连续的机器代码branch或jump指令组成的一维数组，其目的是可以进行多路分支（英语：multiway branch），依编号执行对应的指令。有时编译器优化处理switch指令（英语：switch statement）时，若输入值的范围不大，也可能会用分支表来实现switch指令。

分支表比一连串的If指令要短，但分支脚本仍然会重复出现，而上述的控制表只包括副程序编号，执行上所需时间会分支表要短。

多维数组

编辑

控制表常常也可以视为是真值表或是决策表（英语：decision table）的可执行版本。控制表中常包括了命题及一到多个的对应行动。行动一般会是通用的副程序或是客户建立的副程序，程序扮演类似“解释器”的作用，依命题是否符合执行对应的行动，程序类似一个虚拟机，执行控制表的内容，其抽象化的程度较高。

多维数组的控制表也可以用编程语言中的switch指令来代替，而其条件可以利用逻辑运算的AND和OR指令组合出复杂的条件，条件成立时也可以执行不止一个的副程序。不过各高级语言中的switch指令在语法上可禸能仍然有些差异，而且可能有些语言的switch指令不允许复杂的条件。相较于switch指令，控制表没有编程语言的相依性，在处理上会比较单。

控制表的内容

编辑

控制表保留了传统程序的本质，去除了编程语言的语法及和平台有关的成分（例如IF/THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL），将程序浓缩为变量（例如input1）、数值（例如'A','S','M'及'D')及副程序的识别符号（例如'Add','subtract,..'或#1, #2,..）。控制表的结构本身隐含了有关的程序，包括比较是否相等、执行副程序等。

多维的控制表至少会包括一组数值和动作，可能还会有额外的运算符或其他信息，例如输入或输出资料的位置、长度及格式，供控制表相关程序进行资料转换。控制表可能会包括索引或指向要执行副程序的指针或相对位置。

以下举例用的控制表只接受一个输入。

控制表结构中隐含的条件及动作

（隐含）IF = （隐含）处理
资料 动作
资料 动作

（这种资料及动作对应的情形类似事件驱动程序设计，但后者的事件本身会有异步的特性）

控制表可以包含的资料种类和使用的编程语言有关，汇编语言没有资料类型的限制，允许的资料最多，其至在动作部分可以包括对应的代码地址。一般控制表会包括各个可能的数值及对应副程序的指针。若有些语言没有指针的概念，则其动作部分可以用一个代码的编号表示，再用switch指令执行对应的副程序。

控制表中可以加入注解或其他文字说明，可以使控制表除了包括其程序逻辑以外，也会提升其可读性。若是在程序开发前就已制作手写的决策表，枚举不同的情形及其动作时，控制表可以用来比对是否符合原始程序规格。控制表中也可以包括一些计数器，提供不同情形的统计信息，可以在程序执行中自动进行优化，或是之后由人工修改程序，进行优化。

控制表可以当成程序的静态变量，利用文字档存储，放在数据库中，也可以在程序启动时依参数动态建立。

性能考量

编辑

乍看之下，使用控制表会增加运算负担（英语：Computational overhead），因为需要一个程序来查表及执行对应的副程序。不过将执行的程序及用表格表示的逻辑分开，可以更清楚的让每个程序执行各自的机能。就像是表格的应用程序一様，为了显示其结果，表格软件将复杂的公式变成可以有效用表格显示的方式。

控制表的例子

编辑

以下的示例是以四则运算为例，为简单起见只接受一个输入，示例的目的只是展示如何用控制表来取代一般程序的指令来调整控制流程。控制表也可以接受多个输入，若利用有层次的链接式控制表，也可以达到结构化程序设计的目的（可能可以使用缩进来突显控制表中的副程序）。

CT1的控制表是一个简单的查找表，第一栏是要测试的资料，若资料等于第一栏的数值，会执行第二栏指定的副程序。实务上这就是一个多路分支的形式来进行，也是一种动态分配（英语：dynamic dispatch）的形式，最后一列是对应资料不符合任一数值时的处理。

CT1

输入1 指针
A -->Add
S -->Subtract
M -->Multiply
D -->Divide
? -->Default 
 static const char  CT1[] = {  "A",   "S",        "M",        "D" };                          /* permitted input  values */
 static const void *CT1p[] = { &&Add, &&Subtract, &&Multiply, &&Divide, &&Default};           /* labels to goto & default*/
 for (int i = 0; i < sizeof(CT1); i++)      /* loop thru ASCII values                                                    */
   {if (x == CT1[i]) goto *CT1p[i]; }       /* found --> appropriate label                                               */
 goto *CT1p[i+1];                           /* not found --> default label                                               */

若控制表改为一个有256个元素的一维数组，直接将数值转换为对应副程序的编号，即利用元素大小为字节的数组进行索引映射（英语：index mapping），可以在常量时间  内找到对应的副程序，CT1p数组也可以用指向副程序的指针代替标记，就不需用到goto指令，但因为调用副程序需要的系统服务（英语：Housekeeping (computing)）较多，会对程序性能略为影响。 

 static const void *CT1p[] = {&&Default, &&Add, &&Subtract, &&Multiply, &&Divide};
 /* the 256 byte table, below, holds values (1,2,3,4), in corresponding ASCII positions (A,S,M,D), all others set to 0x00 */
 static const char CT1x[]={
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x01','\x00','\x00','\x04','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x03','\x00','\x00',
             '\x00','\x00','\x00','\x02','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x03','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',
             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00'};
 /* the following code will execute in constant time, irrespective of the value of the input character (x)                    */
 i = CT1x(x);            /* extract the correct subroutine index from table CT1x using its ASCII value as an index initially  */
 goto *CT1p[i];          /* goto (Switch to) the label corresponding to the index (0=default,1= Add,2= Subtract,.) - see CT1p */

以下的例子说明只要编程语言支持依编号分支到各副程序的语法（副程序放在一个启始编号为0的数组中），就可以达到类似上述程序的二维控制表的效果。下例中用数组CT2来决定指针数组CT2P的编号，若编程语言不支持指针数组，也可以用类似SWITCH指令的方式处理，SWITCH指令中可以直接处理输入，或是跳到对应的副程序再处理输入。

CT2

输入 1 副程序编号
A 1
S 2
M 3
D 4
? 0
CT2P 指针数组
指针数组
-->default
-->Add
-->Subtract
-->Multiply
-->Divide
-->?other

以下的例子不使用实际的代码，只用二个数组来表示，只要是支持依编号分支到数组中（数组是从0开始编号）特定副程序的编程语言皆可适用。可利用数组CT2将输入的资料转换为副程序数组（CP2）的编号，若此编程语言不支持指针，也可以用类似SWITCH指令的作法取代CP2数组的查表，依序将输入值和每一个可能的资料比对，若资料符合，跳到对应的副程序中。

CT2

输入1 副程序编号
A 1
S 2
M 3
D 4
? 0

此例可以在不使用查表法的情形下，很有效率的将ASCII输入资料（A、S、M、D或其他）转换为指针数组的编号，不过为了和上例一致，仍使用数组表示。

CT2P 指针数组
指针数组
-->default
-->Add
-->Subtract
-->Multiply
-->Divide
-->?other

也可以配合实际的应用，创造有更多字段的控制表，控制表会比上例复杂，但可以在更多测试输入时有更多测试条件的组合，而不是只比对单一测试条件。以下的控制表有增加一个输入资料（小写的a、s、m、d），若输入满足其中一个资料，该测试条件就成立，也就会进行对应的动作，另外也增加一栏来计算实际执行时各个条件成立过几次。

CT3

输入1 替代输入 副程序编号 计数
A a 1 0
S s 2 0
M m 3 0
D d 4 0
? ? 0 0

上述的控制表更接近过程化编程中用到的条件指令，不过实际语言中用到的一些指令已转换为处理控制表的“解释器”程序，控制表只看到各个输入及其对应的副程序编号。 结构化程序设计或是“无Goto代码”也可以配合经过适当设计及缩进的控制表结构使用。

表格驱动评级

编辑

在电信领域中决定一通电话特定费率的“电信评级”应用中，“表格驱动评级”（table-driven rating）技术描述将控制表应用在规则可能常常会因为市场外力而进行调整的情形，在许多情形下，决定计费的表格会由非程序设计者花一点时间进行修改及维护，更改需要的时间很短。[4][5]

若其算法不是事先建在解释器中，而是由程序决定此算法，此技术称为“以规则为基础的评价”（Rule-based Rating），但和表格驱动评级比较，前者的运算负担（英语：Computational overhead）更高。

表格

编辑

表格可以看成是一种二维的控制表，其非空白的单元格中有资料，而表格的程序即为解释器。有公式的格子一般前面会前置一个等号，表示这是特殊形态的输入，在处理中可能还会用到其他单元格的资料。表格和上述的“以规则为基础的评价”有很相近的地方，就是控制表的外化，即使是非程序设计者也能进行维护。

编程范型

编辑

和控制表最接近的编程范型是自动机编程或是反射的元编程。不过控制表的解释器及各副程序可以用任何一种或多种编程范型来开发。表格本身可以只是原始资料的集合，不需要编译，在使用时再从外部设备中读取即可，不过表格放在存储器中的效率会比较高。

和比特码/虚拟机指令集的对照

编辑

多维的控制表在概念上类似在虚拟机上运作的字节码，虚拟机是一个跨平台的“解释器”软件，要执行一,一些对应的程序，而要执行的内容是依表格内容所决定。控制表的概念也有些类似通用中间语言，其目的都在创建一个共享的跨平台的“指令集”。

监控控制表的执行情形

编辑

解释器也可以存储各阶段的程序计数器内容或是其他资料，来记录部分或完整程序的流桯，记录的目的可以为了调试的需要、热点（英语：Hot spot (computer science)）侦测、代码覆盖的分析及性能分析，像上述CT3的例子就可以计数各个动作执行过的次数。

优点

编辑
  • 清楚：以二维表格表示的控制表可以清楚的表示资料及其对应的动作，容易被一般社会大众了解，像一般产品说明书中的故障处理也是以类似控制表的方式表示。
  • 可携性：可以设计成和编程语言及平台无关的形式。
  • 弹性：可以配合问题所需，某些条件下执行程序指令，某些条件下执行副程序。
  • 精简：二维表格表示的控制表直接将条件和动作的组合列出，不需利用编程语言的其他语法，因此
    • 其二进制文件的长度变小。
    • 其源代码的大小也变小，因为少了许多重复的判断指令。
    • 提升程序下载的速度。
  • 维护性：控制表减少了需维护及比对的代码。
  • 访问局部性：精简的控制表结构可以使整个表格留在缓冲存储器中。
  • 代码复用：“编译器”可以复用，而且新的计划可以应用相同的技术，逐渐可以建立由已测试过的函数组成的标准库，再由表格的定义及内容决定要执行哪些程序。
  • 算法效率（英语：algorithmic efficiency）：可以进行系统面的优化，任何对于“编译器”的优化都会带来所有使用“编译器”应用程序的效率提升。
  • 可扩展性：只要增加控制表的内容即可增加新的指令。

缺点

编辑
  • 需要训练：程序设计一般不熟悉利用控制表的方式处理程序。
  • 运算负担（英语：Computational overhead）会提高，原因是因为读取控制表时会根据相当资料去找对应的动作。
  • 复杂的表达式不一定可以放在控制表中直接比较，但有时可以事先计算表达式的值放在一变量中，在控制表中直接比较变量即可。
  • 控制表只有资料及其对应的动作，若没有注解说明时，不易看出资料及其动作的因果关系。

相关条目

编辑

参考资料

编辑
  1. ^ Programs from decision tables, Humby, E., 2007,Macdonald, 1973 ... Biggerstaff, Ted J. Englewood Cliffs, NJ : Prentice-Hall ISBN 0-444-19569-6
  2. ^ 存档副本 (PDF). [2012-09-17]. （原始内容 (PDF)存档于2012-08-08）. 
  3. ^ Donald Knuth. Structured Programming with go to Statements (PDF). Computing Surveys. Nov 1974, 6 (4): pp 261–301 [11 Oct 2012]. （原始内容 (PDF)存档于2012-05-23） （英语）. 
  4. ^ Carl Wright, Service Level Corpo. (2002) Program Code Based vs. Table-driven vs. Rule-Based Rating （页面存档备份，存于互联网档案馆）, Rating Matters issue n. 12, 13 November 2002 ISSN: 1532-1886
  5. ^ Brian E. Clauser, Melissa J. Margolis, Stephen G. Clyman, Linette P. Ross (1997) Development of Automated Scoring Algorithms for Complex Performance Assessments: A Comparison of Two Approaches Journal of Educational Measurement, Vol. 34, No. 2 (Summer, 1997), pp. 141-161

外部链接

编辑
检索自“https://zh.wikipedia.org/w/index.php?title=控制表&oldid=76574348”