维基百科

控制表

控制表是一個決定控制流程或是主要影響控制流程的表。關於控制表的結構或內容沒有硬性的規定，其特點是其可以影響控制流程的能力。這類表格的設計有時稱為「表格驅動設計」[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”