Skip to content

Tag Archives: Code Complete

《Code Complete》笔记(二)

第5章 在OI这种极限运动中,与Design这东西有关的主要还是Algorithm Design,至于实现方面的Design由于代码量真的很小应该并不需要做,只需要按照惯常的风格和习惯去做就行了。所以说专业编程中的设计工作很险恶,但OI基本上还是在一个温室的环境里进行的。 设计的过程了无章法,就像在最终得出优美的正确算法之前会有很多稀奇古怪的东西出现。但“设计”就是为了犯错——让可能会在实现过程中出现的错误尽早地出现和被解决。这是一个启发式的过程。 软件的首要技术使命是管理复杂度(managing complexity),这一点应该会让所有OIers颔首。但也许你首要想到的是时间/空间复杂度之类的东西。不过最先需要解决的问题是思维复杂度,它决定经你手写出程序的正确性。正确性,还有完整性(不能只写了一半),是比时空复杂度更先需要解决的问题。既然大脑不能把一个程序全部装进去,那么就需要把程序模块化,保证每个子程序的短小精悍和整体把握。设计的目标是易于理解,而不是smart。设计范畴内的每个特征都值得注意。 设计是分层次的,在某些OI程序里我们做到这一点可以减轻思维复杂度(尽管大多数不需要分层次的思维方式)。我们分出的模块(子系统)可能是:构图模块、网络流模块、二分答案模块,其中模块之间只有一条链型的依赖(也有可能是树形的,但一般还不会复杂到DAG)。在OI程序中使用类的情况不多,事实上我现在认为应该试图尽量减少,只有在不得不这样的情况下才去声明一个类(例如程序中用到了两个平衡树);上面所说的类不包括没有成员函数的结构体。 设计有一些启发式方法。在OI中要抽象,必须要从题目的背景中跳脱出来。封装(一般指封装到函数)也是不错的注意,它让你看不到不必要的复杂度。信息隐藏、变化、松散耦合、设计模式等概念虽然异常重要,与OI关系却不大。其它的启发式方法中对OI可能有帮助的有:为测试而设计、考虑使用蛮力突破、画一个图、保持设计的模块化。109页改变自Polya的总结有点意思。至于剩下的过于具体(或者说高级?)的设计方法在OI中更是没有必要了。 最后提及的相关书目中的某些是将来(可能是较久的将来)一定要看的。 第6章 “在计算时代的早期,程序员基于语句思考编程问题。到了20世纪七八十年代,程序员开始基于子程序去思考编程。进入21世纪,程序员以类为基础思考编程问题。” 理解类首先要理解ADT,事实上在OI中用到的类一般都仅仅是ADT而已。 类的接口的设计是一门有意思的学问,但OIers暂时不需要研究这个。 包含是has a,继承是is a,老生常谈了。不过说实话在OI程序中这两种最常见的对象间的关系我好像都没用过。 在软件工程中创建类的原因很充分,但我现在倾向于认为在OI中可以尽量避免创建它,因为写起来麻烦一些,而且可能会给代码增加不必要的复杂度。比较充分的一个原因是在代码中会被复用(比如说需要用两个平衡树),还有就是建模。

《Code Complete》笔记(一)

第1章 构建(Construction)的确是软件工程中最主要的环节。特别的,在我们的信息学竞赛这一规模很小的“工程”中,Design和Testing可探讨的空间不大不大。Design过程中出错几乎无药可救,Testing一般不会出什么错;或者说,OI中的Design和Testing不属于“工程”的范畴,可称作工程的只有Construction,也就是Programming。 第2章 在隐喻的层面,软件业界中已经广泛地认识到了增量开发的重要性,而信息学竞赛的语境中还使用着一套相当落后的隐喻(写信?),甚至有很多人从来没用过什么软件工程意义上的隐喻。应该把写程序看成一个“培育”的过程,一点一点做,最终长出珍珠;建造/修饰的隐喻体系也不错。这两个隐喻体系和分点测试的OI在精神层面上是暗合的。 在中国的比赛的环境中,“买得到的东西”比较少,但正因为如此,我们应该更娴熟地掌握和运用它们。比如说,我已经很长时间以来都没有写过qsort了。 规划得当的项目具有“在后期改变细节设计”的能力。我们书写的代码也应当如此。比如说,把我的网络流程序的存储方式由邻接表改成邻接矩阵(或者相反),我可以保证一切需要改变的不超过5行代码。这需要一种成熟和良好的书写模式/习惯。 总的来说,隐喻这种东西对于OI来说,在软件工程的层面的启示并不大,我们使用更多的是利用隐喻来理解算法。最简单的,其实“Queue”或者“Tree”都是隐喻。 第3章 OI中,构建前的前期准备让人困惑。似乎就是想出来算法吧。但是,你真的“想出来”算法了吗?或者说……你真的准备好了吗?在写程序之前,和写程序之后,把思路在脑海中理顺一遍似乎是个好主意。 按照正确的顺序做事情,这很重要,在上一章或上上一章也提过。先把圣诞树立起来,再对它作装饰。或者说,先写好DFS的框架,再去剪枝。(注意这也只是一个类比而已。)熟练的OIer写出的DFS框架应该是很容易嵌入剪枝代码的。 发现错误的时间要尽可能接近引入错误的时间。因为修复错误的代价是随着错误诞生的时间呈指数式增长的。我不确定这是否意味着我们应该在写完每一个函数之后先看一遍再开始写下面的东西,因为看上去太浪费时间。也许做到这一点最好的办法还是尽量的增量开发吧。 选择序列式开发法和迭代式开发法各有不同的理由,他们适用范围就不同。但我认为仅仅一个理由就可以让OI采用迭代式开发法(在这个语境下“增量式”似乎是更好的描述?):分点测试。 “需求”的概念在软件开发中性命攸关,但在OI中似乎真的没有它的位置。“架构”这种东西似乎也一样。 OI中,解决一道题有多少时间需要花费在前期准备上?似乎是因题而异的。唯一可以确定的大约有两点:如果你发现看完题后一秒钟就可以开始写代码了了,那么最好再看一遍;如果这道题的“前期准备”花了10min(或者一个更为妥帖的时间限制)屏幕上还没有一行像样的代码,那么暂时放弃。 第4章 编程语言的选择对软件项目影响巨大,这是经过严格的研究证实的,它甚至影响程序员面对问题时的思维。想必OI中也是这样,比如说你可以看到USACO月赛中从Bronze到Silver至Gold的组别中C/C++对Pascal的比率严格递增。或者说,NOI中使用C/C++的选手比例肯定会比NOIp中高。这也许是互为因果的。 编程约定是一个有用的东西。在我的程序中,它会以变量或函数处的一行注释体现。——变量的意义,表示特殊意义的值(例如-1表示还未计算),调用的先决条件,等等。它们是在实现前写的,而何时需要它们则是一个相当经验性的东西。