数据结构与算法设计
设计高效率的程序是基于良好的数据结构与算法,而不是基于编程小技巧。
一般说来,数据结构与算法就是一类数据的表示及其相关的操作(这里算法不是指数值计算的算法)。从数据表示的观点来看,存储在数组中的一个有序整数表也是一种数据结构。算法是指对数据结构施加的一些操作,例如对一个线性表进行检索、插入、删除等操作。一个算法如果能在所要求的资源限制(Resource
Constraints)范围内将问题解决好,则称这个算法是有效率(Efficient)的。例如一个资源限制可能是“用于存储数据的内存有限”,或者“允许执行每个子任务所需的时间有限”。一个算法如果比其它已知算法所需要的资源都少,这个算法也被称为是有效率的。算法的代价(Cost)是指消耗的资源量。一般说来,代价是由一个关键资源例如时间或空间来评估的。
毋庸置疑,人们编写程序是为了解决问题。只有通过预先分析问题来确定必须达到的性能目标,才有希望挑选出正确的数据结构。有相当多的程序员忽视了这一分析过程,而直接选用某一个他们习惯使用的,但是与问题不相称的数据结构,结果设计出一个低效率的程序。如果使用简单的设计就能够达到性能目标时,选用复杂的数据结构也是没有道理的。
人们对常用的数据结构与算法的研究已经相当透彻,可以归纳出一些设计原则:
1) 一种数据结构与算法都有其时间、空间的开销和收益。当面临一个新的设计问题时,设计者要彻底地掌握怎样权衡时空开销和算法有效性的方法。这就需要懂得算法分析的原理,而且还需要了解所使用的物理介质的特性(例如,数据存储在磁盘上与存储在内存中,就有不同的考虑)。
2) 开销和收益有关的是时间——空间的权衡。通常可以用更大的时间开销来换取空间的收益,反之亦然。时间——空间的权衡普遍地存在于软件开发的各个阶段中。
3) 设计人员应该充分地了解一些常用的数据结构与算法,避免不必要的重复设计工作。
4) 数据结构与算法为应用服务。我们必须先了解应用的需求,再寻找或设计与实际应用相匹配的数据结构。
数据结构与算法设计的一般流程如下:
(1)数据结构与算法有全局和局部之分,当然先设计全局的,后设计局部的(通常在模块设计时进行)。
(2)根据问题的特征,先查找已经存在的数据结构与算法,挑选最合适的(并不一定是最先进的)。如果不存在现成的,那么自己设计。
(3)设计并且编写代码之后,要进行测试。如果不满足性能要求,那么要进一步优化数据结构和算法。