Disptach系列谈1:branch table

Disptach系列谈1:branch table

就disptach这一意义而言,branch table与很多技术都是相同的,包括虚函数,中断向量,symbol

table,dispatch (SICP中提到),call back, windows消息响应,MFC消息响应,CPU的指令执行循环。

如果这一篇对大家有意义,那么,我以后就继续写下去,把后面的技术挨个介绍了。不然,就仅只 branch table吧,它本身也够强力了。

1. 追求解析解之无望,然后呢?

童话的最后一句说,"从此王子与公主过上了幸福的生活",好像前面的一切铺垫啊痛苦啊斗争啊,到此结束,从现在开始就风平浪静再无矛盾,可以无忧无虑了。我们知道,指望找到万能良药或者银弹,一了百了地解决工程上的需求是不可能的。现实世界不是这样美好的,甚至存在这种幻想都有害无益。

不过另一方面,是不是可以归结为虚无主义,这世界就没有规律可循,工程中的所有需求必须每次都找个牛人解决,不然就束手无策呢?我以前问过本科的导师李老师,工程师这一辈子要一直追赶新技术,是不是就没个头,没有希望了呢。后来,我在博客里提到,答案不是那么悲观的,解析解也许并不存在,但是局部的优势偶尔还是有的。对于某些问题,我们确实可以找到足够好的方法。

比如branch table所代表的思想,就是其中的一个有效方法。

2. 从刘邦说起,任务与执行者的关系

刘邦,太祖高皇帝。得势以后有人问起他为什么这么牛,我们可以想像他洋洋自得地谦虚的神态,他说:我啥啥不如萧何,啥啥不如韩信,啥啥不如张良,那为啥单只我刘邦能统一天下呢,因为我能用人呐。

批判略过。

刘邦所做的,叫做"dispatch",中文翻译为分发。有的书中翻译为调度,我们所不取也。因为调度还有另一个英文词与之对应,就是

schedule,表示计划在以后的某个时间段去做事,而dispatch的意思大抵是现在马上就做。有牛人可能说,这不明明是delegate么。是的,比喻的故事么,你也可以强调那个方面,不过,我想讨论的方向,就只是

dispatch,delegate还是dispatch以后的事。

Dispatch的作用在于,"我"并不知道应该如何完成某项工作,但是"我"知道"谁"可以胜任这一任务。今天讨论的重点,不是完成这个任务的是"谁",而是"我"所知道的重要信息,即"我"知道任务"谁"之间的对应关系。重点就是这一关系。

任务与执行者间的关系如何记录在程序中呢?最直接的想法就是用代码来记录吧。从冯・诺伊曼体系结构以后,代码与数据分开来存储,分别另眼看待,所有的信息如果想存储起来,就要先选择它是数据,还是逻辑。

如果任务与执行者的关系用代码 (逻辑)来记录,那么应该是什么样呢?

3. switch-case

可以用switch-case,或者if-else来写,这二者无甚区别。如下:

(代码片断1)

1 switch (任务)

2 {

3 case 适合张良:

4 张良do();

5 break;

6 case 适合韩信:

7 韩信do();

8 break;

9 case 适合萧何:

10 萧何do();

11 break;

12 }

在以上代码中,第一行的意思是:根据任务的情况 (或其中的信息) 而进行选择(转发)。

以后每一行的case,代表一种情况,case后的 适合张良,是个逻辑表达式,返回结果是个逻辑上的真假,而本身是个谓词的表达式。

以上代码也是很多年轻程序员和年轻的其他人类的长久困惑,"活儿都是俺们干的,经理或者老板到底做了什么。"刘邦做了什么呢,他的责任就是分发–决定把什么样的任务派给谁。

换句话说,上面的代码"记录"了刘邦的功能。在计算机的世界里,刘邦就是用上面的代码实现的,每当来个任务,刘邦就run起来,直到把任务转交给某个人。

4. branch table

