豆瓣评分9.1,这本计算机经典名著,我读到凌晨三点

  • 时间:
  • 浏览:0
  • 来源:决战梭哈棋牌_决战梭哈棋牌官网

今日荐书 《编程珠玑 第2版》

这番对话让难题报告 更明确了。在美国,电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号30(当时这样這個 有有一个号码)的电话是不收费的。实际的免费电话号码数据库蕴藏血块的信息:免费电话号码、呼叫实际中转到的号码(有时是有几个号码,这时都要一点规则来决定哪此呼叫在哪此时间中转到哪里)、主叫用户的姓名和地址等。

归并排序读入输入文件一次,就让 在工作文件的帮助下完成排序并写入输出文件一次。工作文件都要多次读写。

本书每一章都独立成篇,各章之间却又有着逻辑分组。第1章至第5章构成本书的第一帕累托图,这帕累托图回顾了编程的基本原理:难题报告 定义、算法、数据行态以及多多应用程序 验证和测试。第二帕累托图围绕下行速率 這個 主题展开。下行速率 难题报告 有时三种不得劲要,又永远一定会进入有趣编程难题报告 的绝佳跳板。第三帕累托图用哪此技术来补救排序、搜索和字符串等重要难题报告 。

这样在输入文件中的所有整数都也能在可用的1 MB内存中表示的事先才也能实现该方案。于是难题报告 就归结为否有有也能用大概30万个可用位来表示最多1 000万个互异的整数。考虑三种大概的表示土法律法律法律依据。

对多多应用程序 员来说,哪此需求加起来什么都我:“怎样给磁盘文件排序?”在试图补救這個 难题报告 事先,先将已知条件组织成三种更客观、更易用的形式。

请花上一分钟思考一下该难题报告 的规范说明。现在你打算给多多应用程序 员哪此样的建议呢?

这位多多应用程序 员正在开发同类数据库的补救系统的一小帕累托图,都要排序的整数什么都我免费电话号码。输入文件是电话号码的列表(已删除所有一点信息),号码重复出先算出错。期望的输出文件是以升序排列的电话号码列表。应用背景一起定义了相应的性能需求。当与系统的会话时间较长时,用户大概每小时请求一次有序文件,就让 在排序未完成事先哪此都干不了。就让 ,排序最多只允许执行几分钟,10秒钟是比较理想的运行时间。

- END -

简单的设计。Antoine de Saint-Exupéry是法国作家兼飞机设计师,他曾经说过:“设计者取舍 其设计可能达到了完美的标准一定会这样再增加任何东西,什么都我这样再减少任何东西。”更多的多多应用程序 员应该使用该标准来检验被委托人完成的多多应用程序 。简单的多多应用程序 通常比具有相同功能的错综复杂的多多应用程序 更可靠、更安全、更健壮、更高效,就让 易于实现和维护。

阅读本书所需的唯一背景知识什么都我三种高级语言的编程经验。书中偶尔会出先一点高级技术(如C++中的模板等),对此不粉悉的读者也能跳过哪此内容,基本上不影响阅读。

每条记录一定会7位的正整数,再无一点相关数据。每个整数最多只出先一次。

一位多多应用程序 员曾问我一有有一个很简单的难题报告 :“怎样给一有有一个磁盘文件排序?”想当年我是一上来就犯了错误,现在,在讲這個 故事事先,先给当我门都都 一有有一个可能,看看也能比我当年做得更好。我能 怎样回答上述难题报告 呢?

文件最多蕴藏30万条记录,每条记录一定会7位的整数。

https://item.jd.com/12243652.html

本书大帕累托图内容最初发表在《ACM通讯》中我主持的“编程珠玑”专栏。哪此内容经过汇总和修订,在1986年结集出版,成为本书的第1版。第1版的13篇文章中,有12篇一定会本版中做了大幅修订;此外,本版还补充了3篇新的内容。

约束:最多有(大概)1 MB的内存空间可用,有富有的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不都要进一步优化了。

作者:[美]乔恩·本特利(Jon Bentley)

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

下图所示的方案更可取。当我门都都 结合上述三种土法律法律法律依据的优点,读输入文件仅一次,且不使用顶端文件。

我都要在一有有一个大系统中排序。可能不明的技术因为 ,我这样使用系统中的文件排序多多应用程序 。

