翼若垂天之云

（本文为《信息学竞赛中的软件工程学》系列的第二篇文章）
我认为，软件工程学的发展史就是代码的抽象层次不断提高的过程。在所有的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教程敲的程序中应用了如上函数后。我发现程序的思路一时无比清晰，马上就找出了程序中的错误。
当然，以上的东西估计大牛都会不屑一顾。我只是想论证一下提高抽象层次的必要性。然而在程序中提高抽象层次的最主要方法恐怕是面向对象。这个话题将另有专文论及。

Tags: 软件工程

Related posts

别忽略思考
降低耦合

（本文为《信息学竞赛中的软件工程学》系列的第一篇文章）
由于本文面向的并不是专业程序员而是信息学竞赛选手，所以我有必要从基础概念讲起。按照我对软件工程学粗浅的理解，耦合就是程序中模块与模块间的关系的总和。上面的“模块”一词是一个模糊的概念，可以是一个变量、一个函数、一个类，或者是一个package（在大型软件项目中），在信息学竞赛级别的程序中，主要指的是全局变量与函数（本文中“函数”一词包含Pascal语言中所谓“过程”）。
显然，如果这样定义耦合的话，我们编的任何程序都有它的存在，而且它显然是不可避免的——你的程序用到了一个函数，它要调用其它函数，或被其它函数所调用，或读和写某个变量——在我们粗浅的定义里，这些都是耦合了。
但耦合不仅是函数A调用函数B所以A与B之间存在耦合这么简单。事实上，这已经是比较轻的一种耦合。它带来的后果仅仅是：如果函数B改名了、被移除了、改变功能了就会影响到A的功能的实现，这种情况在我们的信息学竞赛的编程过程中并不多见，而且很有可能在编译期就被检查和改正。我想说的是更深一点的东西： 比如，函数A和函数B共同使用某个全局的变量或数组，那么它们对它就必须有某种哪怕是最显而易见的约定，否则就会出问题。（这句话的前提是你用一般认为 “正确”的方法声明和使用全局变量，如果您的编程风格是把每个函数都要用到的临时循环变量i声明成全局的……那您没必要接着看下去了，道不同不相为谋，真的。）
为何要降低耦合？很简单，我们希望我们的程序尽量清晰，而不是一团蛛网或浆糊；这样利于阅读和思考，也利于修改和优化。比如说若函数A依赖于函数B的实现中某个细微的对于全局变量的副作用，那么我们可以说A和B之间的耦合很深；这可能导致我们简单地修改了B之后发现A不能正常工作 了；这可能花费我们大量的时间来寻找原因，毕竟“由于B的副作用被消除导致A的崩溃”这种事情太晦涩了，这不是我们希望看到的。
接下来说如何降低耦合：
1.一个函数只做一件事。我看到过的一些OI程序似乎在“吝啬”地使用函数。也就是说持“能少一个函数就少一个函数”的态度。然而为了减少耦合，我们应该把庞大的、笨重的东西拆成小部件，让每一个小部件和尽量少的外部的东西耦合。另外，单个函数的行数多了会导致出错这也是广泛的共识。
2.不要过早在意细节优化。我知道，有些OI程序中有很巧妙的东西，比如说在排序的同时算前缀和之类。可是，真的需要这样做 吗？为了少写几次for或者是为了还不清楚的“效率”？效率不是想当然的东西，只有Profile能告诉你真正的效率如何瓶颈在哪里。先用最清楚的逻辑描述出程序的框架，如果真的有时间效率问题那一般来说是算法复杂度的问题，在程序编好且正确之后再考虑细节优化吧。这是耦合度增加的温床。
3.减少全局变量的数量。全局变量是耦合的多发地。在软件的开发过程中甚至有些专门对付它们的模式，例如“Singleton”。相信我，你能减少它们。在这一点上我不想说太多。
4.试图面向对象。我知道很难让人像我一样，每当要在程序中用到某种数据结构——不管是最简单的队列还是复杂些的并查集或者Suffix Tree——我都会编一个class，而且很可能是Template Class。我并不是炫耀，我只是想减少耦合，我只是想使程序更清晰些。“面向对象”这个话题会在本系列中单列一篇文章来做更详尽的分析。
我不知道你是否听说过UML、MVC等等这些在软件工程界很“时髦”的缩写词。我认为这些技术（尤其是MVC）存在的主要目的就是为了减少耦合。所以说，不要再写像涂了胶水的绳结一样的程序了，试图减少耦合，从今天开始。
（由于本人对“信息学竞赛”和“软件工程学”的认识都实在粗浅，故错讹之处在所难免，请包涵和指出。）

Tags: 软件工程

Related posts

别忽略思考
提高抽象层次

“你上午在机房待了一上午干了些什么？”
“做题。”
“那下午的四个小时呢？”
“当然是做题。”
“晚上呢？”
“做题呀……”
“那你什么时间思考呢？”
以上无聊的老段子你当然可以忽略，但是思考这个问题是绝对不能忽略的。
在开始写程序前别忽略思考
你肯定跳了起来：“在开始写程序前我怎么会不思考呢！不思考哪来的算法？”不，你很可能没有思考，你的算法可能仅仅是凭“感觉”得出的。就像我今天做那道Letter Game时一样，一看那道题就觉得要写一个Trie——肯定要有频繁的字符串查号嘛……然后再对原字符串进行全排列，然后再……写了一百多行时我发现我受够了。不应该是这样的，远不应该是这样的。你只是模模糊糊有了一点算法的“感觉”就开始写程序，然而你甚至根本就没有仔细对题目本身进行思考！为什么字典里的词的长度大于3小于7？这可以给我们带来什么样的便利？是的……我想你已经知道我的意思了：要思考特殊性，而非一般性。我在写程序前由于没有从题目的“特殊性”中思考而是只看到了所谓的“一般情况”，所以走了弯路。是的，别一看到题就噼噼啪啪敲键盘，那样真的不cool。
在coding中别忽略思考
那么对算法有了清晰完整的认识后就该比拼谁的打字速度快吗？不，一定不是这样的。这时也要思考。不过这个阶段的思考过程似乎“潜意识”的成分居多，有时会突然发现算法中的纰漏等等。就不要“刻意”一边coding一边thinking了……还是快点写完程序再说吧。

在调试中别忽略思考
把程序交上去……WA/*LE。我想你预料到这种情况了不是吗？那么调试吧，调试吧……但这时先思考一下！哪一部分是你写程序的时候最感觉别扭最感觉不舒服的地方？哪一部分代码是你自己可能都没有真正理解的？好了……抓住那段代码。像我这种长于静态调试的家伙就会不厌其烦地在.log中把可疑的步骤全部输出出来……
做完题后别忽略思考
OK……AC了，天空晴了，花儿开了，一切都结束了。可是真的是这样就万事大吉了吗？不是的。你还要思考。不刻意地去思考你很难从一道题里得到什么。写几句简短的Analysis，也许你会发现那些萦绕于心的想法变得清晰，你会发现你再次遇到那类题时会成竹在胸而不是依然不知所措。我想你已经知道为何很多神牛（如maigo就是最好的例子）都有大量的解题报告传世，也许它们是互为因果的。
（本文章仍待补充）

Tags: 软件工程

Related posts

提高抽象层次
降低耦合