第23章

调试本身并不是改进代码质量的方法，可以认为它只是一种补救措施、不得已的手段。在OI中应该尽量避免调试，应该在一开始避免错误的发生。调试的效率在人与人之间有巨大差距，所以培养调试能力十分有必要。

寻找缺陷和理解缺陷是调试中最费时的步骤。事实上在这点上不应该吝惜时间，一定要确保已经完全理解缺陷后再开始动手修改。

把需要尝试的事情在纸上逐条列出，这也许是一个加速调试得好途径，因为调试时的人大多都昏头昏脑的，最好有一个能让你保持清醒的东西。

优先检查最近修改过的代码。尽量对程序保持全局理解。永远不要随机地、尝试地修改代码，每一处代码改动都需要有明确的理由。一次只做一个改动。

心理因素让人看到他“希望”看到的东西，这对调试的影响有点大，所以要保持优秀且一致的编程习惯，要让变量名之间的“心理距离”尽量远。

把编译器警告级别设为最高，这是默认的。Profiler也可以当作调试工具，有时从不正常的运行时间或调用次数中可以看出错误。

第24章

一帆风顺的软件项目是神话，实际中的代码是经常需要经受剧烈变化的。好在实际中引起变化的（最？）重要原因——需求的变化——在我们的OI中不会出现，只要你别读错题了。

软件演化的基本准则是，演化应当提升程序的内在质量。

重构的定义是“在不改变软件外部行为的前提下，对其内部结构进行改变，使之更容易理解并便于修改”。需要重构的理由在OI中同样充分的有：代码重复，冗长的子程序，嵌套过深，过长的参数列表，命名不当。

特定的重构方法很多，也很系统，但在OI中还是应该尽量在一开始就写出更好的代码，毕竟你没有太多时间。

如果确定要对代码——特别是正确（指不可能WA）的代码——进行某种大幅度的修改（不一定是重构），一定先备份一下。

第25章

性能调整在OI中也许没有你一开始想象得那么重要，似乎复杂度才更王道。任何情况下“性能”都不是头等大事，正确性才是。

程序需求方面，就是可能不切实际的复杂度分析，少数时候实际运行时间无法用理论复杂度衡量。程序的设计就是基本的算法了，如果这里面出了致命问题，再多的代码调整也无济于事。最后的手段才是代码调整。

代码调整的问题在于，高效的代码并不一定就是“更好”的代码。80/20法则是一定要注意的，Profile一下嘛……“随时随地”的优化是绝对不可取的。

常见操作的相对效率那个表真是好东西。它说我们整数的赋值、整数的加减乘、浮点数的加减乘、调用一个函数、用下标访问数组等操作所需的时间都相差无几！这还真是惊人的结论……（有空还是自己验证一下。）

优化前，一定要保存代码的可运行版本。

第26章

OI中可以考虑的代码调整技术：用查询表替代复杂表达式（没用过呢还）、使用惰性求值（常用的思想）；展开（这个很有点意思）、哨兵值（这个我比较喜欢）、把最忙的循环放在最里层（可能被忽视的常识）、削减强度（值得注意）；尽量减少数组引用、使用缓存机制（事实上很高级的东西，值得简单地尝试）；利用代数恒等式（如果真的有而你没发现的话……）、削弱运算强度（常用的）、使用正确的常量类型（以前没有注意过，也许真的很重要）、删除公共子表达式（为了程序清晰也应该做）；把子程序写成内联（“现代”计算机说这样做不一定就会性能提升）。

第19章

在表明bool值的时候，应该采用true和false而非1或0。如果从“理论”的方面论述这一点，可以说1和0是“神秘数”而true和false就不是。

比较长的判断语句中的bool表达式是一个容易出错的地方。在bool表达式方面降低复杂度的方法有：把它提炼到一个函数里然后忘掉它、试图用DeMorgan律简化它、用括号使它更清晰。

要理解很多语言中对于&&和||运算都有“短路求值”的处理，如果想避免它可以使用&和|。

按照数轴的顺序编写数值表达式，也就是说写MIN<i&&i<MAX而非i>MIN&&i<MAX。

在写复合语句时先写好开头和末尾的大括号，再填充内容。一种良好的习惯是将if、for后面跟的一条语句也放到一个单独的块里。

在程序中要避免三四层以上的深层嵌套，因为他们带来可能不必要的思维复杂度。可以考虑的解决方法有：重复判断一部分条件（违反DRY原则，故似乎不大可取）；重构某些代码到子程序中（这个比较好）；使用break语句的小trick；试图转化为一组if-else-if语句。

