序
在拙文 《高手看了,感觉惨不忍睹——关于“【ACM】杭电ACM题一直WA求高手看看代码”》中,我对ACMer们的一些代码“惯例”发表了我的看法, librazy网友在评论中给出了他的一些见解,我予以了相应的回复。
我个人认为这种讨论是极其有益的,双方取得了一些基本共识,对分歧之处,也都说明了自己的理由,以待读者自行判断。无疑,这是一次高水准的讨论。
感觉这些讨论散见于“评论”中有些可惜,故此稍作整理,以利于网友阅读。需要说明的是,整理过程中我做了一些润色和补充。如果librazy网友感到有必要,欢迎也进行必要的润色和补充。
基本共识
我和librazy网友一致认为:
竞赛有时是不择手段的;
但真正写代码时必须堂堂正正。
因为竞赛是为了“赢”对手,但代码绝对不是像卫生纸那样一次性使用的。
此外我和librazy网友都一致认为宏名应该大写,不应该无故违背C语言长期形成的这种“公序良俗”。
以下则是我和librazy网友对某些问题的“各自表述”:
关于ACM竞赛
librazy:
算法竞赛中,更注重的是代码质量和效率的平衡。
garbageMan:
不能用牺牲代码质量来换取效率,
这是得不偿失的短视行为。
效率应该通过精心设计的算法获得,
而不是通过别的手段,
尤其是不能牺牲代码质量。
关于在源文件头部写无用的#include预处理命令
librazy:
一般上ACM开头无论用不用的到,常用的库是一定要引用全的。
garbageMan:
我知道这样写是为了万一遗忘,是有鱼无鱼先撒一网再说的意思,是对自己忙碌的代码没有自信的表示,但这与C的精神是背道而驰的。
C的特点之一是简洁甚至至简,
我个人就无法容忍代码中有任何多余的东西,
哪怕是一个标点符号。
这同样违背了计算机代码本质精神——精确,不多也不少。
关于main()定义是否应该写不需要的形参
librazy网友:
main的风格这两种在ACM中都无所谓……反正编译过了就行。。
garbageMan:
无法容忍
理由之一是代码中不应该有多余的东西。
此外
任何多余的东西都可能导致意料之外的错误
而墨菲定律告诉我们
任何可能出错的东西
一定会出错
所以在用不到形参的main()中写参数
在我看来就如同阑尾
我在这里补充一个有些极端的例子void swap( int *p , int *q , int *r)
{
int tmp = *p ;
* p = * q ;
* q = tmp ;
}这个函数的功能是交换两个int类型数据对象的值,错不错呢?我的看法是,错!
关于使用什么样的数据结构
librazy:
在算法竞赛中数据存储用数组还是结构体基本属于代码风格问题。
garbageMan:
不对
以为数据结构可以随意选取的想法在复杂的数据面前必定会被碰得头破血流
我的经验法则是
要处理的数据越多变量恰恰应该越少
否则最后必定一团糟
这就像卖糖葫芦一样
不能靠手一粒一粒去抓
总有你抓不住的时候
就算你能抓住
现实中有人这样做吗?
哪种是明智的做法?
道理是一样的。
对此librazy网友表示同意:
这点我同意。明显成对的数据用结构体会更好,但一些需要高级数据结构处理的数据可能存储方式会有不同。
关于flag标识变量
librazy:
原代码中的flag数组完全没用确实该吐槽一下。但如果把flag理解成算法竞赛中的标记思想,倒还是很实用的……
garbageMan:
其实我的说法意在矫枉过正,
滥用flag的现象太严重了。更可怕的是
滥用flag导致了很多扭曲变态的思考
这就是我无法容忍这个flag的原因
我崇尚代码的美感
而实现这种美感的前提是
思想的优美和简洁
我见到的用flag思考的代码
95%以上都是出自一种变态的思考
文中引用的代码即属此列
我用自己的代码证明了
思考这个问题其实根本用不着flag
且思考方式更自然更流畅
关于数组清零及外部变量(“全局变量”)
librazy:
已知的大部分OIer都习惯用for循环清空数组,遇到大数组memset。没记错的话《骗分导论》还是哪篇集训队、省队论文有分析过数组操作的时间复杂度(貌似结论是都差不多……反正怎么做都比读入快并且不影响时间复杂度。数组反倒是放全局比较好……要不然还没有MLE就爆栈了。
garbageMan:
数组像我那样安排(注:指定义局部数组并初始化,int stu[max] = {}; 以实现将stu数组全部元素初始化为0的目的。而不是用循环语句将数组各元素逐个赋值为0的方式)
显然没必要用循环清零用memset清0我认为是一种概念错误(除非是对char 数组)
这一点以前有过多次讨论
比如 http://www.cnblogs.com/pmer/p/3313913.html
至于
“没记错的话《骗分导论》还是哪篇集训队、省队论文有分析过数组操作的时间复杂度(貌似结论是都差不多……反正怎么做都比读入快并且不影响时间复杂度。数组反倒是放全局比较好……要不然还没有MLE就爆栈了。”
这些我认为都属于竞赛投机行为
在竞赛中不可避免存在
我也能理解
因为你不用这种“卑鄙”的手段
别人也会用
不用会吃亏
不用白不用
但在编程中是绝对不能摆到桌面上的
在实际编程时,外部变量绝对不能滥用,因为那可能会破坏程序整体结构,违背结构化程序设计原则。
关于数组定义
librazy网友:
数组越界的问题说明他确实是新手……按惯例一般上开MAXN+10
garbageMan:
不能容忍
我的原则是必须一个不多一个不少
很多ACMer不会从0开始数数
需要100个整数元素的数组时
int a[101];
以便
for (i = 1 ; i <101; i ++)
a[i]=i;
白白地空一个位置在前面
在我看来也是不能容忍的
因为我觉得C程序员就是要会从0开始数数
而且要数得不多不少
关于“一main到底”的问题
librazy:
还有一点就是“一main到底”的问题。作为一名程序员,这是忍无可忍的,但作为OIer/ACMer,这倒是很常见的。为了编写效率和调试方便,这种水题很少会注意代码风格的,最常见的就是全部写在main里。复杂的题目,函数也一般是按照某个算法的基本操作来分的。每个人甚至每个地区、每个学校的代码风格都可能不同。特意在晒代码(http://shaidaima.com/)采样了一些,比较常见的有 主算法逻辑写在main里,各个函数是算法操作的风格 和 main按照输入、解题、输出、关闭的顺序分成四个函数的风格/*int main(void){init();work();print();end();return 0;}*/(实质上和一main到底没有太多区别。
过多的函数调用在算法竞赛的代码量(20~200行)的情况下反而会造成编写复杂度加大、静态检查困难等问题,并且增大了时间复杂度常数。
garbageMan:
这一点我和你看法不同
一main到底确实在效率方面占便宜
无论是程序运行效率还是写代码的时间成本
只要你把代码写对。
但是任何人都不可能把代码永远写正确
这时,一main到底的缺陷就彻底暴露了
因为很难debug很难test
以他那个代码为例
如果不是一main到底
而是分成几个函数的话
应该不难找出错误
甚至根本不会发生错误
但由于一main到底
就连我都没能把他的错误完全挑出来
这就是为什么要写函数的原因:
第一不容易错
第二错了也容易找到
第三找到之后容易纠正
要知道
调试程序的时间成本和智力成本是写代码的几倍甚至几十倍
所以一main到底必须保证不会写错
但据我所知
没有人不犯错
一旦出错
哭都来不及
这个时候就会知道
一main到底是贪小便宜吃大亏的行为了“按照输入、解题、输出、关闭的顺序分成四个函数的风格/*int main(void){init();work();print();end();return 0;}*/”
不应该视同“实质上和一main到底没有太多区别”
关于算法竞赛与编程的区别
librazy:
算法和编程是有区别的,在编程实践中,我和你的观点是基本一致的。
但在算法竞赛中,首要的考虑是得分。无论写得怎么样,是打表还是爆搜,只要AC了就可以。但为了调试、编写方便,代码风格也是要注重的。
同样是C、C++,在编程和算法竞赛的实践中,形成了不同的代码风格。在编程中的要求,放在算法竞赛中可能不大合适。
算法竞赛中,需要考虑的顺序是时间复杂度最少、算法逻辑最清晰、时间常数最少、易读性最高、程序结构最清晰
当然,对于真正的神犇来说,高效地写出高效、清晰的代码也是一门必修课。
garbageMan:
同意。没招的时候谁都可能采用“下三滥”手段,只要不违反规则。
竞赛有时是不择手段的
但真正写代码时我认为必须堂堂正正
问题在于
很多人并不懂得竞赛与编程的差别
还以为编程就要像竞赛那样呢
这一点上我认为ACM的有关方面是有责任的
是应该受到谴责的
“从”还是"不从"?
这条看法来自BMan、网友:
在做数学试卷的时候你会优先选择把字写得快点还是写得好看点?
garbageMan:
如果一个考试逼着人必须把字写得很烂,那么显而易见,这个考试本身是成问题的。我觉得你我之间的区别在于,你可能毫不犹豫地接受了这种逼良为娼的考试,而我则指出了这种考试的荒谬性。我反对这种考试,反对片面追求速度和效率。我认为一个合理的考试应该全面评价代码质量。