65.9K
CodeProject 正在变化。 阅读更多。
Home

表格驱动的方法

Peter Kankowski
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.67/5 (21投票s)

2009年9月29日

Zlib

5分钟阅读

viewsIcon

78081

如何通过使用数组使代码更短、 更易于维护

引言

通过将代码的不同部分放入数组，通常可以避免重复代码。

// A text adventure game
if(strcmpi(command, "north") == 0) {
    if(cur_location->north)
        GoToLocation(cur_location->north);
    else
        Print("Cannot go there");
}
else if(strcmpi(command, "east") == 0) {
    if(cur_location->east)
        GoToLocation(cur_location->east);
    else
        Print("Cannot go there");
}
else if(strcmpi(command, "south") == 0) {
    if(cur_location->south)
        GoToLocation(cur_location->south);
    else
        Print("Cannot go there");
}
else if(strcmpi(command, "west") == 0) {
    if(cur_location->west)
        GoToLocation(cur_location->west);
    else
        Print("Cannot go there");
}

更短的等效实现

enum SIDE {SIDE_NORTH = 0, SIDE_EAST, SIDE_SOUTH, SIDE_WEST};
struct COMMAND {
   const char * name;
   SIDE side;
};
static const COMMAND commands[] = {
   {"north", SIDE_NORTH},
   {"east", SIDE_EAST},
   {"south", SIDE_SOUTH},
   {"west", SIDE_WEST},
};
for(int i = 0; i < NUM_OF(commands); i++)
    if(strcmpi(commands[i].name, command) == 0) {
        SIDE d = commands[i].side;
        if(cur_location->sides[d])
            GoToLocation(cur_location->sides[d]);
        else
            Print("Cannot go there");
    }

第二个版本不仅更短，而且更抽象，因此更易于维护。要实现短命令名称，只需在一处修改代码。如果需要添加更多命令，可以轻松地将数组替换为哈希表。

这类数组在许多程序中都不可或缺：从编译器和反汇编器到税务计算器和 Web 应用程序。本文将重点介绍一些使用示例。

价格计算

在 《重构》 一书中，Martin Fowler 讨论了以下代码：

// calculating the price for renting a movie
double result = 0;
switch(movieType) {
   case Movie.REGULAR:
     result += 2;
     if(daysRented > 2)
        result += (daysRented - 2) * 1.5;
     break;
 
   case Movie.NEW_RELEASE:
     result += daysRented * 3;
     break;
 
   case Movie.CHILDRENS:
     result += 1.5;
     if(daysRented > 3)
        result += (daysRented - 3) * 1.5;
     break;
}

为了改进它，他 用继承替换了 switch 语句（一个类用于计算常规价格，一个用于新发行，另一个用于儿童电影）。

一个更简单的解决方案是使用数组。

enum MovieType {Regular = 0, NewRelease = 1, Childrens = 2};
 
                             // Regular   NewRelease   Childrens
const double initialCharge[] = {2,             0,        1.5};
const double initialDays[] =   {2,             0,          3};
const double multiplier[] =    {1.5,           3,        1.5};
 
double price = initialCharge[movie_type];
if(daysRented > initialDays[movie_type])
    price += (daysRented - initialDays[movie_type]) * multiplier[movie_type];

显然，这三种情况都使用了相同的公式，因此您不必为它们创建复杂的类层次结构。基于表格的代码速度更快，代码量大大减少，并且更易于维护。

通常，当您只从一种范式（在本例中为 OOP）思考时，您会错过更好的解决方案。通过学习更多不同的方法（包括表格驱动方法），您可以扩展您的思维工具箱，并用更少的代码行解决更多的编程问题。

运费和累进税

表格有用的另一种情况是 简单 或 分段线性 函数。

设想您正在开发一个 Web 商店脚本。显示给用户的总价应包含运费，运费取决于商品的重量和配送距离。例如，俄罗斯邮政 的费率如下：

Distance 每 0.5 公斤的价格
小于 601 公里 27.60 卢布
601..2000 公里 35.00 卢布
2001..5000 公里 39.60 卢布
5001..8000 公里 46.35 卢布
超过 8000 公里 50.75 卢布

距离和价格之间的依赖关系无法用公式表示，因此程序必须在数组中查找以找到适用的费率。

