Skip to content

《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中可以尽量避免创建它,因为写起来麻烦一些,而且可能会给代码增加不必要的复杂度。比较充分的一个原因是在代码中会被复用(比如说需要用两个平衡树),还有就是建模。

Post a Comment

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