Skip to content

提高抽象层次

(本文为《信息学竞赛中的软件工程学》系列的第二篇文章)

我认为,软件工程学的发展史就是代码的抽象层次不断提高的过程。在所有的0和1都必须人工一个一个打孔到纸带上的时代,在代码中没有任何抽象,自然也就还不存在软件工程学。而当一些聪明人发现,代码中总有一些相同或相似的部分,于是他们提出了function。function的概念被广泛接受,也就是抽象层次的初步建立,就可以说是软件工程学的萌芽。然而function可以说是从数学里现成地拿来的东西,算不上软件工程师自己的创造。软件工程学真正作为一门系统的方法学得以建立,我认为是在Object的概念被广泛应用之后。

Object的抽象层次比function要高。我们在使用function的过程中会发现,有些data和function之间的关系非常紧密。——比如说,某个数组(比如说,int heap[MAXN])只被那么两三个函数(例如void push_heap(int x)和int pop_heap())所读取。也就是说,某些data和function之间有一种“自成体系”的感觉。此时,我们就把这一组数据与函数(或者说,method,方法)抽象成一个Object(比如说,class heap)。

在面向过程的编程环境中,我们思考的是“如何做某事”。也就是说,我们的思考过程是:要想达到最终的目标A,我们必须先做B、再做C、最后做D。这时写出的程序肯定是这样的:函数A调用函数B、C、D。而在用面向对象的方式思考问题时,我们思考的是“我们需要什么”或者说“问题是什么”。我们需要一个可以进可以出且每次出来的都是最后进去的值的东西,那么我们就会写下class stack以及stack::push、stack::pop。

当然,现在软件工程业界认识到的抽象层次又提高了许多。比如说,著名的GoF (Gang of Four) 发现,在代码中,某些一群对象的“关系”是经常出现、有章可循的。那么就有了Design Patterns。还有人发现,总是可以把Web程序分成Model、Viewer、Controller三个部分,于是就有了MVC模型(或者说模式)。(注:MVC模型的应用并不限于Web程序,但据我观察它目前在Web程序中的应用比较广泛。)

上面扯远了,不好意思。我们还是看看在信息学竞赛中为什么要提高抽象层次吧。答案很简单,当你站在一个更高的层次去编程与思考,你会发现你的思路变得清晰,编程和调试的速度都会有所加快,你通过一个程序中学到的东西也会更多。

举一个简单的例子。在某些程序(动态规划尤甚)中,我们经常会看到这样的语句:

if(xxx < yyy)xxx=yyy;

其中xxx是一个变量,yyy可能是一个很长的式子。既然这种东西反复出现,我们为何不将它抽象成一个函数?

inline void update(int& old,int x){
  if(old < x)old=x;
}

这样做的一个明显好处是,yyy是一个很长的式子,但是这样一来我们在程序中只用将yyy写一遍,而不是原来的两遍。这减少了出错的可能性。(可能性更大的出错方式是你在调试过程中将yyy做了修改,但是你可能只修改了一处。)

再举一例,这是我昨天写凸包程序时,我开始把程序写成了这样(片断):

for(;;){
  if(S-S0 > 1&&zcross(P[p]-P[s[S-1]],P[s[S0]]-P[p]) < 0){
  p=s[S--];
  continue;
  }
  if(S-S0 > 1&&zcross(P[s[S0]]-P[p],P[s[S0+1]]-P[s[S0]]) < 0){
  ++S0;
  continue;
  }
  break;
}

连matrix67这样以Brainfuck为乐的大牛都抱怨看不懂我的程序……可见这代码有多晦涩。在这样的代码中,你能看出p=s[S--];这一句其实应该改成p=s[--S];吗?

从上面的代码片断中,你应该看到一个抽象:

inline bool badjob(const point& a,const point& b,const point& c){
  return zcross(b-a,c-a) < 0;
}

仅仅是在在那个几乎完全照着USACO教程敲的程序中应用了如上函数后。我发现程序的思路一时无比清晰,马上就找出了程序中的错误。

当然,以上的东西估计大牛都会不屑一顾。我只是想论证一下提高抽象层次的必要性。然而在程序中提高抽象层次的最主要方法恐怕是面向对象。这个话题将另有专文论及。

2 Comments

  1. 木瓜 wrote:

    你再抽象,我就变狮子。

    Tuesday, April 3, 2007 at 16:12 | Permalink
  2. 桔子 wrote:

    我的天。。。我晕过去三回了已经,起来后只会说这一句

    Wednesday, April 4, 2007 at 01:44 | Permalink

One Trackback/Pingback

  1. Matrix67: My Blog on Tuesday, April 3, 2007 at 16:24

    比比谁更无聊:Whitespace语言…

    &amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;我们已经见过了[url=http://www.matrix67.com/blog/article.asp?id=139]满篇æ%……

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*