2.5 原理
排序。排序最显而易见的用处是产生有序的输出,该输出既可以是系统规范要求的一部分,也可以是另一个程序(也许是一个二分搜索程序)的前期准备工作。但是在变位词问题中,排序并不是关注的焦点。排序是为了将相等的元素(本例中为标识)集中到一起。这些标识产生了另外一个排序应用:将单词内字母排序使得同一个变位词类中的单词具有标准型。通过给每条记录添加一个额外的键,并按照这些键进行排序,排序函数可以用于重新排列磁盘文件中的数据。在第三部分,我们还会多次回顾排序这个主题。
二分搜索。该算法在有序表中查找元素时极为高效,并且可用于内存排序或磁盘排序。唯一的缺陷就是整个表必须已知并且事先排好序。基于该简单算法的思想在许多应用程序中都有应用。
标识。当使用等价关系来定义类时,定义一种标识使得类中的每一项都具有相同的标识,而该类以外的其他项则没有该标识,这是很有用的。对单词中的字母排序可以产生一个用于变位词类的标识。其他标识通过排序给出。然后使用一个计数来代表重复的次数(于是标识“mississippi”可以写成“i4m1p2s4”或将1省略——“i4mp2s4”)。也可以使用一个包含26个整数的数组来标识每个字母出现的次数。标识的其他应用包括:美国联邦调查局用来索引指纹的方法,以及用来识别读音相同但是拼写不同的名字的Soundex启发式方法:
Knuth⑧在其The Art of Computer Programming, Volume 3: Sorting and Sear ching⑨一书的第6章描述了Soundex方法。
问题定义。第1章指出确定用户的真实需求是程序设计的根本。本章的中心思想是问题定义的下一步:使用哪些基本操作来解决问题?在本章的每个例子中,啊哈!灵机一动都定义了一个新的基本操作使得问题得到简化。
问题解决者的观点。优秀程序员都有点懒:他们坐下来并等待灵机一动的出现而不急于使用最开始的想法编程。当然,这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握,这只能来源于解决问题和反思答案所获得的经验。