首页 > 代码库 > 表驱动法 -《代码大全》读书笔记

表驱动法 -《代码大全》读书笔记

表驱动法是一种编程模式,从表里面查找信息而不是使用逻辑语句(if…else…switch),当是很简单的情况时,用逻辑语句很简单,但如果逻辑很复杂,再使用逻辑语句就很麻烦了。

比如查找一年中每个月份的天数,如果用表驱动法,完全不需要写一堆if…else…语句,直接把每个月份的天数存到一个数组里就行了,取值的时候直接下标访问,最多针对二月判断一下闰年。这么算的话,平时用的的HashMap,SparseArray也可以算是表驱动

表里可以存数据,也可以存指令,或函数指针等都可以。

示例

看一个例子,计算保险的保险费率,不同年龄的人费率是不同的,当判断费率时就要写很长的if…else…来判断不同的年龄段对应的费率,如果要区分性别,那么判断语句就会增加一倍,如果再判断是否吸烟,是否已结婚,每一个条件都会使判断增加一倍。虽然可以通过给是否已结婚,是否吸烟等设置一个比例系数,这样就不用使判断加倍,但这个系数可不能保证对不同年龄段或不同性别的人是相同的,而且如果要改变,就要很麻烦地改程序。

如果用表驱动法解决这个问题,直接抛弃逻辑判断,使用一个表保存各个条件的费率,比如只考虑是性别,是否吸烟和年龄,就可以定义一个三维数组保存各个条件的费率

double[][][] rate = {
        {{1,2,3}, {1,2,3}},
        {{1,2,3}, {1,2,3}}
};

for (int gender = 0; gender < rate.length; gender++) {
    System.out.println("Gender:" + gender);
    double[][] genderRate = rate[gender];
    for (int smoke = 0; smoke < genderRate.length; smoke++) {
        System.out.println("\tSmoke:" + smoke);
        double[] ageRate = genderRate[smoke];
        System.out.print("\t\tAge:");
        for (int age = 0; age < ageRate.length; age++) {
            System.out.print(ageRate[age] + " ");
        }
        System.out.println();
    }
}
// Output
Gender:0
    Smoke:0
        Age:1.0 2.0 3.0 
    Smoke:1
        Age:1.0 2.0 3.0 
Gender:1
    Smoke:0
        Age:1.0 2.0 3.0 
    Smoke:1
        Age:1.0 2.0 3.0
当想取一种情况的费率时直接访问数组就行了,比如封装成下面的方法
private static double getRate(int gender, int smoke, int age) {
    return rate[gender][smoke][age];
}
前两个条件性别和是否吸烟还好说,条件还是相对固定的,对于年龄,不可能在数组中针对每个年龄定义一个数据,因为一般都是按年龄段分的,这种情况也可以定义一个函数,把年龄转换成一个数组中的第三维的索引。

使用表驱动法的好处是,当费率改变的时候,我们用不着依次改每个条件,直接修改这个费率表就行了,即使是新加条件,也只需要把这个费率表再加一维,修改一下根据条件获取费率的函数就行了

还有另一个好处就是,完全可以把这个数据表保存到文件中,在程序运行的时候读取这个文件,这样如果条件不变只是各个条件对应的数据变化时,直接修改这个文件就行了,甚至不用修改程序。

另一个复杂的例子是打印文件中存储的信息

一个文件中存储了很多信息,这些信息可以分为几十种,每个信息通过首部的一个信息ID分区

如果用传统的逻辑方法,步骤大概是:

  1. 读取每条消息的ID
  2. 然后大量的if…else…或switch判断消息类型
  3. 针对每种消息调用相应的处理函数

即使是面向对象的方法,也会为每种消息定义一个类,这样每添加一种消息都需要添加一个条件条件判断或添加一个类。

那么用表驱动法怎么解决呢?

每条消息都由一些字段组成,这些字段是有限的,比如数字,字符串,布尔类型,日期等。我们可以用另外一个文件记录每个消息对应的字段,如下所示

“Message Description” 
Field1 Float “Prompt” 
Field2 Date “Created Date”

每一种消息都通过上面的方式描述,所有消息类型被组织成一张表,这样读取消息的步骤就变为了:

  • 读取消息ID
  • 找到消息ID定义的消息描述
  • 读取描述中的每一个字段,根据字段的类型调用相应的打印方法

这样就只需要为每个字段类型定义一个打印方法,所有的消息打印方法都是一样的,除非增加字段的种类,否则即使添加消息类型也不需要修改代码

表数据的访问

表数据的访问方法我不打算按《代码大全》中的分类方法划分为:直接访问、索引访问与阶梯访问,这些只是针对特定的表的较优的访问方法,像费率计算中的年龄条件,由于年龄是分段的,但也只需要进行一个转换,可以说是直接访问,根据年龄的区间可以把年龄分为不同的段,也可以说是阶段访问。(可以把各段的端点也保存到文件中增加灵活性)

像前面的计算每月的天数的问题,直接以月份为下标就能访问需要的数据,或者像费率计算中的年龄条件,通过一个转换就可以取到需要的数据

