跳转到内容

控制表

本页使用了标题或全文手工转换
维基百科,自由的百科全书
一个简单的控制表,依单一输入变数决定程式流程,每个表格项目包括一个可能的输入数值,及对应动作的副程式,若程式语言不支援指向副程式或函式的指标,也可以用副程式的编号代替

控制表是一个决定控制流程或是主要影响控制流程的。关于控制表的结构或内容没有硬性的规定,其特点是其可以影响控制流程的能力。这类表格的设计有时称为“表格驱动设计”[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。若要使用一维表格的控制表,数据的可能范围需要很小,像ASCIIEBCDIC字元都只有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指令来代替,而其条件可以利用逻辑运算的ANDOR指令组合出复杂的条件,条件成立时也可以执行不止一个的副程式。不过各高级语言中的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

外部链接

[编辑]