没有合适的资源?快使用搜索试试~ 我知道了~
《编程珠玑》笔记(一切资源私聊免费发送)
需积分: 10 0 下载量 111 浏览量
2020-10-07
11:07:15
上传
评论
收藏 1.12MB PDF 举报
温馨提示
本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值
资源推荐
资源详情
资源评论
2019/7/8 把《编程珠玑》读薄 - Hawstein 的博客
hawstein.com/2013/08/11/make-thiner-programming-pearls/ 1/26
Reading (/archive/?tag=Reading)
把
《编程珠玑
》读薄 Hawstein | August 11,
2013
目录
1. 开篇
2. 啊哈!算法
3. 数据决定程序结构
4. 编写正确的程序
5. 编程中的次要问题
6. 程序性能分析
7. 粗略估算
8. 算法设计技术
9. 代码调优
10. 节省空间
11. 排序
12. 取样问题
13. 搜索
14. 堆
15. 字符串
开篇
具体化你的解决的问题。下面是A和B的对话。
2019/7/8 把《编程珠玑》读薄 - Hawstein 的博客
hawstein.com/2013/08/11/make-thiner-programming-pearls/ 2/26
1
2
3
4
5
6
7
8
A:我该如何对磁盘文件进行排序?
B:需要排序的内容是什么?文件中有多少条记录?每个记录的格式是什么?
A:该文件包含至多10,000,000个记录,每条记录都是一个7位整数。
B:如果文件那么小,为什么要使用磁盘排序呢?为什么不在主存中对它排序?
A:该功能是某大型系统中的一部分,大概只能提供1MB主存给它。
B:你能将记录方面的内容说得更详细一些吗?
A:每个记录是一个7位正整数,没有其它的关联数据,每个整数至多只能出现一次。
... ...
经过一系统的问题,我们可以将一个定义模糊不清的问题变得具体而清晰:
1
2
3
4
5
6
7
8
9
输入:
所输入的是一个文件,至多包含n个正整数,每个正整数都要小于n,这里n=10^7。
如果输入时某一个整数出现了两次,就会产生一个致命的错误。
这些整数与其它任何数据都不关联。
输出:
以增序形式输出经过排序的整数列表。
约束:
大概有1MB的可用主存,但可用磁盘空间充足。运行时间至多允许几分钟,
10秒钟是最适宜的运行时间。
如果主存容量不是严苛地限制在1MB,比如说可以是1MB多,或是1~2MB之间, 那么我们就可以
一次性将所有数据都加载到主存中,用Bitmap来做。 10,000,000个数就需要10,000,000位,也就
是10,000,000b = 1.25MB。
程序可分为三个部分:第一,初始化所有的位为0;第二,读取文件中每个整数, 如果该整数对应
的位已经为1,说明前面已经出现过这个整数,抛出异常,退出程序 (输入要求每个整数都只能出
现一次)。否则,将相应的位置1;第三, 检查每个位,如果某个位是1,就写出相应的整数,从而
创建已排序的输出文件。
如果主存容量严苛地限制在1MB,而使用Bitmap需要1.25MB, 因此无法一次载入完成排序。那
么,我们可以将该文件分割成两个文件, 再分别用Bitmap处理。分割策略可以简单地把前一半的
数据放到一个文件, 后一半的数据放到另一个文件,分别排序后再做归并。 也可以把文件中小于
某个数(比如5,000,000)的整数放到一个文件,叫less.txt, 把其余的整数放到另一个文件,叫
greater.txt。分别排序后, 把greater.txt的排序结果追加到less.txt的排序结果即可。
啊哈!算法
第2章围绕3个问题展开。
2019/7/8 把《编程珠玑》读薄 - Hawstein 的博客
hawstein.com/2013/08/11/make-thiner-programming-pearls/ 3/26
给定一个包含32位整数的顺序文件,它至多只能包含40亿个这样的整数, 并且整数的次序
是随机的。请查找一个此文件中不存在的32位整数。 在有足够主存的情况下,你会如何解决
这个问题? 如果你可以使用若干外部临时文件,但可用主存却只有上百字节, 你会如何解
决这个问题?
这是CTCI中的一道题目,详细解答请戳以下链接:
请猛戳我 (/posts/12.3.html)
请将一个具有n个元素的一维向量向左旋转i个位置。例如,假设n=8,i=3, 那么向量
abcdefgh旋转之后得到向量defghabc。
这个问题很常见了,做3次翻转即可,无需额外空间:
1
2
3
reverse(0, i-1); // cbadefgh
reverse(i, n-1); // cbahgfed
reverse(0, n-1); // defghabc
给定一本英语单词词典,请找出所有的变位词集。例如,因为“pots”, “stop”,“tops”相互之
间都是由另一个词的各个字母改变序列而构成的, 因此这些词相互之间就是变位词。
这个问题可以分3步来解决。第一步将每个单词按字典序排序, 做为原单词的签名,这样一来,变
位词就会具有相同的签名。 第二步对所有的单词按照其签名进行排序,这样一来,变位词就会聚
集到一起。 第三步将变位词分组,形成变位词集。示意图如下:
数据决定程序结构
恰当的数据视图实际上决定了程序的结构。 我们常常可以通过重新组织内部数据来使程序变得小
而美。
2019/7/8 把《编程珠玑》读薄 - Hawstein 的博客
hawstein.com/2013/08/11/make-thiner-programming-pearls/ 4/26
发明家悖论:更一般性的问题也许更容易解决。(有时候吧)
程序员在节省空间方面无计可施时,将自己从代码中解脱出来, 退回起点并集中心力研究数据,
常常能有奇效。数据的表示形式是程序设计的根本。
下面是退回起点进行思考时的几条原则:
使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构—— 数组来更
好地表述。
封装复杂结构。当需要非常复杂的数据结构时,使用抽象术语进行定义, 并将操作表示为
类。
尽可能使用高级工具。超文本,名字-值对,电子表格,数据库, 编程语言等都是特定问题
领域中的强大的工具。
从数据得出程序的结构。在动手编写代码之前,优秀的程序员会彻底理解输入, 输出和中间
数据结构,并围绕这些结构创建程序。
提到的书籍:Polya的《How to Solve it》,中文书《怎样解题》; Kernighan和Plauger的
《Elements of Programming Style》;Fred Brooks的《人月神话》 Steve McConnell的《代码大
全》;《Rapid Development》; 《Software Project Survival Guide》
编写正确的程序
本章以二分搜索为例子,讲述了如何对程序进行验证及正确性分析。
深入阅读:David Gries的《Science of Programming》 是程序验证领域里极佳的一本入门书籍。
编程中的次要问题
到目前为止,你已经做了一切该做的事:通过深入挖掘定义了正确的问题, 通过仔细选择算法和
数据结构平衡了真正的需求,通过程序验证技术写出了优雅的代码, 并且对其正确性相当有把
握。万事俱备,只欠编程。
使用断言assert
自动化测试程序
剩余25页未读,继续阅读
资源评论
Brucechows
- 粉丝: 55
- 资源: 36
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功