还有的情况是不方便直接访问到数据的问的情况是,比如你有100个商品,编号为0-9999,这些编号是无规律的,你无法根据商品编号获取表键,如果直接用商品编号为键,那就需要建立一个10000项的表,而其中只有100项有意义,如果商品相关的数据项很大会浪费很多空间,此时可以使用索引技术,建立一个100项的表存储商品,然后建立一个10000项的索引表存储商品编号到商品表的表键的映射。这样会浪费一个索引表,但所幸是索引表的表项一般很小,问题不大。

即使应用索引没有节约空间而是浪费了空间,应用索引也可能会节约时间,比如查询数据库。

当然,上面的例子只是为了说明情况,如果数据不是存储在文件中而是在内存中,HashMap就行了,不过如果数据结构很复杂,计算HashCode也需要时间,当然可以优化HashCode的计算,如进行缓存等。还有稀疏矩阵等方法。

实际应用

表驱动法有没有实际的应用?平时我们肯定或多或少想到了这个方法,只是就像设计模式一样,大多数时候的思考只停留在当下的问题中,而没有形成一个思想。当看到这个方法时我第一个想到的是Android启动init时的init.rc。

以下是init.rc中zygote相关配置项:

service zygote /system/bin/app_process -Xzygote/system/bin --zygote --start-system-server
    class main
    socket zygote stream 660 root system
    onrestart write /sys/android_power/request_state wake
    onrestart write /sys/power/state on
    onrestart restart media
    onrestart restart netd

像这段代码中的writerestart关键字,我们很容易看出这是一些指令,但是系统是怎么将这些关键字对应到相应的指令上的?这就要看一个有意思的文件:keywords.h

#ifndef KEYWORD
int do_chroot(int nargs, char **args);
int do_chdir(int nargs, char **args);
...
int do_restart(int nargs, char **args);
...
int do_write(int nargs, char **args);
int do_copy(int nargs, char **args);
...
int do_wait(int nargs, char **args);
#define __MAKE_KEYWORD_ENUM__
#define KEYWORD(symbol, flags, nargs, func) K_##symbol,
enum {
    K_UNKNOWN,
#endif
    KEYWORD(capability,  OPTION,  0, 0)
    KEYWORD(chdir,       COMMAND, 1, do_chdir)
    ...
    KEYWORD(restart,     COMMAND, 1, do_restart)
    ...
    KEYWORD(write,       COMMAND, 2, do_write)
    KEYWORD(copy,        COMMAND, 2, do_copy)
    ...
    KEYWORD(ioprio,      OPTION,  0, 0)
#ifdef __MAKE_KEYWORD_ENUM__
    KEYWORD_COUNT,
};
#undef __MAKE_KEYWORD_ENUM__
#undef KEYWORD
#endif

使用keywords.h的地方在init_parser.c

#include "keywords.h"

#define KEYWORD(symbol, flags, nargs, func) \
    [ K_##symbol ] = { #symbol, func, nargs + 1, flags, },

static struct {
    const char *name;
    int (*func)(int nargs, char **args);
    unsigned char nargs;
    unsigned char flags;
} keyword_info[KEYWORD_COUNT] = {
    [ K_UNKNOWN ] = { "unknown", 0, 0, 0 },
#include "keywords.h"
};
#undef KEYWORD
在init_parser.c中include了两次keywords.h

第一次时还没有#defile KEYWORD,所以会定义do_restartdo_write等函数,并且在内部字义KEYWORD

#define KEYWORD(symbol, flags, nargs, func) K_##symbol,
这样就会走这一句
enum {
    K_UNKNOWN,
一连串的KEYWORD定义会被这样转换
KEYWORD(restart,     COMMAND, 1, do_restart) -> K_restart,
最终的结果就是定义了一个enum:
enum {
    K_UNKNOWN,
    ...
    K_restart,
    ...
    K_write,
    ...
    KEYWORD_COUNT,
}
在第一次#include "keywords.h"后,init_parser.c中DEFINE了KEYWORD,并声明了一个结构数组
#define KEYWORD(symbol, flags, nargs, func) \
    [ K_##symbol ] = { #symbol, func, nargs + 1, flags, },

static struct {
    const char *name;
    int (*func)(int nargs, char **args);
    unsigned char nargs;
    unsigned char flags;
} keyword_info[KEYWORD_COUNT] = {
    [ K_UNKNOWN ] = { "unknown", 0, 0, 0 },
#include "keywords.h"
};
#undef KEYWORD
由于此处定义了KEYWORD,所以再次#include "keywords.h"#ifndef KEYWORD内的语句就不会走,这一串KEYWORD宏被被这样转化:
KEYWORD(restart,     COMMAND, 1, do_restart) -> [ K_restart ] = { "restart", do_restart, 2, COMMAND },
其中COMMAND会也会被转化,只是上面没写
#define SECTION 0x01
#define COMMAND 0x02
#define OPTION  0x04

这样第二次include之后,就声明了一个结构数组keyword_info,结构的成员分别是操作名、操作对应的处理函数、参数个数、操作类型。

通过对keywords.h的两次include,init进程成功定义了一个枚举和一张表,并且以枚举为键查找表可以找到相应的处理函数,这样就不用每次获得操作类型后查收处理函数了,直接读表就行了,这就是前面说的,表中不只可以存数据,还可以存指令、函数指针等。虽然从init.rc的命令名找到对应的枚举名也需要查找,但从枚举名到处理函数的查找方便多了。