switch-case实现了记录disptach的任务和执行者的关系,不过它也有些毛病。如果刘邦可能还能把任务转给很多别的人,那么这个switch-case就要变长了。每个可转发的人,会使switch-case增加3行,只需30个人,一屏80行就容纳不下了。也就是说,看后面的某个case的时候,你看不到前面的switch。无疑地,这让你在编程时得留一个心眼想到"有case,前面肯定得有switch,而且…对了,这个是给刘邦分派任务用的"。如果你心眼多还好,如果心眼少,再多些别的需要关注的,很容易就整得缺心眼了。

工程方法之所以存在,就是为了让心眼不那么多的人,也能做心眼非常多之牛人能做的事,甚至做得更好。按萨特的观点,如果你能完成牛人做的事,那你就也是牛人。

除了switch-case可能变长,刘邦还可能在开始disptach之前和结束之后,还要做初始化和清理的工作,而那些,与任务和执行者的关系没有任何关联。软件工程追求的目标之一:高内聚低藕合。凡是无关的,我们希望它们能离得远一些。初始化和清理工作,它们与任务和执行的关系关联较小,我们因此希望它它们与这些switch-case离得远一些。

更关键的是,我们意识到这个switch-case结构是不会随意人员增加而发生变化的。人员与任务的对应关系会变,但是这个关系的存在、我们利用switch-case结构实现这个关系的对应,这些是不会改变的。不变的东西在人类历史上具有特别重要的意义,中流砥柱和海枯石烂的精神正是因此而受到赞扬的。虽然现在不流行了…另外,这些不变并非原来就存在的,而是人们创造或者发现出来的。有人问到,宇宙定律为什么适合于很多别处。那是因为我们把那些恰好也适合于很多别处的事件总结为了定律,那些变化的,都被我们抛弃了。即使大河奔流,世界变化莫测,人不能再次时踏入同一条河流,而河流的奔流这一变化本身–正是不变的。

扯远了,再拉回来。有人可能争辩,他可以这么写,就解决了上述问题:

(代码片断2)

1 switch (任务)

2 {

3 case 适合张良: 张良do(); break;

4 case 适合韩信: 韩信do(); break;

5 case 适合萧何: 萧何do(); break;

6 }

事实上,插一句,除了这种优秀写法与我们的第一种写法,还有更不符合软件工程原则的写法,把每个case都写得很长–那里不是 张良do()

这样的函数,而是 张良do()的函数体本身,长达三五十行或者更长。当然,这种方案逞一时之快(或者叫牛人的匹夫之勇?)尚可,但是长此以往,后面修改的难度可就大了。每个case都这么长,再加上如果switch是第一级缩进,等缩到张良do()的函数体,就是第三级,如果张良do()的函数体本身再有if-else或者for循环呢?

代码片断2这种写法,每增加一个case只增加一行,case的条件与执行者的对应关系一目了然。那么,我们为什么不再进一步,按下面这样写呢?

(代码片断3-1)

1 适合张良 张良do()

2 适合韩信 韩信do()

3 适合萧何 萧何do()

没错,这不是C代码,所以不行。那么像下面这样呢?

分发条件类型的数组 cond = {适合张良, 适合韩信, 适合萧何};

执行人的数组 worker = {张良do, 韩信do(), 萧何do()};

这样,我们把任务 (的适合发布条件)

与执行人的关系,从用代码记录改为了用数据记录。这有什么好处?最大的好处是,switch-case这个稳定的结构可以不变,可以在工程接下来的迭代中,不需要变化。无论是增加新的人和任务的对应关系,还是修改初始化和清理的动作,都不需要触碰switch-case这个结构。当然,这个结构已经不再是上述的样子,而变成了:

(代码片断3-2)

1 for( 每一个 current_cond)

2 {

3 if(current_cond == 任务)

// 原始代码为:switch (任务) – case (适合某条件),

// 这里的current_cond就相当于"某条件"

4 执行与cond相同下标的worker;

5 }