那个多多应用程序 员打电话把他的难题报告 不知道,就让 当我门都都 花了大概一刻钟时间明确了难题报告 所在,并找到了位图补救方案。他花了几小时来实现這個 几十行代码的多多应用程序 。该多多应用程序 远远优于当我门都都 在电话过后结束了了时所担心的需大概一周时间编写的几百行代码的那个多多应用程序 。就让 多多应用程序 执行得放慢:磁盘上的归并排序可能都要一点分钟的时间,该多多应用程序 所需的时间只比读取输入和写入输出所需的时间多一点点——大概10秒钟。答案3蕴藏了对完成该任务的几种不同多多应用程序 的计时细节。

尽管机器有一点兆字节的内存,但排序功能什么都我大系统中的一帕累托图,什么都,估计到时这样1 MB的内存可用。

显而易见的土法律法律法律依据是以一般的基于磁盘的归并排序多多应用程序 为起点,就让 要对其进行调整,可能当我门都都 是对整数进行排序。曾经就也能将曾经的30行多多应用程序 减少为几十行,一起也使得多多应用程序 运行得放慢,就让 完成多多应用程序 并使之运行可能仍然都要几天的时间。

从哪此事实中也能总结出该实例研究所得到的第一有有一个结论:对小难题报告 的仔细分析有时也能得到明显的实际益处。在该实例中,几分钟的仔细研究也能大幅削减代码的长度、多多应用程序 员时间和多多应用程序 运行时间。Chuck Yeager将军(第一有有一个超音速飞行的人)赞扬一架飞机的机械系统时用的词是“行态简单、部件很少、易于维护、非常坚固”,该多多应用程序 拥有同样的属性。然而,当规范说明的一点因素趋于稳定改变时,该多多应用程序 的特殊行态将真难修改。除了都要精巧的编程以外,该实例阐明了如下一般原理。

关于本书

为哪此这样被委托人编写排序多多应用程序 呢?为哪此不必系统提供的排序功能呢?

這個 实现概要可能足以补救那个多多应用程序 员的难题报告 了。习题2、习题5和习题7描述了他会遇到的一点实现细节。

你还能不知道一点一点与记录相关的信息吗?

计算机编程有什么都方面。Fred Brooks在《人月神话》一书中为当我门都都 描绘了全景,他的文章强调了管理在大型软件项目中所起的关键作用。而Steve McConnell在《代码大全》一书中更具体地传授了良好的编程风格。这两本书所讨论的是好软件的关键因素和专业多多应用程序 员应有的行态。遗憾的是,仅仅熟练地运用哪此可靠的工程原理,不见得一定也能如期完成软件并顺利运行。

多多应用程序 设计的阶段。

输入:一有有一个最多蕴藏n个正整数的文件,每个数都小于n,其中n=107。可能在输入文件蕴藏任何整数重复出先什么都我致命错误。这样一点数据与该整数相关联。

本书描述了计算机编程更具魅力的一面:在可靠的工程之外,在洞察力和创造力范围内结晶而出的编程珠玑。正如自然界中的珍珠来自于磨砺牡蛎的细沙一样,哪此编程珠玑来自于磨砺多多应用程序 员的实际难题报告 。书中的多多应用程序 都很有趣,传授了重要的编程技巧和基本的设计原理。

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

我错就错在马上回答了這個 难题报告 。我告诉他一点有关怎样在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材,他似乎不太感冒。他更关心怎样补救這個 难题报告 ,而一定会深入学习。于是我告诉他在一本流行的多多应用程序 设计书里有磁盘排序的多多应用程序 。那个多多应用程序 有大概30行代码和十有几个函数,我估计他最多都要一周时间来实现和测试该代码。

多趟算法。哪此算法多趟读入其输入数据,每次完成一步。在1.3节可能见到了一有有一个40趟算法,习题5鼓励读者去完成一有有一个两趟算法。

等一下,既然文件这样小,并不这样在磁盘上进行排序呢?为哪此不出内存里进行排序呢?

若给定表示文件中整数集合的位图数据行态,则也能分一有有一个自然阶段来编写多多应用程序 。第一阶段将所有的位都置为0,从而将集合初始化为空。第二阶段通过读入文件中的每个整数来建立集合,将每个对应的位都置为1。第三阶段检验每一位,可能该位为1,就输出对应的整数,由此产生有序的输出文件。令n为位向量中的位数(在本例中为10 000 000),多多应用程序 也能使用伪代码表示如下:

正确的难题报告 。明确难题报告 ,这场战役就成功了90%——我很庆幸多多应用程序 员这样满足于我给出的第一有有一个多多应用程序 。一旦正确理解了难题报告 ,习题10、习题11和习题12的答案一定会很优雅。在查看提示和答案事先,请努力思考哪此难题报告 。

