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

  • 时间:
  • 浏览:3
  • 来源:uu快3官方邀请码_uu快3app赚钱_彩神8

时间—空间折中与双赢。编程文献和理论中充斥着时间—空间的折中:通过使用更多的时间,都还里能 都都还里能 减少系统进程所需的空间。类似于,答案5中的两趟算法让系统进程运行时间加倍从而使空间减半。但我的经验常常是从前的:减少系统进程的空间需求也会减少其运行时间。①空间上高效的位图形状显著地减少了排序的运行时间。空间需求的减少未必会意味运行时间的减少,有有一另另一一两个意味:时需防止的数据变少了,意味防止哪些数据所需的时间也变少了;同时将哪些数据保存在内存中而都会磁盘上,进一步防止了磁盘访问的时间。当然了,都还里能 都都还里能 在原始的设计远非最佳方案时,才有或者时光英文英文双赢。

那个系统进程员打电话把他的问提他不知道,或者亲们儿花了最少一刻钟时间明确了问提所在,并找到了位图防止方案。他花了几小时来实现这人 几十行代码的系统进程。该系统进程远远优于亲们儿在电话开始英语 英语 时所担心的需最少一周时间编写的几百行代码的那个系统进程。或者系统进程执行得更快:磁盘上的归并排序或者时需有些分钟的时间,该系统进程所需的时间只比读取输入和写入输出所需的时间多有些点——最少10秒钟。答案3带有了对完成该任务的几种不同系统进程的计时细节。

阅读本书的有一另另一一两个提示:未必读得太快了 了 。要仔细阅读,一次读一章。要尝试解答书中提出的问提——有些问提时需集中精力思考一两小时才会变得容易。或者,要努力解答每章末尾的习题:当读者写下答案时,从本书学到的大每项知识就会跃然纸上。如有或者,要先与亲们和同事讨论一下另一方的思路,再去查阅本书末尾的提示和答案。每章末尾的“深入阅读”未必有无学术意义上的参考文献表,也不我推荐的有些好书,哪些书是我另一方藏书的重要每项。

下图所示的方案更可取。亲们儿结合上述五种办法 的优点,读输入文件仅一次,且不使用上面文件。

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

都还里能 都都还里能 在输入文件中的所有整数都都还里能 都都还里能 在可用的1 MB内存中表示的以前才都都都还里能 实现该方案。于是问提就归结为有无都都都还里能 用最少30万个可用位来表示最多1 000万个互异的整数。考虑五种最少的表示办法 。

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

关于本书

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

你还能他不知道有些有些与记录相关的信息吗?

显而易见的办法 是以一般的基于磁盘的归并排序系统进程为起点,或者要对其进行调整,或者亲们儿是对整数进行排序。从前就都还里能 都都还里能 将从前的30行系统进程减少为几十行,同时也使得系统进程运行得更快,或者完成系统进程并使之运行或者仍然时需几天的时间。

- END -

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

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

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

每条记录都会7位的正整数,再无有些相关数据。每个整数最多只再次出显一次。

简单的设计。Antoine de Saint-Exupéry是法国作家兼飞机设计师,他从前说过:“设计者确定其设计或者达到了完美的标准都会都还里能 再增加任何东西,也不都还里能 再减少任何东西。”更多的系统进程员应该使用该标准来检验另一方完成的系统进程。简单的系统进程通常比具有相同功能的简化的系统进程更可靠、更安全、更健壮、更高效,或者易于实现和维护。

请花上一分钟思考一下该问提的规范说明。现在你打算给系统进程员哪些样的建议呢?

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

系统进程设计的阶段。

我以为或者防止了他的问提,或者他的踌躇使我返回到了正确的轨道上。其后都会了下面的对话,楷体每项是我的问提。

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

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

为哪些都还里能 都都还里能 另一方编写排序系统进程呢?为哪些不不系统提供的排序功能呢?

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

阅读本书所需的唯一背景知识也不五种高级语言的编程经验。书中偶尔会再次出显有些高级技术(如C++中的模板等),对此不不太熟悉的读者都还里能 都都还里能 跳过哪些内容,基本上不影响阅读。

本书是为系统进程员而写的。假如书中的习题、提示、答案和深入阅读对每另一方都会用。本书已用作算法、系统进程验证和软件工程等课程的教材。附录A中的算法分类可供实际编程人员参考,该附录同时还说明了何如在算法和数据形状课程中使用本书。