5. 实例

下述实例是C语言的,电分析化学设备的一部分,为方便阅读进行了剪裁。

为了定义 执行者 表方便,我们用到了函数指针,先简单复习一下。

类型定义的时候:

(代码片断4-1)

1 typedef int (*func_ptr)(float*);

这表示所有的执行者的函数都具有这样两个相同点:参数是float指针,返回值是int。它们唯一的不同,就是名字不同。函数签名一共就三点,它们有两点一样。

函数指针的实例定义的时候:

(代码片断4-2)

func_prt foobar=某个函数指针;

调用的时候:

(代码片断4-3)

int a = foobar(2.0);

以上是函数指针的复习,下面是 branch table 的一个实例。

(1) 条件 表

(代码片断5-1)

1 int method [MAX_METHOD_NUM]={CV , OCV, ITC, LSV, SWV, NPV};

CV,OCV等都是宏定义,代表一种电化学方法。对于 branch table 而言,这些电化学方法就是

适合执行某个函数的条件,也即任务–不同的任务,用不同的函数执行。

(2) 函数 表(执行者表)

(代码片断5-2)

1 typedef int (*func_ptr)(float*);

2 func_ptr func_array[MAX_METHOD_NUM]={

3 CV_Config, OCV_Config, ITC_Config, LSV_Config, SWV_Config, NPV_Config};

这里的CV_Config和OCV_Config等都是函数名。在别的地方,声明和定义着它们,像这样: int

CV_Config(float*); int

OCV_Config(float*)。它们就是适合于某个条件时要执行的函数。对应的条件和函数,它们的下标是相同的。

(3) 查找函数

(代码片断5-3)

1 func_ptr lookup(float task)

2 {

3 int i=0;

4 for(i=0;i<MAX_METHOD_NUM;i++)

5 {

6 if(method[i]==task)

7 {

8 return config_funtor[i];

9 }

10 }

11 }

其中的lookup的本意是"查找",这里的用意是查找哪员大将符合执行这个任务的条件。

(4) 执行部分

(代码片断5-4)

1 func_ptr foo = lookup(task);

2 int a = foo();

其中 lookup 以 task 为参数,返回值是查找到的适合于task的函数的指针,这

一指针赋值给foo (相同基类型的指针) 。在第2行执行这个函数foo,返回值赋值

给a。

或者,更简单的写法:

(代码片断5-5)

1 lookup(task)();

有人可能会抱怨,(代码片断5-5)这样的写法太逆天或者残忍或者诸如此类的形容词。为什么可以这么写呢,除了受到C的训练以后,你得习惯读这样的代码,另一个更重要的原因是–这一段代码,你根本就不会再去改它。事实上,除了条件表和函数表以外,在以后的迭代中,无论天翻地覆,只要不需要触及灵魂深入的switch-case这一结构,其他的部分是不需要修改也不需要阅读的。

当把继续维护的任务转交给别人时,你也只需要告诉他,

a. 我们用了 branch table,

b. 条件表和任务表分别在哪里,

c.函数原型 (即函数表中元素的类型,本例中是 int (foo*) (float*),

d. 任务的类型 (即任务表中元素的类型,本例中是 int)。

你完全不需要告诉它"这个switch-case可别改坏了","这两个case之间其实没有任何变量藕合"等等,如果担心,你可以把除任务表和函数表以外的东西都放到某个头文件里,甚至编译成静态库或动态库。这样,你给续任者的就是一个框架,而不是一堆容易冒错的规范。C++之父有云,如果你不查让别人做的,不是告诉他,而是让他无法那么做,而不是小心翼翼提心吊胆地一边替你卖命一边担心你的评价。

然后呢?我们把刘邦流放了,让随便一个什么人坐在那里,来一个任务,就到任务表里查一下,然后分派给适合的人。从此,王子和公主过上了幸福的生活。

——————–

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]

Leave a Reply