首页 > 搜索 > 查找变位词设计算法,藏在《编程珠玑》里的【啊哈!算法】这一篇你看过没?

查找变位词设计算法,藏在《编程珠玑》里的【啊哈!算法】这一篇你看过没?

互联网 2020-10-29 16:46:57
在线算命,八字测算命理
啊哈!算法

研究算法给实际编程的程序员带来许多好处。算法课教给学生完成重要任务的方法和解决新问题的技术。在后续的章节中将会看到,先进的算法工具有时候对软件系统影响很大——减少开发时间,同时使执行速度更快。

算法与其他那些深奥的思想一样重要,但在更一般的编程层面上具有更重要的影响。在《啊哈!灵机一动》一书中(本章的标题就借鉴了它),Martin Gardner①描述了深得我心的一个思想:“看起来很困难的问题也可以有一个简单的、意想不到的答案。”与高级的方法不同,算法的啊哈!灵机一动并非只有在大量的研究以后才能出现;任何愿意在编程之前、之中和之后进行认真思考的程序员都有机会捕捉到这灵机一动。

1三个问题

好了,泛泛的话讲得够多啦。本章将围绕三个小问题展开。在继续阅读以前,请先试着解决它们。

A.给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺失一个这样的数——为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内存,又该如何解决该问题?

B.将一个n元一维向量向左旋转②i个位置。例如,当n=8且i=3时,向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间,在正比于n的时间内完成向量的旋转?

C.给定一个英语字典,找出其中的所有变位词集合。例如,“pots”“stop”和“tops”互为变位词,因为每一个单词都可以通过改变其他单词中字母的顺序来得到。

2无处不在的二分搜索

我想到的一个数在1到100之间,你来猜猜看。50?太小了。75?太大了。如此,游戏进行下去,直到你猜中我想到的数为止。如果我的整数位于1到n之间,那么你可以在log2n次之内猜中。如果n是1 000,10次就可以完成;如果n是100万,则最多20次就可以完成。

这个例子引出了一项可以解决众多编程问题的技术:二分搜索。初始条件是已知一个对象存在于一个给定的范围内,而一次探测操作可以告诉我们该对象是否低于、等于或高于给定的位置。二分搜索通过重复探测当前范围的中点来定位对象。如果一次探测没有找到该对象,那么我们将当前范围减半,然后继续下一次探测。当找到所需要的对象或范围为空时停止。

在程序设计中二分搜索最常见的应用是在有序数组中搜索元素。在查找项50时,算法进行如下探测。

众所周知,二分搜索程序要正确运行很困难。在第4章中我们将详细研究其代码。

顺序搜索在搜索一个具有n个元素的表时,平均需要进行n/2次比较,而二分搜索仅仅进行不超过log2n次的比较就可以完成。这在系统性能上会造成巨大的差异。下面的故事来自于《ACM通讯》的实例研究“TWA Reservation System”。

我们有一个执行线性搜索的程序,可以在1秒钟内对一块非常巨大的内存块完成100次搜索。随着网络的增长,处理每条消息所需的平均CPU时间上升了0.3毫秒,这对我们来说是巨大的变化。我们发现问题的根源是线性搜索。把程序改为使用二分搜索以后,该问题消失了。

我在许多系统中也遇到过相同的问题。程序员在开始的时候使用简单的顺序搜索数据结构,这在开始的时候通常都足够快。当搜索变得太慢的时候,对表进行排序并使用二分搜索通常可以消除瓶颈。

但是二分搜索的故事并没有在快速搜索有序数组这里终止。Roy Weil将该技术应用于清理一个约1000行的输入文件,其中仅包含一个错误行。很不幸,肉眼看不出错误行。只能通过在程序中运行文件的一个(起始)部分并且观察到离奇错误的答案来辨别,这将会花费几分钟的时间。他的前任调试人员试图通过每次运行整个程序中的少数几行程序来找出错误行,但只在取得解决方案的道路上前进了一点点。Weil是如何仅仅运行10次程序就找到罪魁祸首的呢?

经过前面的热身,我们现在来攻克问题A。输入为顺序文件(考虑磁带或磁盘——虽然磁盘可以随机读写,但是从头至尾读取文件通常会快得多)。文件包含最多40亿个随机排列的32位整数,而我们需要找出一个不存在于该文件中的32位整数。(至少缺少一个整数,因为一共有232也就是4 294 967 296个这样的整数。)如果有足够的内存,可以采用第1章中介绍的位图技术,使用536 870 912个8位字节形成位图来表示已看到的整数。然而,该问题还问到在仅有几百字节内存和几个稀疏顺序文件的情况下如何找到缺失的整数?为了采用二分搜索技术,就必须定义一个范围、在该范围内表示元素的方式以及用来确定哪一半范围存在缺失整数的探测方法。如何来实现呢?

