Skip to content

Tag Archives: 软件工程

提高抽象层次

(本文为《信息学竞赛中的软件工程学》系列的第二篇文章) 我认为,软件工程学的发展史就是代码的抽象层次不断提高的过程。在所有的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; […]

降低耦合

(本文为《信息学竞赛中的软件工程学》系列的第一篇文章) 由于本文面向的并不是专业程序员而是信息学竞赛选手,所以我有必要从基础概念讲起。按照我对软件工程学粗浅的理解,耦合就是程序中模块与模块间的关系的总和。上面的“模块”一词是一个模糊的概念,可以是一个变量、一个函数、一个类,或者是一个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)存在的主要目的就是为了减少耦合。所以说,不要再写像涂了胶水的绳结一样的程序了,试图减少耦合,从今天开始。 (由于本人对“信息学竞赛”和“软件工程学”的认识都实在粗浅,故错讹之处在所难免,请包涵和指出。)

别忽略思考

“你上午在机房待了一上午干了些什么?” “做题。” “那下午的四个小时呢?” “当然是做题。” “晚上呢?” “做题呀……” “那你什么时间思考呢?” 以上无聊的老段子你当然可以忽略,但是思考这个问题是绝对不能忽略的。 在开始写程序前别忽略思考 你肯定跳了起来:“在开始写程序前我怎么会不思考呢!不思考哪来的算法?”不,你很可能没有思考,你的算法可能仅仅是凭“感觉”得出的。就像我今天做那道Letter Game时一样,一看那道题就觉得要写一个Trie——肯定要有频繁的字符串查号嘛……然后再对原字符串进行全排列,然后再……写了一百多行时我发现我受够了。不应该是这样的,远不应该是这样的。你只是模模糊糊有了一点算法的“感觉”就开始写程序,然而你甚至根本就没有仔细对题目本身进行思考!为什么字典里的词的长度大于3小于7?这可以给我们带来什么样的便利?是的……我想你已经知道我的意思了:要思考特殊性,而非一般性。我在写程序前由于没有从题目的“特殊性”中思考而是只看到了所谓的“一般情况”,所以走了弯路。是的,别一看到题就噼噼啪啪敲键盘,那样真的不cool。 在coding中别忽略思考 那么对算法有了清晰完整的认识后就该比拼谁的打字速度快吗?不,一定不是这样的。这时也要思考。不过这个阶段的思考过程似乎“潜意识”的成分居多,有时会突然发现算法中的纰漏等等。就不要“刻意”一边coding一边thinking了……还是快点写完程序再说吧。 在调试中别忽略思考 把程序交上去……WA/*LE。我想你预料到这种情况了不是吗?那么调试吧,调试吧……但这时先思考一下!哪一部分是你写程序的时候最感觉别扭最感觉不舒服的地方?哪一部分代码是你自己可能都没有真正理解的?好了……抓住那段代码。像我这种长于静态调试的家伙就会不厌其烦地在.log中把可疑的步骤全部输出出来…… 做完题后别忽略思考 OK……AC了,天空晴了,花儿开了,一切都结束了。可是真的是这样就万事大吉了吗?不是的。你还要思考。不刻意地去思考你很难从一道题里得到什么。写几句简短的Analysis,也许你会发现那些萦绕于心的想法变得清晰,你会发现你再次遇到那类题时会成竹在胸而不是依然不知所措。我想你已经知道为何很多神牛(如maigo就是最好的例子)都有大量的解题报告传世,也许它们是互为因果的。 (本文章仍待补充)