结构化编程就是仅仅是用顺序、选择、迭代三种控制结构的编程方法学。控制流是复杂度来源的很大一个方面。度量（思维）复杂度有一种简单的方法，但在OI中大多时候是没必要这样度量的。

第20章

软件质量的特性中有很多是与OI无关的，外在特征中也就正确性和效率需要注意，内在特征几乎都不用过多考虑。软件工程学之所以存在，很大程度上就是因为这些特征是互相矛盾的。

有时靠阅读和检查代码发现错误会比测试高效得多，极限编程(XP)的结对编程和代码检查是降低出错率的重要手段。在OI中不妨借鉴这一点，当发现错误时，先不忙着调试，先把代码看一遍。但是这样做的前提似乎是代码风格应该足够优秀，能被轻松地理解，甚至能被速读。

第21章

协同构建这部分内容，或许ACM/ICPC选手可以从中得到启迪，但对于目前的OI还是一点用途都没有。

第22章

测试在OI中最主要的体现是自己编些数据来测试正确性，这比较接近于集成测试。但与单元测试的思想类似的方法似乎也是应该应用的，也就是在编写完一个感觉上很易错的模块时应该马上独立地测试它。

第14章

直线型代码有两种，一种是语句之间有（可能是极隐蔽的）前后依赖关系，另一种是顺序无关的语句。

对于依赖关系的语句，应该设法让这种依赖关系表现得极为明显，比如说第二个函数调用的参数是第一个函数调用的返回值，或者说它们有共同的（按引用传递的）参数。当然，也可以用数据来表明没有依赖关系的语句。

至于顺序无关的语句，也应该尽量让相关（操作于同一对象）的语句放在一起。也就是说，应该让越靠近的语句关系越大。

第15章

if语句的一种常见用途就是区分正常情况与异常情况。应该把正常情况放到if前面然后异常情况用else处理，这是一种好的习惯。但我认为如果所有的代码逻辑都是异常情况用if，似乎也不会带来太大困扰。特别是在遇到异常情况就会return的情况，先处理了所有异常情况，然后在“净室”的环境下写正常情况的代码，减少了缩进层次，似乎也会更清晰。这是我的编程习惯。

if-then-else语句串的排列一般采用常见的情况在前的方式来处理，这样可以（很不明显的）提高效率。case语句是类似的。提倡尽量在每一case语句后都break，否则很容易令人困惑。

第16章

循环有好多种，不过在OI中选择哪一种似乎是自明的。应该尽量避免在循环体内外重复语句，虽然有时候看上去是不可避免的。

循环的控制语句和循环的内部最好应该可以互相看作黑盒，完全分离。

循环的初始化代码应该紧紧放在循环前面。当这种代码进有一句时，把它放到for的第一个语句似乎是更好的选择。

尽管C中的for很强大，但是一般应该让循环头中的语句仅与循环控制相关。其实还是循环的控制和循环的内容分离。

使用continue可以避免一个能让整个循环体都缩进的if判断。

减少off-by-one错误的好方法是在脑海或者用纸笔模拟，对于优秀的程序员来说这不应该太费时。

我觉得在OI中采取从内而外编写循环的方法学不是个好主意。

第17章

如果能增强可读性，那么就使用return。

对于goto，我的观点是：永远不要用。事实上我坐到了这一点。

第18章

表驱动法是一个好主意，应该了解。其实OIers对于这种东西应该比一般的“程序员”熟些，大部分情况下，不就是一预处理么，呵呵。

第10章

变量，显然是程序里最多使用的东西。我认为这是在OI中改善程序清晰度最重要的一个环节。

声明应该尽量靠近变量第一次使用的位置，初始化靠近声明。尽量减少变量的作用域（存活时间），能局部就不要全局，循环变量不在循环体外部使用的话就声明在内部。能采用const的不要采用神秘数值，如果保证只出现一次的话可以例外。不要采用节省一两个字节的奇怪技巧，比如说同一个变量会先后代表两个不同的事物。确保所有声明的变量都有被使用。

并不像伪代码编程过程之类的方法学，这些软件工程技巧都是“零代价”的。所以为何不将它们引入到OI中呢？

第11章

在OI中，关于变量的命名，唯一的目的是保证你自己能够在整个过程中都能完全清晰的理解。可能的情况下让它尽量自描述可以帮助理解。更值得称道的是你自己养成的从不会搞错的根深蒂固的命名规则。“何时采用命名规则”的清单里，没有OI能对上号的。变量名字没有意义(i,j,k)不要紧，值得担心的是变量名字的字面意义和实际用途不一致。