def shipping_fee(weight, distance, value):
# weight in grams, distance in kilometers, declared value in rubles
    rates = [
        # max distance, price
        ( 600, 27.60),
        (2000, 35.00),
        (5000, 39.60),
        (8000, 46.35)
    ]
    # Find the applicable rate for this distance
    for r in rates:
        if distance <= r[0]:
            rate = r[1]
            break
    else:
        rate = 50.75
    
    # For each 500 grams of the parcel
    fee = rate * math.ceil(weight / 500)
    
    # For each ruble of the declared value
    fee += 0.03 * math.ceil(value)
    
    # Apply VAT (18%)
    return round(fee * 1.18, 2)

数组通常很小，因此线性扫描的速度比二分搜索快。

例如，从莫斯科寄送 《编程实践》 到哈巴罗夫斯克（0.3 公斤，超过 8000 公里，214 卢布）应花费 67.46 卢布（约合 2.20 美元）。

累进税计算 是一个类似的，但稍复杂一些的例子。

def get_tax(income):
    if income < 0:
        return income
    MAX_INCOME = 0; RATE = 1 # array indexes
    tax_brackets = [
        (  8350,  0.10),
        ( 33950,  0.15),
        ( 82250,  0.25),
        (171550,  0.28),
        (372950,  0.33)
    ]
    tax = 0
    prev_bracket = 0
    for bracket in tax_brackets:
        tax += ( min(bracket[MAX_INCOME], income) - prev_bracket ) * bracket[RATE]
        if income <= bracket[0]:
            break
        prev_bracket = bracket[MAX_INCOME]
    else:
        tax += (income - prev_bracket) * 0.35
    return tax

免责声明：这些函数仅用于说明表格驱动技术；作者不声称它们能正确计算俄罗斯的运费和美国 美国的所得税。对于后者，请使用 IRS 网站 上的计算器，该计算器考虑了各种扣除项。

汇编器、反汇编器和代码生成器

编写汇编器或反汇编器是表格驱动设计的良好练习。通常，您需要为单字节和双字节指令的数组。每条指令的助记符和操作数类型都存储在这些数组中。Gary Shute 提供了一个 使用此技术的 RISC 汇编器的小示例。

x86 代码由于其不规则和复杂的结构而更难汇编。最好的汇编器/反汇编器使用附加表来处理操作码扩展（例如，参见 Ms-Rem 的 CADT）。Jan Nikitenko 的 表驱动汇编器 表明，可以编写一个通用的汇编器，它可以重新定位到任何 ISA。

字符属性

C 语言的 ctype.h 头文件包含字符分类宏（isdigit、isupper、isalnum 等）。它们的基于比较的实现笨拙且效率低下。

int isalnum(int ch) {
    return 'a' <= ch && ch <= 'z' ||
           'A' <= ch && ch <= 'Z' ||
           '0' <= ch && ch <= '9';
}

如果有多个字符属性，您可以为每个属性分配一个位，然后制作一个包含 256 个元素的数组，存储每个字符的属性。大多数 C 运行时库都使用此方法处理 ctype.h 宏。

static const unsigned char properties[] = {
      0,  0,  0,  0,  0,  0,  0,  0,  0, 16, 16, 16, 16, 16,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     16,160,160,160,160,160,160,160,160,160,160,160,160,160,160,160,
    204,204,204,204,204,204,204,204,204,204,160,160,160,160,160,160,
    160,202,202,202,202,202,202,138,138,138,138,138,138,138,138,138,
    138,138,138,138,138,138,138,138,138,138,138,160,160,160,160,160,
    160,201,201,201,201,201,201,137,137,137,137,137,137,137,137,137,
    137,137,137,137,137,137,137,137,137,137,137,160,160,160,160,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
};
#define islower(ch)  (properties[ch] & 0x01)
#define isupper(ch)  (properties[ch] & 0x02)
#define isdigit(ch)  (properties[ch] & 0x04)
#define isalnum(ch)  (properties[ch] & 0x08)
#define isspace(ch)  (properties[ch] & 0x10)
#define ispunct(ch)  (properties[ch] & 0x20)
#define isxdigit(ch) (properties[ch] & 0x40)
#define isgraph(ch)  (properties[ch] & 0x80)

如果您只需要存储一个属性，可以使用位数组，它更小（256 位 = 32 字节），但检索值需要额外的操作。