(回想在前言中所提到的,for i=[0, n)表示在从0至n-1的范围内对i进行迭代。)

https://www.epubit.com/bookDetails?id=UB6c87641132d8a

本书是为多多应用程序 员而写的。假如有一天书中的习题、提示、答案和深入阅读对每被委托人一定会用。本书已用作算法、多多应用程序 验证和软件工程等课程的教材。附录A中的算法分类可供实际编程人员参考,该附录一起还说明了怎样在算法和数据行态课程中使用本书。

另三种补救方案更多地利用了该排序难题报告 的特殊性。可能每个号码都使用7字节来存储,这样在可用的1 MB存储空间里共也也能存143 000个号码。可能每个号码都使用32位整数来表示话语,在1 MB存储空间里就也能存储230 000个号码。就让 ,也能使用遍历输入文件40趟的多多应用程序 来完成排序。在第一趟遍历中,将0至249 999之间的任何整数都读入内存,并对这(最多)230 000个整数进行排序,就让 写到输出文件中。第二趟遍历排序230 000至499 999之间的整数,依此类推,到第40趟遍历的事先对9 730 000至9 999 999之间的整数进行排序。对内存中的排序来说,快速排序会相当高效,就让 仅仅都要20行代码。于是,整个多多应用程序 就也能通过一两页纸的代码实现。该多多应用程序 拥有所期望的行态——并不考虑使用顶端磁盘文件;就让 ,为此所付出的代价是要读取输入文件40次。

代表集合中数值的位都置为1,一点所有的位都置为0。

位图数据行态。该数据行态描述了一有有一个有限定义域内的稠密集合,其中的每一有有一个元素最多出先一次就让 这样一点任何数据与该元素相关联。即使哪此条件这样完整版满足(同类,趋于稳定重复元素或额外的数据),也也能用有限定义域内的键作为一有有一个表项更错综复杂的表格的索引,见习题6和习题8。

阅读本书的一有有一个提示:并不读得很慢。要仔细阅读,一次读一章。要尝试解答书中提出的难题报告 ——一点难题报告 都要集中精力思考一两小时才会变得容易。就让 ,要努力解答每章末尾的习题:当读者写下答案时,从本书学到的大帕累托图知识就会跃然纸上。如有可能,要先与当我门都都 和同事讨论一下被委托人的思路,再去查阅本书末尾的提示和答案。每章末尾的“深入阅读”三种否有学术意义上的参考文献表,什么都我我推荐的一点好书,哪此书是我被委托人藏书的重要帕累托图。

都要排序的内容是哪此?文件暗蕴藏几个条记录?每条记录的格式是哪此?

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

我以为可能补救了他的难题报告 ,就让 他的踌躇使我返回到了正确的轨道上。其后一定会了下面的对话,楷体帕累托图是我的难题报告 。

由是观之,应该用位图或位向量表示集合。可用一有有一个20位长的字符串来表示一有有一个所有元素都小于20的简单的非负整数集合。同类,也能用如下字符串来表示集合{1, 2, 3, 5, 8, 13}:

输出:按升序排列的输入整数的列表。

时间—空间折中与双赢。编程文献和理论中充斥着时间—空间的折中:通过使用更多的时间,也能减少多多应用程序 所需的空间。同类,答案5中的两趟算法让多多应用程序 运行时间加倍从而使空间减半。但我的经验常常是曾经的:减少多多应用程序 的空间需求也会减少其运行时间。①空间上高效的位图行态显著地减少了排序的运行时间。空间需求的减少之什么都会因为 运行时间的减少,有一有有一个因为 :都要补救的数据变少了,因为 补救哪此数据所需的时间也变少了;一起将哪此数据保趋于稳定内存中而一定会磁盘上,进一步补救了磁盘访问的时间。当然了,这样在原始的设计远非最佳方案时,才有可能光阴里双赢。

40趟算法读入输入文件多次,写输出文件仅一次,不使用顶端文件。

在当我门都都 的实际难题报告 中,每个7位十进制整数表示一有有一个小于1 000万的整数。当我门都都 使用一有有一个具有1 000万个位的字符串来表示這個 文件,其中,当且仅当整数i在文件中趋于稳定时,第i位为1。(那个多多应用程序 员就让 找到了30万个稀疏位,习题5研究了最大存储空间严格限制为1 MB的情况。)這個 表示利用了该难题报告 的一有有一个在排序难题报告 中不常见的属性:输入数据限制在相对较小的范围内;数据这样重复;就让 对于每条记录而言,除了单一整数外,这样任何一点关联数据。