我们采用已知包含至少一个缺失元素的一系列整数作为范围,并使用包含所有这些整数在内的文件表示这个范围。灵机一动的结果是通过统计中间点之上和之下的元素来探测范围:或者上面或者下面的范围具有至多全部范围的一半元素。由于整个范围中有一个缺失元素,因此我们所需的那一半范围中必然也包含缺失的元素。这些就是解决该问题的二分搜索算法所需要的主要想法。在翻阅答案查看Ed Reingold是如何做的以前,请尝试将这些想法组织起来。

对于二分搜索技术在程序设计中的应用来说,这些应用仅仅是皮毛而已。求根程序使用二分搜索技术,通过连续地对分区间来求解单变量方程式(数值分析家称之为对分法)。当答案11.9中的选择算法区分出一个随机元素以后,就对该元素一侧的所有元素递归地调用自身(这是一种随机二分搜索)。其他使用二分搜索的地方包括树数据结构和程序调试(当程序没有任何提示就意外中止时,你会从源代码中哪一部分开始探测来定位错误语句呢?)。在上述的每个例子中,分析程序并对二分搜索算法做些许修改,可以带给程序员功能强大的啊哈!灵机一动。

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]开始再次进行移动,直到所有的元素都已经移动为止。习题3要求读者将该思想还原为代码,务必小心。

从另外一面考察这个问题,可以得到一个不同的算法:旋转向量x其实就是交换向量ab的两段,得到向量ba。这里a代表x中的前i个元素。假设a比b短,将b分为bl和br,使得br具有与a相同的长度。交换a和br,也就将ablbr转换为brbla。序列a此时已处于其最终的位置,因此现在的问题就集中到交换b的两部分。由于新问题与原来的问题具有相同的形式,我们可以递归地解决之。使用该算法可以得到优雅的程序(答案3描述了Gries和Mills的迭代解决方案),但是需要巧妙的代码,并且要进行一些思考才能看出它的效率足够高。

问题看起来很难,除非最终获得了啊哈!灵机一动:我们将问题看作是把数组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 McIlroy③给出了将十元数组向上旋转5个位置的翻手例子。初始时掌心对着我们的脸,左手在右手上面。

翻转代码在时间和空间上都很高效,而且代码非常简短,很难出错。Brian Kernighan④和P. J. PlaugerBrian Kernighan⑤在其1981年出版的Software Tools in Pascal一书中,就使用该代码在文本编辑器中实现了行的移动。Kernighan报告称在第一次执行的时候程序就正确运行了,而他们先前基于链表的处理相似任务的代码则包含几个错误。该代码用在几个文本处理系统中,其中包括我最初用于录入本章内容的文本编辑器。Ken Thompson⑥在1971年编写了编辑器和这种求逆代码,甚至在那时就主张把该代码当作一种常识。

4排序

现在我们来讨论问题C。给定一本英语单词字典(每个输入行是一个由小写字母组成的单词),要求找出所有的变位词分类。研究这个问题可以举出许多理由。首先是技术上的:获得这个问题的解决方案需要既具有正确的视角又能使用正确的工具。第二个理由更具有说服力:你总不想成为聚会中唯一一个不知道“deposit”“dopiest”“posited”和“topside”是变位词的人吧?如果这些理由还嫌不够,可以看一下习题6描述的现实系统中的一个相似的问题。

解决这个问题的许多方法都出奇地低效和复杂。任何一种考虑单词中所有字母的排列的方法都注定了要失败。单词“cholecystoduodenostomy”(我的字典中单词“duodenocholecystostomy”的一个变位词)有22!种排列,少量的乘法运算表明22! ≈ 1.1241021。即使假设以闪电一样的速度每百亿分之一秒执行一种排列,这也要消耗1.1109 秒。经验法则“π秒就是一个纳世纪”(见7.1节)指出1.1×109是数十年。而比较所有单词对的任何方法在我的机器上运行至少要花费一整夜的时间——在我使用的字典里有大约230 000个单词,而即使是一个简单的变位词比较也将花费至少1 微秒的时间,因此,总时间估算起来就是

230 000单词×230 000比较/单词×1微秒/比较=52 900×106微秒=52 900秒≈14.7小时

你能够找到同时避免上述缺陷的方法吗?

我们获得的啊哈!灵机一动就是标识字典中的每一个词,使得在相同变位词类中的单词具有相同的标识。然后,将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题:选择标识和集中具有相同标识的单词。在进一步阅读之前,先好好想想这些问题。

对第一个问题,我们可以使用基于排序的标识⑦:将单词中的字母按照字母表顺序排列。“deposit”的标识就是“deiopst”,这也是“dopiest”和其他任何在该类中的单词的标识。要解决第二个问题,我们将所有的单词按照其标识的顺序排序。我所知道的关于该算法的最好描述就是Tom Cargill的翻手表示:先用一种方式排序(水平翻手),再用另一种方式排序(垂直翻手)。2.8节描述了该算法的一个实现。

