啊哈算法2伟⼤思维闪耀时_编程珠玑：⽆处不在的算法编程研究算法给实际编程的程序员带来许多好处。先进的算法⼯具有时候对软件系统影响很⼤——减少开发时间，同时使执⾏速度更快。
算法与其他那些深奥的思想⼀样重要，但在更⼀般的编程层⾯上具有更重要的影响。在《啊哈!灵机⼀动》⼀书中(本⽂的标题就借鉴了它)，Martin Gardner1描述了深得我⼼的⼀个思想：“看起来很困难的问题也可以有⼀个简单的、意想不到的答案。”与⾼级的⽅法不同，算法的啊哈！灵机⼀动 并⾮只有在⼤量的研究以后才能出现；任何愿意在编程之前、之中和之后进⾏认真思考的程序员都有机会捕捉到这灵机⼀动。
1　三个问题
好了，泛泛的话讲得够多啦。本⽂将围绕三个⼩问题展开。在继续阅读以前，请先试着解决它们。
A．给定⼀个最多包含40亿个随机排列的32位整数的顺序⽂件，出⼀个不在⽂件中的32位整数(在⽂件中⾄少缺失⼀个这样的数——为什么？)。在具有⾜够内存的情况下，如何解决该问题？如果有⼏个外部的“临时”⽂件可⽤，但是仅有⼏百字节的内存，⼜该如何解决该问题？
B．将⼀个n元⼀维向量向左旋转2i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使⽤⼀个n元的中间向量在n步内完成该⼯作。你能否仅使⽤数⼗个额外字节的存储空间，在正⽐于n的时间内完成向量的旋转?
C．给定⼀个英语字典，出其中的所有变位词集合。例如，“pots”、“stop”和“tops”互为变位词，因为每⼀个单词都可以通过改变其他单词中字母的顺序来得到。
2　⽆处不在的⼆分搜索
我想到的⼀个数在1到100之间，你来猜猜看。50？太⼩了。75？太⼤了。如此，游戏进⾏下去，直到你猜中我想到的数为⽌。如果我的整数位于1到n之间，那么你可以在次之内猜中。如果n是1 000，10次就可以完成；如果n是100万，则最多20次就可以完成。
这个例⼦引出了⼀项可以解决众多编程问题的技术：⼆分搜索。初始条件是已知⼀个对象存在于⼀个给定的范围内，⽽⼀次探测操作可以告诉我们该对象是否低于、等于或⾼于给定的位置。⼆分搜索通过重复探测当前范围的中点来定位对象。如果⼀次探测没有到该对象，那么我们将当前范围减半，然后继续下⼀次探测。当到所需要的对象或范围为空时停⽌。
在程序设计中⼆分搜索最常见的应⽤是在有序数组中搜索元素。在查项50时，算法进⾏如下探测。
众所周知，⼆分搜索程序要正确运⾏很困难。
顺序搜索在搜索⼀个具有n个元素的表时，平均需要进⾏n/2次⽐较，⽽⼆分搜索仅仅进⾏不超过次的⽐较就可以完成。这在系统性能上会造成巨⼤的差异。下⾯的故事来⾃于《ACM通讯》的实例研究“TWA Reservation System”。
我们有⼀个执⾏线性搜索的程序，可以在1秒钟内对⼀块⾮常巨⼤的内存块完成100次搜索。随着⽹络的增长，处理每条消息所需的平均CPU时间上升了0.3毫秒，这对我们来说是巨⼤的变化。我们发现问题的根源是线性搜索。把程序改为使⽤⼆分搜索以后，该问题消失了。
我在许多系统中也遇到过相同的问题。程序员在开始的时候使⽤简单的顺序搜索数据结构，这在开始的时候通常都⾜够快。当搜索变得太慢的时候，对表进⾏排序并使⽤⼆分搜索通常可以消除瓶颈。
厉害的编程代码但是⼆分搜索的故事并没有在快速搜索有序数组这⾥终⽌。Roy Weil将该技术应⽤于清理⼀个约1000⾏的输⼊⽂件，其中仅包含⼀个错误⾏。很不幸，⾁眼看不出错误⾏。只能通过在程序中运⾏⽂件的⼀个(起始)部分并且观察到离奇错误的答案来辨别，这将会花费⼏分钟的时间。他的前任调试⼈员试图通过每次运⾏整个程序中的少数⼏⾏程序来出错误⾏，但只在取得解决⽅案的道路上前进了⼀点点。Weil是如何仅仅运⾏10次程序就到罪魁祸⾸的呢？
经过前⾯的热⾝，我们现在来攻克问题A。输⼊为顺序⽂件(考虑磁带或磁盘——虽然磁盘可以随机读写，但是从头⾄尾读取⽂件通常会快得多)。⽂件包含最多40亿个随机排列的32位整数，⽽我们需要出⼀个不存在于该⽂件中的32位整数。(⾄少缺少⼀个整数，因为⼀共有232也就是4 294 967 296个这样的整数。)如果有⾜够的内存，可以采⽤位图技术，使⽤536 870 912个8位字节形成位图来表⽰已看到的整数。然⽽，该问题还问到在仅有⼏百个字节内存和⼏个稀疏顺序⽂件的情况下如何到缺失的整数？为了采⽤⼆分搜索技术，就必须定义⼀个范围、在该范围内表⽰元素的⽅式以及⽤来确定哪⼀半范围存在缺失整数的探测⽅法。如何来实现呢？
我们采⽤已知包含⾄少⼀个缺失元素的⼀系列整数作为范围，并使⽤包含所有这些整数在内的⽂件表⽰这个范围。灵机⼀动的结果是通过统计中间点之上和之下的元素来探测范围：或者上⾯或者下⾯的范围具有⾄多全部范围的⼀半元素。由于整个范围中有⼀个缺失元素，因此我们所需的那⼀半范围中必然也包含缺失的元素。这些就是解决该问题的⼆分搜索算法所需要的主要想法。在翻阅答案查看Ed Reingold是如何做的以前，请尝试将这些想法组织起来。
对于⼆分搜索技术在程序设计中的应⽤来说，这些应⽤仅仅是⽪⽑⽽已。求根程序使⽤⼆分搜索技术，通过连续地对分区间来求解单变量⽅程式(数值分析家称之为对分法)。当选择算法区分出⼀个随机元素以后，就对该元素⼀侧的所有元素递归地调⽤⾃⾝(这是⼀种随机⼆分搜索)。其他使⽤⼆分搜索的地⽅包括树数据结构和程序调试(当程序没有任何提⽰就意外中⽌时，你会从源代码中哪⼀部分开始探
测来定位错误语句呢？)。在上述的每个例⼦中，分析程序并对⼆分搜索算法做些许修改，可以带给程序员功能强⼤的啊哈！灵机⼀动。
3　基本操作的威⼒
⼆分搜索是许多问题的解决⽅案，下⾯研究⼀个有⼏种解决⽅案的问题。问题B仅使⽤⼏⼗个字节的额外空间将⼀个n元向量x在正⽐于n的时间内向左旋转i个位置。该问题在应⽤程序中以各种不同的伪装出现。在⼀些编程语⾔中，该功能是向量的⼀个基本操作。更重要地，旋转操作对应于交换相邻的不同⼤⼩的内存块：每当拖动⽂件中的⼀块⽂字到其他地⽅时，就要求程序交换两块内存中的内容。在许多应⽤场合下，运⾏时间和存储空间的约束会很严格。
可以通过如下⽅式解决该问题：⾸先将x的前i个元素复制到⼀个临时数组中，然后将余下的n－i个元素向左移动i个位置，最后将最初的i个元素从临时数组中复制到x中余下的位置。但是，这种办法使⽤的i个额外的位置产⽣了过⼤的存储空间的消耗。另⼀种⽅法是定义⼀个函数将x向左旋转⼀个位置(其时间正⽐于n)然后调⽤该函数i次。但该⽅法⼜产⽣了过多的运⾏时间消耗。
要在有限的资源内解决该问题，显然需要更复杂的程序。有⼀个成功的⽅法有点像精巧的杂技动作：移动x[0]到临时变量t，然后移动x[i]⾄x[0]，x[2i]⾄x[i]，依此类推(将x中的所有下标对n取模)，直⾄返回到取x[0]中的元素，此时改为从t取值然后终⽌过程。当i为3且n为12时，元素按如下顺序移动。
如果该过程没有移动全部元素，就从x[1]开始再次进⾏移动，直到所有的元素都已经移动为⽌。
从另外⼀⾯考察这个问题，可以得到⼀个不同的算法：旋转向量x其实就是交换向量ab的两段，得到向量ba。这⾥a代表x中的前i个元素。假设a⽐b短，将b分为bl和br，使得br具有与a相同的长度。交换a和br，也就将ablbr转换为brbla。序列a此时已处于其最终的位置，因此现在的问题就集中到交换b的两部分。由于新问题与原来的问题具有相同的形式，我们可以递归地解决之。使⽤该算法可以得到优雅的程序，但是需要巧妙的代码，并且要进⾏⼀些思考才能看出它的效率⾜够⾼。
问题看起来很难，除⾮最终获得了啊哈！灵机⼀动：我们将问题看做是把数组ab转换成ba，同时假定我们拥有⼀个函数可以将数组中特定部分的元素求逆。从ab开始，⾸先对a求逆，得到arb，然后对b求逆，得到arbr。最后整体求逆，得到(arbr)r。此时就恰好是ba。于是，我们得到了如下⽤于旋转的代码，其中注释部分表⽰abcdefgh向左旋转三个位置以后的结果。
reverse(0,i-1)    /* cbadefgh */reverse(i,n-1)    /* cbahgfed */reverse(0,n-1)    /* defghabc */
Doug McIlroy3给出了将⼗元数组向上旋转5个位置的翻⼿例⼦。初始时掌⼼对着我们的脸，左⼿在右⼿上⾯。
翻转代码在时间和空间上都很⾼效，⽽且代码⾮常简短，很难出错。Brian Kernighan4和P. J. Plauger5在其1981年出版的Software Tools in Pascal⼀书中，就使⽤该代码在⽂本编辑器中实现了⾏的移动。Kernighan报告称在第⼀次执⾏的时候程序就正确运⾏了，⽽他们先前基于链表的处理相似任务的代码则包含⼏个错误。该代码⽤在⼏个⽂本处理系统中，其中包括我最初⽤于录⼊本章内容的⽂本编辑器。Ken Thompson6在1971年编写了编辑器和这种求逆代码，甚⾄在那时就主张把该代码当作⼀种常识。
4　排序
现在我们来讨论问题C。给定⼀本英语单词字典(每个输⼊⾏是⼀个由⼩写字母组成的单词)，要求出所有的变位词分类。研究这个问题可以举出许多理由。⾸先是技术上的：获得这个问题的解决⽅案需要既具有正确的视⾓⼜能使⽤正确的⼯具。第⼆个理由更具有说服⼒：你总不想成为聚会中唯⼀⼀个不知道“deposit”、“dopiest”、“posited”和“topside”是变位词的⼈吧？
解决这个问题的许多⽅法都出奇地低效和复杂。任何⼀种考虑单词中所有字母的排列的⽅法都注定了要失败。单
词“cholecystoduodenostomy”(我的字典中单词“duodenocholecystostomy”的⼀个变位词)有22！种排列，少量的乘法运算表明22! ≈ 1.1241021。即使假设以闪电⼀样的速度每百亿分之⼀秒执⾏⼀种排列，这也要消耗1.1109 秒。经验法则“π秒就是⼀个纳世纪”指出1.1109是数⼗年。⽽⽐较所有单词对的任何⽅法在我的机器上运⾏⾄少要花费⼀整夜的时间——在我使⽤的字典⾥有⼤约230 000个单词，⽽即使是⼀个简单的变位词⽐较也将花费⾄少1 微秒的时间，因此，总时间估算起来就是
230 000单词230 000⽐较/单词1微秒/⽐较=52 900106微秒=52 900秒≈14.7⼩时
你能够到同时避免上述缺陷的⽅法吗？
我们获得的啊哈！灵机⼀动 就是标识字典中的每⼀个词，使得在相同变位词类中的单词具有相同的标
识。然后，将所有具有相同标识的单词集中在⼀起。这将原始的变位词问题简化为两个⼦问题：选择标识和集中具有相同标识的单词。在进⼀步阅读之前，先好好想想这些问题。
对第⼀个问题，我们可以使⽤基于排序的标识7：将单词中的字母按照字母表顺序排列。“deposit”的标识就是“deiopst”，这也
是“dopiest”和其他任何在该类中的单词的标识。要解决第⼆个问题，我们将所有的单词按照其标识的顺序排序。我所知道的关于该算法的最好描述就是Tom Cargill的翻⼿表⽰：先⽤⼀种⽅式排序(⽔平翻⼿)，再⽤另⼀种⽅式排序(垂直翻⼿)。
5　原理
排序 排序最显⽽易见的⽤处是产⽣有序的输出，该输出既可以是系统规范要求的⼀部分，也可以是另⼀个程序(也许是⼀个⼆分搜索程序)的前期准备⼯作。但是在变位词问题中，排序并不是关注的焦点。排序是为了将相等的元素(本例中为标识)集中到⼀起。这些标识产⽣了另外⼀个排序应⽤：将单词内字母排序使得同⼀个变位词类中的单词具有标准型。通过给每条记录添加⼀个额外的键，并按照这些键进⾏排序，排序函数可以⽤于重新排列磁盘⽂件中的数据。在第三部分，我们还会多次回顾排序这个主题。
⼆分搜索 该算法在有序表中查元素时极为⾼效，并且可⽤于内存排序或磁盘排序。唯⼀的缺陷就是整个表必须已知并且事先排好序。基于该简单算法的思想在许多应⽤程序中都有应⽤。
标识 当使⽤等价关系来定义类时，定义⼀种标识使得类中的每⼀项都具有相同的标识，⽽该类以外的其他项则没有该标识，这是很有⽤的。对单词中的字母排序可以产⽣⼀个⽤于变位词类的标识。其他标识通过排序给出。然后使⽤⼀个计数来代表重复的次数(于是标
识“mississippi”可以写成“i4m1p2s4”或将1省略——“i4mp2s4”)。也可以使⽤⼀个包含26个整数的数组来标识每个字母出现的次数。标识的其他应⽤包括：美国联邦调查局⽤来索引指纹的⽅法，以及⽤来识别读⾳相同但是拼写不同的名字的Soundex启发式⽅法：
Knuth8在其The Art of Computer Programming, Volume 3: Sorting and Sear ching9⼀书的描述了Soundex⽅法。
问题定义。确定⽤户的真实需求是程序设计的根本。本⽂的中⼼思想是问题定义的下⼀步：使⽤哪些基本操作来解决问题？在每个例⼦中，啊哈！灵机⼀动都定义了⼀个新的基本操作使得问题得到简化。
问题解决者的观点。优秀程序员都有点懒：他们坐下来并等待灵机⼀动的出现⽽不急于使⽤最开始的想法编程。当然，这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握，这只能来源于解决问题和反思答案所获得的经验。
6　习题
1．考虑查给定输⼊单词的所有变位词问题。仅给定单词和字典的情况下，如何解决该问题？如果有⼀些时间和空间可以在响应任何查询之前预先处理字典，⼜会如何？
2．给定包含4 300 000 000个32位整数的顺序⽂件，如何出⼀个出现⾄少两次的整数？
3．前⾯涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独⽴的程序实现。在每个程序中，i和n的最⼤公约数如何出现？
4．⼏位读者指出，既然所有的三个旋转算法需要的运⾏时间都正⽐于n，杂技算法的运⾏速度显然是求逆算法的两倍。杂技算法对数组中的每个元素仅存储和读取⼀次，⽽求逆算法需要两次。在实际的
计算机上进⾏实验以⽐较两者的速度差异，特别注意内存引⽤位置附近的问题。
5．向量旋转函数将向量ab变为ba。如何将向量abc变为cba？(这对交换⾮相邻内存块的问题进⾏了建模)。
6．20世纪70年代末期，贝尔实验室开发出了“⽤户操作的电话号码簿辅助程序”，该程序允许雇员使⽤标准的按键电话在号码簿中查电话号码。
要查该系统设计者的名字Mike Lesk10，可以按“LESKM”(也就是“53756”)，随后，系统会输出他的电话号码。这样的服务现在随处可见。该系统中出现的⼀个问题是，不同的名字有可能具有相同的按键编码。在Lesk的系统中发⽣这种情况时，系统会询问⽤户更多的信息。给定⼀个⼤的名字⽂件(例如标准的⼤城市电话号码簿)，如何定位这些“错误匹配”呢？(当Lesk在这种规模的电话号码簿上做实验时，他发现错误匹配发⽣的概率仅仅是0.2%。)如何实现⼀个以名字的按键编码为参数，并返回所有可能的匹配名字的函数？
7．在20世纪60年代早期，Vic Vyssotsky与⼀个程序员⼀起⼯作，该程序员需要转置⼀个存储在磁带上的4 000×4 000的矩阵(每条记录的格式相同，为数⼗个字节)。他的同事最初提出的程序需要运⾏50个⼩时。Vyssotsky如何将运⾏时间减少到半⼩时呢？
8．[J. Ullman]给定⼀个n元实数集合、⼀个实数t和⼀个整数k，如何快速确定是否存在⼀个k元⼦集，其元素之和不超过t？
9．顺序搜索和⼆分搜索代表了搜索时间和预处理时间之间的折中。处理⼀个n元表格时，需要执⾏多少次⼆分搜索才能弥补对表进⾏排序
所消耗的预处理时间？
10．某⼀天，⼀个新研究员向托马斯·爱迪⽣报到。爱迪⽣要求他计算出⼀个空灯泡壳的容积。在使⽤测径仪和微积分进⾏数⼩时的计算
后，这个新员⼯给出了⾃⼰的答案——150 cm3。⽽爱迪⽣在⼏秒钟之内就计算完毕并给出了结果“更接近155”。他是如何实现的呢？
7　变位词程序的实现(边栏)
我的变位词程序按三个阶段的“管道”组织，其中⼀个程序的输出⽂件作为下⼀个程序的输⼊⽂件。第⼀个程序标识单词，第⼆个程序排序
标识后的⽂件，⽽第三个程序将这些单词压缩为每个变位词类⼀⾏的形式。下⾯是⼀个仅有6个单词的字典的处理过程。
输出包括三个变位词类。
下⾯的C语⾔sign程序假定没有超过100个字母的单词，并且输⼊⽂件仅包含⼩写字母和换⾏符。(因此我使⽤了⼀个⼀⾏的命令对字典进⾏
预处理，将其中的⼤写字母改为⼩写字母。)
int charcomp(char *x, char *y) { return *x - *y;}#define WORDMAX 100int main(void){  char word[WORDMAX], sig[WORDMAX];    while (scanf("%s", word) !=EOF)
while循环每次读取⼀个字符串到word中，直⾄⽂件末尾为⽌。strcpy函数复制输⼊单词到单词sig中，然后调⽤C标准库函数qsort对单词
sig中的字母进⾏排序(参数是待排序的数组、数组的长度、每个待排序项的字节数以及⽐较两个项的函数名。在本例中，待⽐较项为单词中
的字母)。最后，printf语句依次打印标识、单词本⾝和换⾏符。
系统sort程序将所有具有相同标识的单词归拢到⼀起。squash程序在同⼀⾏中将其打印出来。
int main(void){  char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];  int linenum = 0;    strcpy(oldsig, "");  while (scanf("%s %s", sig, word) != EOF) {
⼤部分⼯作都是使⽤第⼆个printf语句来完成的。对每⼀个输⼊⾏，该语句输出第⼆个字段，后⾯跟⼀个空格。if语句捕捉标识之间的差
异。如果sig与oldsig(其上⼀次的值)不同，那么就打印换⾏符(⽂件中的第⼀条记录除外)。最后⼀个printf输出最后⼀个换⾏符。
在使⽤⼩输⼊⽂件对这些简单部分进⾏测试后，我通过下⾯的命令构建了变位词列表：
sign gramlist
该命令将⽂件dictionary输⼊到程序sign，连接sign的输出⾄sort，连接sort的输出⾄squash，并将squash的输出写⼊⽂件gramlist。程
序的运⾏时间为18秒：sign⽤时4秒、sort⽤时11秒⽽squash⽤时3秒。
我在⼀个包含230 000个单词的字典上运⾏了该程序。然⽽，不包括众多的-s和-ed后缀。以下是⼀些很有趣的变位词类。
subessential suitablenesscanter creant cretan nectar recant tanrec trancecaret carte cater crate creat creta react recta tracedestain instead sainted satinedadroit

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。