马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？我要加入
x
论程序设计方法
作者：杨老师
如果你是初学者----------------请不要阅读；
但有志成为中高级程序员--------请务必阅读；
如果你是中级程序员------------请务必阅读；
如果你高级程序员--------------请批评指正。
本文是我在“软件工程师班”开学第一节课的讲义，和“计算机软件设计发展”讲座上的内容整理而成。写作本文的目的是引导学生从更高的层次来看待程序设计方法，为将来成为高级程序员而做好理论准备。
一、计算机硬件环境对软件设计方法的限制
计算机的发明到现在已经60年了，计算机程序设计方法也伴随着计算机硬件技术的提高而不断发展。硬件环境对软件设计既有严重的制约作用，也有积极的推动作用。
在我的大学母校（此处删除6个字），数学系的一些老师，有幸成为了我国第一代的计算机DIY一族。呵呵，不要以为是组装PC机呦，他们组装的可是小型机。一人多高铁皮柜大小的主机，加上纸带机（后期改进为读卡机），组装好后，除了供学校自己的科研使用外，还在全国各地销售了十几台。当时（七十年代）一台的售价是10几万元人民币，如果换算到今天，相当于价值大约为100多万元，非常高档的小型计算机了。下面大家猜猜，这么高档的计算机，它的内存是多少那？（都把嘴闭好了，我要公布答案了）—— 4K。
一块50公分见方的内存板，
插入到主机箱中，好了------ 1K；
再插一块内存板，好了------ 2K；
再插一块内存板，好了------ 3K；
再插一块内存板，好了------ 4K；
再......不行了，插不起了，太贵了！这就是当时的环境。这样的环境下，用什么写程序那？当然只有机器码了。先用汇编写，然后翻阅手册手工改写为机器码，然后打卡或穿纸带，输入运行。可以想象，在当时的条件下，什么叫好的程序那？什么叫优秀的程序那？—— 技巧！
程序设计的最初始阶段，是讲究技巧的年代。如何能节省一个字节，如何能提高程序运行的效率，这些都是要严肃考虑的问题。而所谓的程序的易读性，程序的可维护性根本不在考虑范围之内。
今天，35岁以上的学习过计算机的朋友可能都使用过一种个人计算机——APPLE-II（中国也生产过这种计算机的类似产品“中华学习机”）。主频1M，内存48K（扩展后，最多可达到64K）。我就是使用这样的计算机长大的 :)。当年，类似的个人计算机产品，还有PC1500，Layser310等。这种计算机上已经固化了 BASIC 语言，当然只是为学习使用。要想开发出真正的商业程序，则必须使用汇编，否则的话，程序就比蜗牛还要慢了。于是，程序设计中对于技巧的运用，是至关重要的了。
题外话1：
比尔盖茨是 BASIC 的忠实拥护和推动者。当年，他在没有调式环境的状况下，用汇编语言写出了一款仅有 4K 大小的 BASIC 解释器，且一次通过。确实另人佩服。（不象现在微软出品的程序，动辄几十兆。）这也许就是比尔对 BASIC 情有独忠的原因，每当微软推出（临摹）一个新技术，则他会立刻在 BASIC 中提供支持。
题外话2：
在 APPLE-II 上有一款游戏软件“警察抓小偷”，当年熬夜玩游戏，乐趣无穷。后来这款游戏被移植到了PC上，咳~~~根本没有办法玩，因为小偷还没跑就被警察抓到了。硬件的速度提升，另我无法再回味以前的时光了。
二、结构化程序设计
随着计算机的价格不断下降，硬件环境不断改善，运行速度不断提升。程序越写越大，功能越来越强，讲究技巧的程序设计方法已经不能适应需求了。记得是哪本书上讲过，一个软件的开发成本是由：程序设计 30% 和程序维护 70% 构成。这是书上给出的一个理论值，但实际上，从我十几年的工作经验中，我得到的体会是：程序设计占 10%，而维护要占 90%。也许我说的还是太保守了，维护的成本还应该再提高。下面这个程序，提供了两种设计方案，大家看看哪个更好一些那？
题目：对一个数组中的100个元素，从小到大排序并显示输出。(BASIC)
方法1：冒泡法排序，同时输出。
FOR I=1 TO 100
FOR J=I+1 TO 100
IF A[I] > A[J] THEN T=A[J]: A[J]=A[I]: A[I]=T
NEXT J
? A[I]
NEXT I
方法2：冒泡法排序，然后再输出。 FOR I=1 TO 100
FOR J=I+1 TO 100
IF A[I] > A[J] THEN T=A[J]: A[J]=A[I]: A[I]=T
NEXT
NEXT
FOR I=1 TO 100
? A[I]
NEXT
显然，“方法1”比“方法2”的效率要高，运行的更快。但是，从现在的程序设计角度来看，“方法2”更高级。原因很简单：（1）功能模块分割清晰——易读；（2）也是最重要的——易维护。程序在设计阶段的时候，就要考虑以后的维护问题。比如现在是实现了在屏幕上的输出，也许将来某一天，你要修改程序，输出到打印机上、输出到绘图仪上；也许将来某一天，你学习了一个新的高级的排序方法，由“冒泡法”改进为“快速排序”、“堆排序”。那么在“方法2”的基础上进行修改，是不是就更简单了，更容易了？！这种把功能模块分离的程序设计方法，就叫“结构化程序设计”。
三、对程序设计中技巧使用的思考
我可以肯定，大家在开始学习程序设计的时候，一定都做过这样一个题目：求100以内的素数。老师在黑板上，眉飞色舞地写出了第一个程序：（C程序）
方法1： for(i=1; i<100; i++)
{ for(j=2; j< i; j++)
if(i%j == 0) break;
if(j >= i) printf("%d,", i);
}
然后，老师开始批判这个程序“这个叫什么呀？太慢了！因为我们都知道大偶数不可能是素数了，因此，要排除掉！” 于是，意尤未尽地写出了第二个程序：
方法2： printf("2,");
for(i=3; i<100; i+=2)
{ for(j=2; j< i; j++)
if(i%j == 0) break;
if(j >= i) printf("%d,", i);
}
老师说：“看！我们只改动了一点点，程序运行的速度就提高了一倍多”。然后运用诱导式教学法继续提问“程序的效率，还能再提高吗？能！”，得意地写出第三个程序：
方法3： printf("2,");
for(i=3; i<100; i+=2) ''''不考虑大偶数
{ for(j=3; j< i/2; j+=2) ''''不考虑用偶数去测试，而且只验算到一半就足够了
if(i%j == 0) break;
if(j >= i) printf("%d,", i);
}
“大家看，我们又只改动了一点点，运行速度又提高了一倍多。可以了吗？不可以！我们还能再提高”。于是又高傲地写出了第四个程序：
方法4： printf("2,");
for(i=3; i<100; i+=2)
{ int k = sqrt(i);
for(j=3; j<= k; j+=2)
if(i%j == 0) break;
if(j >= k ) printf("%d", i);
}
然后，开始证明为什么我们判断素数的时候，只需要验算到平方根就足够了：
假设p是合数，那么令:p=a*b。反正法：由于我们已经判断了p的平方根以内的整数都不能被p整除，于是 a>SQRT(p)。基于同样的理由 b>SQRT(p)。于是 p = a * b > SQRT(p) * SQRT(p) = p 得出矛盾， 命题得正。
的确，“方法4”的确比“方法1”的运行速度要提高了好几倍，甚至好几十倍。但我们仔细分析测试看看。
（1）“程序4”到底比“程序1”快了多少那？我在某台计算机上进行测试（P4，1.5G)得到的速度对比表：
计算范围
100 1000 10000 100000
速度差 0.00秒 0.01秒 0.18秒 15秒
（2） 在10万以上，才会看出一些差别。而这种差别根本就不够底偿程序设计阶段的付出。如果计算的范围再大，那么不管是“方法1”，还是“方法4”都不是好的算法。（计算素数的另外一个比较优秀的算法叫“漏筛法”）
（3）写出“方法1”，只要具有小学四年级的数学水平就够了，而“方法4”则需要初中三年级的水平并且还要具备一些“数论”的知识。
（4）从维护性看，如果你写的程序需要另外一个程序员来维护，或者若干时间以后，你重新来阅读这段程序，那么就会对这个程序产生很多疑问：这个求平方根是干什么用的？其实，就这个题目来说，使用到“方法3”就已经足够了。
总结发言：
I. 计算机的价格每年下降一半，而运算速度每年提高一倍”，因此我们应该把速度提高的任务交给硬件实现。
II. 从易读性、维护性出发，程序员只负责按定义给出软件实现。算法的问题是数学家解决的。
题外话：
多年以来，人们一直在寻找动态图象(影视)的存储和回放的算法，但效果都不理想。直到有人发现，原来在200多年前的数学家早就帮我们解决了这个问题——傅立叶（Fourier）级数展开。因此我要说，优秀的算法不是我们程序员要考虑的问题，我们的任务只要按照数学家给出的算法翻译为计算机程序语言而已。（这句话恐怕要遭到大多数程序员抛出的板砖袭击）再比如，计算一元多次方程解的问题。我们使用的就是牛顿的迭代算法。不要怪我瞧不起你，你能发明这个方法的话，那就是当代的牛顿了。
四、程序的易读性与书写方法
程序是否容易阅读和维护，与怎么书写有很大的关系。说实在的，C语言中为了方便程序员书写，允许使用++,--,<<,&&，？......这些运算符号。但很多人经常乱用，以为自己写的程序多么简洁，效率多高。其实，当你分行书写的话则更加容易阅读和维护，效率也不会降低，因为编译程序早就帮你优化为最快捷的代码了。先看一个简单的例子：
计算一个整数乘 255(C语言)
方法1：a *= 255;
方法2：因为移位运算比乘法运算要快很多倍，因此a*255的运算书写为：
a =(a<<8)-a; //a*255 = a*256 - a = (a<<8) - a
方法1的书写非常简单，直截了当，显然更容易维护。而方法2的书写运用了移位的技巧，不容易阅读，但效率最高。是不是真的是这样那？把这两个程序编译为汇编代码看看。原来无论是方法1还是方法2，它们的汇编代码都是一样的：
mov ecx, eax
shl eax, 8
sub eax, ecx
也就是说，你认为非常技巧的书写方法，其实编译器的优化功能早就帮你想到了。那么方法2的方式就很值得批判了。下面是几个有关C语言书写方面的重要原则：
尽量表达愿义，多加注释；
变量名称和函数名称，要使用有意义的符号，并且遵守“匈牙利命名法”；
不要为俭省内存，使一个变量在一个模块中表达多个含义。
在某个模块中，前半部分用i表示计数器，由于后半部分不再使用计数器了，于是又用i来保存某个中间的结果。等你维护这段程序的时候，保证你肯定会犯傻的。
在使用条件表达式的时候，不要混合书写运算表达式；
经常有人在书写for循环的时候，使用这样的方式： for(int a=1,s=0; a<=100 && (s+=a); a++);
天呀，这样写是不会提高程序运行效率的，尤其是当运算表达式复杂的时候，就更不容易阅读了，还是把运算写到for的循环体中吧。 int s = 0;
for(int a=1; a<=100; a++)
s += a; //计算1+2+...+100 这不很好吗?!
再比如，if(a=b)这个写法在语法上是允许的，但不要使用。要使用也要if(0!=(a=b))这样的方式。 还有值得一提的是慎用“,”（逗号运算符）。
不要连续使用++,--,<<，*，& .....这样的运算符号。
a = b++-(--c<<1+e&0x0f>>1); //这个人有病。出这个题目考试的老师，也有病。
常量要写在条件表达式的左边；
if(5 == a) 这是正确的写法，这样书写可以避免勿输入而导致的 if(a=5)这样的错误。
避免程序中{ }的嵌套层次太深；
最多4层。如果必须大于4层，那么写成调用子函数或宏的方式。
尽量多地使用断言；
当你在书写程序的过程中，凭你的智慧，你一定是知道：程序运行到我正书写的这行代码的时候某个变量一定是某个值。好啦，那么不要忧郁，马上加上一句代码：ASSERT(nnn == xxx);。将来在调式维护这段代码的时候，你会得到无限美妙的回报。
书写需要“成对匹配”使用的代码的时候，在写使用代码之前，就先把结束写出来；
file.Open(...); //当要打开文件的时候 char *lp=new char [100]; //当要申请内存的时候
...... //先不要写这段代码 ...... //先不要写这段代码
file.Close(); //马上写关闭 delete [] lp; //马上写释放
xxx.Loack(); //当某个对象需要锁定的时候 for(....)
...... //先不要写这段代码 { //写大括号的时候
xxx.Unlock(); //马上写解锁 } //马上写大括号结束
和这个道理相同，在C++的类中，如果需要申请内存，那么先在构造函数中给出 lp=NULL;然后马上在析构函数中书写 if(lp) delete []lp; |
发表于 2006-8-30 08:12
提升卡
变色卡
显身卡
楼主