5原理

排序。排序最显而易见的用处是产生有序的输出,该输出既可以是系统规范要求的一部分,也可以是另一个程序(也许是一个二分搜索程序)的前期准备工作。但是在变位词问题中,排序并不是关注的焦点。排序是为了将相等的元素(本例中为标识)集中到一起。这些标识产生了另外一个排序应用:将单词内字母排序使得同一个变位词类中的单词具有标准型。通过给每条记录添加一个额外的键,并按照这些键进行排序,排序函数可以用于重新排列磁盘文件中的数据。在第三部分,我们还会多次回顾排序这个主题。

二分搜索。该算法在有序表中查找元素时极为高效,并且可用于内存排序或磁盘排序。唯一的缺陷就是整个表必须已知并且事先排好序。基于该简单算法的思想在许多应用程序中都有应用。

标识。当使用等价关系来定义类时,定义一种标识使得类中的每一项都具有相同的标识,而该类以外的其他项则没有该标识,这是很有用的。对单词中的字母排序可以产生一个用于变位词类的标识。其他标识通过排序给出。然后使用一个计数来代表重复的次数(于是标识“mississippi”可以写成“i4m1p2s4”或将1省略——“i4mp2s4”)。也可以使用一个包含26个整数的数组来标识每个字母出现的次数。标识的其他应用包括:美国联邦调查局用来索引指纹的方法,以及用来识别读音相同但是拼写不同的名字的Soundex启发式方法:

Knuth⑧在其The Art of Computer Programming, Volume 3: Sorting and Sear ching⑨一书的第6章描述了Soundex方法。

问题定义。第1章指出确定用户的真实需求是程序设计的根本。本章的中心思想是问题定义的下一步:使用哪些基本操作来解决问题?在本章的每个例子中,啊哈!灵机一动都定义了一个新的基本操作使得问题得到简化。

问题解决者的观点。优秀程序员都有点懒:他们坐下来并等待灵机一动的出现而不急于使用最开始的想法编程。当然,这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握,这只能来源于解决问题和反思答案所获得的经验。

6习题

1.考虑查找给定输入单词的所有变位词问题。仅给定单词和字典的情况下,如何解决该问题?如果有一些时间和空间可以在响应任何查询之前预先处理字典,又会如何?

2.给定包含4 300 000 000个32位整数的顺序文件,如何找出一个出现至少两次的整数?

3.前面涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独立的程序实现。在每个程序中,i和n的最大公约数如何出现?

4.几位读者指出,既然所有的三个旋转算法需要的运行时间都正比于n,杂技算法的运行速度显然是求逆算法的两倍。杂技算法对数组中的每个元素仅存储和读取一次,而求逆算法需要两次。在实际的计算机上进行实验以比较两者的速度差异,特别注意内存引用位置附近的问题。

5.向量旋转函数将向量ab变为ba。如何将向量abc变为cba?(这对交换非相邻内存块的问题进行了建模)。

6.20世纪70年代末期,贝尔实验室开发出了“用户操作的电话号码簿辅助程序”,该程序允许雇员使用标准的按键电话在公司电话号码簿中查找电话号码。

要查找该系统设计者的名字Mike Lesk⑩,可以按“LESK*M*”(也就是“5375*6*”),随后,系统会输出他的电话号码。这样的服务现在随处可见。该系统中出现的一个问题是,不同的名字有可能具有相同的按键编码。在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”。他是如何实现的呢?

本文摘自《编程珠玑 第2版》[美] 乔恩·本特利(Jon Bentley) 著,黄倩,钱丽艳 译

《编程珠玑 第2版》([美]乔恩·本特利(Jon,Bentley))【摘要 书评 试读】- 京东图书​item.jd.com经典算法和数据结构习题精粹计算机科学领域20余年畅销不衰的不朽经典程序员案头常备,融深邃思想、实战技术与趣味轶事于一炉的奇书,带你真正领略计算机科学之美

多年以来,当让程序员推选喜爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师乔恩·本特利以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇编程“珠玑”,成为世界计算机界名刊《ACM通讯》历史上受欢迎的专栏,终结集为两部计算机科学经典名著,影响和激励着一代又一代程序员和计算机科学工作者。本书为第一卷,主要讨论计算机科学中*本质的问题:如何正确选择和高效地实现算法。

在书中,作者选取许多具有典型意义的复杂编程和算法问题,生动描绘了历史上大师们在探索解决方案中发生的轶事、走过的弯路和不断精益求精的历程,引导读者像真正的程序员和软件工程师那样富于创新性地思考,并透彻阐述和总结了许多独特而精妙的设计原则、思考和解决问题的方法以及实用程序设计技巧。解决方案的代码均以C/C++语言编写,不仅有趣,而且有很大的实战示范意义。每章后所附习题极具挑战性和启发性,书末给出了简洁的解答。

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多