位图数据形状。该数据形状描述了有一另另一一两个有限定义域内的稠密集合,其中的每有一另另一一两个元素最多再次出显一次或者太难 有些任何数据与该元素相关联。即使哪些条件太难 详细满足(类似于,存在重复元素或额外的数据),也都还里能 都都还里能 用有限定义域内的键作为有一另另一一两个表项更简化的表格的索引,见习题6和习题8。

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

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

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

本书每一章都独立成篇,各章之间却又有着逻辑分组。第1章至第5章构成本书的第一每项,这每项回顾了编程的基本原理:问提定义、算法、数据形状以及系统进程验证和测试。第二每项围绕速度这人 主题展开。速度问提有时五种很糙要,又永远都会进入有趣编程问提的绝佳跳板。第三每项用哪些技术来防止排序、搜索和字符串等重要问提。

这位系统进程员正在开发类似于数据库的防止系统的一小每项,时需排序的整数也不免费电话号码。输入文件是电话号码的列表(已删除所有有些信息),号码重复再次出显算出错。期望的输出文件是以升序排列的电话号码列表。应用背景同时定义了相应的性能需求。当与系统的会话时间较长时,用户最少每小时请求一次有序文件,或者在排序未完成以前哪些都干不了。或者,排序最多只允许执行几分钟,10秒钟是比较理想的运行时间。

文件最多带有30万条记录,每条记录都会7位的整数。

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

尽管机器有有些兆字节的内存,但排序功能也不大系统中的一每项,好多好多 有,估计到时都还里能 都都还里能 1 MB的内存可用。

一位系统进程员曾问我有一另另一一两个很简单的问提:“何如给有一另另一一两个磁盘文件排序?”想当年我是一上来就犯了错误,现在,在讲这人 故事以前,先给亲们儿有一另另一一两个或者,看看都还里能 都都还里能 比我当年做得更好。你都还里能 都都还里能 何如回答上述问提呢?

归并排序读入输入文件一次,或者在工作文件的帮助下完成排序并写入输出文件一次。工作文件时需多次读写。

另五种防止方案更多地利用了该排序问提的特殊性。或者每个号码都使用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次。

我时需在有一另另一一两个大系统中排序。或者不明的技术意味,我都还里能 使用系统中的文件排序系统进程。

输入:有一另另一一两个最多带有n个正整数的文件,每个数都小于n,其中n=107。或者在输入文件带有任何整数重复再次出显也不致命错误。太难 有些数据与该整数相关联。

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

这人 实现概要或者足以防止那个系统进程员的问提了。习题2、习题5和习题7描述了他会遇到的有些实现细节。

等一下,既然文件太难 小,未必都还里能 都都还里能 在磁盘上进行排序呢?为哪些不在 内存里进行排序呢?

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

对系统进程员来说,哪些需求加起来也不:“何如给磁盘文件排序?”在试图防止这人 问提以前,先将已知条件组织成五种更客观、更易用的形式。

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

这番对话让问提更明确了。在美国,电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号30(当时都还里能 都都还里能 这有一另另一一两个号码)的电话是不收费的。实际的免费电话号码数据库带有絮状的信息:免费电话号码、呼叫实际中转到的号码(有时是有几个号码,这时时需有些规则来决定哪些呼叫在哪些时间中转到哪里)、主叫用户的姓名和地址等。

时需排序的内容是哪些?文件暗带有几个条记录?每条记录的格式是哪些?

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

正确的问提。明确问提,这场战役就成功了90%——我很庆幸系统进程员太难 满足于我给出的第有一另另一一两个系统进程。一旦正确理解了问提,习题10、习题11和习题12的答案都会很优雅。在查看提示和答案以前,请努力思考哪些问提。

我错就错在马上回答了这人 问提。我告诉他有些有关何如在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材,他似乎不太感冒。他更关心何如防止这人 问提,而都会深入学习。于是我告诉他在一本流行的系统进程设计书里有磁盘排序的系统进程。那个系统进程有最少30行代码和十有几个函数,我估计他最多时需一周时间来实现和测试该代码。

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

在亲们儿的实际问提中,每个7位十进制整数表示有一另另一一两个小于1 000万的整数。亲们儿使用有一另另一一两个具有1 000万个位的字符串来表示这人 文件,其中,当且仅当整数i在文件中存在时,第i位为1。(那个系统进程员后后找到了30万个稀疏位,习题5研究了最大存储空间严格限制为1 MB的清况 。)这人 表示利用了该问提的有一另另一一两个在排序问提中不常见的属性:输入数据限制在相对较小的范围内;数据太难 重复;或者对于每条记录而言,除了单一整数外,太难 任何有些关联数据。