inline int isalnum(int ch) {
    static const unsigned int alnum[] = {
        0x0, 0x3ff0000, 0x7fffffe, 0x7fffffe, 0x0, 0x0, 0x0, 0x0,
    };
    return (alnum[ch >> 5]) & (1 << (ch & 31));
}

alnum 数组在对应于字母数字字符的位置具有 1，在其他位置具有 0。

匹配字符的范围通常是有限的。如果您有一个小于或等于 32 个字符的范围，您可以将位存储在整数常量中。

// True for a, e, i, o, u, and y
inline int isvowel(int ch) {
    int x = ch - 'a';
    return (0x1104111 >> x) & ((x & 0xffffffe0) == 0);
}

当 x 为负数或大于 31 时，C 语言中移位 x 的结果是未定义的。x86 处理器使用 x 的低 5 位；其他一些处理器总是为大的移位数返回 0。为了可移植性，我们必须进行额外的检查：(x & 0xffffffe0) == 0。MSVC++ 和 MinGW 都为此条件生成无分支的 x86 代码（使用 SBB 或 SETE 指令）。这种方法不如表格驱动方法快，但代码更小。

这些方法的数组可以 通过脚本 生成。对于 Unicode 字符属性，请使用 多级表。如果字符范围是连续的，比较 应该比表查找更有效。

决策表

一个复杂的条件通常可以用一个简短的 决策表 来替代。例如。一个程序计算二元组的数量，以确定文档的编码和语言（例如，Windows Latin-1、德语）。所有字符分为 3 类：

  • 语言的字母（例如，德语的 a 到 z, ä, ö, ü, 和 ß）
  • 语言中不使用的字母（例如，德语的 è 或 ô）；
  • 分隔符（空格、句号、逗号等）

如果找到两个相邻的分隔符，则应忽略它们，因为有人可能会使用空格进行缩进。非使用字符不应出现在字母附近，因此此二元组的预期频率为零（例如，如果我们发现 êt 二元组，则文本很可能用法语而不是德语书写）。由未使用字符组成的单词应被忽略：这将提高多语言文本（例如，阿拉伯语文本中提到的英语商标）的统计数据。

如果语句序列处理这些规则将很长且难以阅读（尝试写一下！）。最好用 决策表 来表示此类条件。下面是一段构建 expected_frequencies 矩阵的代码片段。

enum LETTER_CLASS { ST_NONUSED = 0, ST_LETTER, ST_SEPARATOR };
enum DECISION { DT_SETDONTCARE, DT_SETZERO, DT_LEAVEASIS };
const DECISION decision_table[3][3] = {
      // Non-used        Letter        Separator
    {DT_SETDONTCARE, DT_SETZERO,   DT_SETDONTCARE},  // Non-used
    {DT_SETZERO,     DT_LEAVEASIS, DT_LEAVEASIS},    // Letter
    {DT_SETDONTCARE, DT_LEAVEASIS, DT_SETDONTCARE}}; // Separator

// Read a sample text and fill the expected_frequencies matrix with digraph frequencies
...

// Correct the expected_frequency value depending on the letter class
switch (decision_table[letter_class1][letter_class2]) {
    case DT_SETDONTCARE:
        expected_frequencies[letter1][letter2] = DONTCARE;
        break;

    case DT_SETZERO:
        if (expected_frequencies[letter1][letter2] != 0)
            OutputMessage("Illegal letter combination %c%c\n",
                letter1, letter2);
        expected_frequencies[letter1][letter2] = 0;
        break;

    case DT_LEAVEASIS:
        // No action, use previously calculated expected_frequencies value
        break;
}

延伸阅读

书籍

  • 《代码大全》 by Steve McConnell，第 18 章（表格驱动方法）。涵盖了按索引访问和数组中的线性搜索。McConnell 还批评了面向对象编程的机械应用。
  • 《编程珠玑》 by Jon Bentley，第 3.1、3.3 章（调查程序，示例数组）。本章展示了如何通过使用数组使统计程序更短，并提供了表格驱动方法可能有效的更多示例。

网页

  • Eric Lippert 的《脚本语言中的表格驱动编程》（The Fabulous Adventures In Coding 博客）
  • Gary Shute 的《表格驱动设计》

历史

  • 2009 年 9 月 29 日：初始发布
© . All rights reserved.