多路分支

多路分支（Multiway branch）是依照一些事先規劃的準則來變更控制流程，變更後的選擇不止兩個。多路分支是條件指令的一種。若要從多個標記選擇一個，轉移流程控制，多路分支多半是算法效率最高的方法，尤其是已事先從原始資料中決定索引值，以此決定流程控制的情形。

像分支表、switch指令、多分派都是多路分支的例子。

分支表

多路分支可以用有效率，配合索引進行的查找表進行（用資料本身當数组索引，或是用某個從資料計算出來的值當索引），這也是常見實現多路分支的作法

...switch指令的實現袲通常會等於多路分支。不過，在許多現實程式中使用的switch指令，可以避免分支指令，將switch指令改為一個或多個的查找表。例如 Has30Days範例[在前面曾展示過]可以用以下的方式實現:[C語言範例]

switch (x) {                     /* x is month no */
  case 4:                        /* April         */                             
  case 6:                        /* June          */
  case 9:                        /* September     */
  case 11:                       /* November      */
  return true;
}

可以用「安全雜湊」（safe-hashing）的技巧，取代為以下的程式

unsigned int t = x | 2;
switch (t) {
  case 6:
  case 11:
  return true;
}

也可以用索引映射的查找表，改為以下程式

x %= 12;                                            /* to ensure x is in range 0-11*/                                                 
static const int T[12] = {0,0,0,0,1,0,1,0,0,1,0,1}; /* 0-based table 'if 30 days =1,else 0'  */
return T[x];                                        /* return with boolean 1 = true, 0=false */

（考慮後者程式的簡潔，可以將程式用内联函数方式實現，因為呼叫函式的開銷，比有索引的查找表本身還大。）

引文

多路分支是重要的程式設計技巧，也是太常被沒有效率的if指令代替的技巧，彼得·諾爾最近寫信給我，他提到用表格方式來控制程式流程，是計算機科學的基本概念，幾乎已被人遺忘了，但他預期，此概念某天就會被人再度發現。這是我所研究最好的編譯器中，其效率的關鍵

——高德纳，Structured Programming with go to Statements

相關條目

• 條件 (編程)
• 查找表

外部連結

• Coding Multiway Branches Using Customized Hash functions by H. G. Dietz
• Learning Python By Mark Lutz
• Programming in C++ By Nell B. Dale, Chip Weems
• A Superoptimizer Analysis of Multiway Branch Code Generation by Roger Anthony Sayle