第12章

避免使用神秘数值，说过好多遍了。事实上，一般使用const声明的原因是因为你可以方便地改动它。

整数需要关注的问题是除法和溢出。除法的规则已经了解，溢出的问题需要加强估算。（我还是记不住2 147 483 647这个神秘数……还是(~0)>>1好了。）

浮点数的加减运算也会出问题，在数量级相差巨大的数之间。等量判断的常识应该是众所周知的。

数组中，需要关心的是下标的溢出，以及嵌套循环中的“下标串话(cross-talk)”。

第13章

结构体可以明确数据的关系。例如几个看上去无关的数组其实是在表示一组元素的多个不同属性。这时若定义一个struct，并使用这个struct的数组可以使代码清晰一些，但也会加大代码长度。值得权衡。当它们可能被作为一个整体来使用时，例如交换甚至排序，那么毫无疑问应该用struct了。

指针是令人亦爱亦恨的东西。它的确很方便，能简化一些东西，但也是很多很多错误的源泉。至于指针的理解，呵呵，每一个真正的C程序员都理解的。

把指针操作限制在子程序或类里面我是同意的。不过若一个名为NextLink()的函数的唯一一行就是i=i->next的话，也太形式主义了点。

应该把指针看作更“易碎”的变量来看待。对待变量的原则——声明与初始化与首次使用尽量接近之类——应该更加严格地施加于指针之上。指针的运用还是应该尽量减少，但决不应该“惧怕”到自己用数组模拟一种指针出来，那会能使强类型变弱。当指针仅仅是为了使接受它为参数的子程序能够修改此变量的时候应该使用引用。

全局变量在OI中的地位有点微妙。由于一个OI程序本身研究的是一个很“局部”的问题。所以所有和整个问题相关的变量（比如说输入进来的数据）都可以全局。真正需要避免的是把确实“局部”的东西，例如循环中的i、j、k都弄成全局的。

第7章

（作者太厉害了，竟然举了一个例子就介绍了在书写rountine过程中可能犯的几乎全部错误。）

创建子程序的最初始目的还是为了避免重复，但是在现代编程中，这不是唯一的目的。降低复杂度，更高层次的抽象，隐藏某些信息是目的中最主要的，其它目的也都很有启发性，因为它们可以最明确无误地告诉我们何时使用子程序。

即便一个看上去过于简单没必要写成子程序的操作，只要它确实多次重复，出于更好的（是的，没有最好的）可读性的目的，还是提倡把它写成子程序。另外，短小但重复的代码带来的另一个问题是无法变化。

在子程序的层面，内聚性的意思就是一个子程序里面做的事情应该是彼此紧密相关的。功能上的内聚性是首要的，在OI中我们应该做到一个子程序只做一件事。

子程序的名字很重要，虽然在OI中似乎不用拘泥什么规则，但最好还是形成自己固定且清晰的命名习惯。当你发现你不能用简短清晰的名字说明子程序所作的事情时，这个子程序的设计大概有问题，比如说有副作用。

也许子程序的长度是一个有意思的研究领域，但是在OI中大约还没有真正“长”的子程序。我近来不喜欢在OI中为子程序而子程序的做法，也就是说任何程序都有Input、Solve、Output这样的子程序（我以前这么做）。我现在认为在OI中不重复的代码完全没必要做子程序。

对于参数表的参数顺序，首要原则我认为是重要的变量放在前面，同时参数列表相似的子程序其顺序应该一致。

函数（在C-like的语言中，特指非void函数）的返回值在某些执行路径中可能会忘记返回值，g++对此也没警告。这是我经常犯的错误……很多时候都会为此调试半天……一定要注意这个。

对于子程序的性能，不要臆测，要知道只有Profile能告诉你真正的瓶颈所在。

第8章

在OI中，一般是完全不需要“防御式编程”的。我常常采用的方法是给需要传入的数据满足一定条件的函数处加上注释，而不是在程序中采取断言之类的措施。

第9章

在写程序前写高质量的伪代码的确是个提高代码质量的好主意，但在竞赛中还是把这个过程留在脑海中吧。不过以后有空的话可以考虑把所有常用的算法自己写一份伪代码，写完以后与CLRS之类的书上的伪代码进行比较。（其实也说不定自己写的才更好哦。）

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

第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表示还未计算），调用的先决条件，等等。它们是在实现前写的，而何时需要它们则是一个相当经验性的东西。