全文字数：4285个，阅读时长：约11分钟
总评
思从深而行从简
引用豆瓣的一个书评，原地址：https://book.douban.com/review/1621380/
这本书是往往是读者们有了几年开发经验后，会在某些章节与作者的想法不谋而合，会在脑海中回想起当年的种种经历，包括经过上线或者开发期间的各种bug折磨， 自己总结出来的经验才发现书中早已指出，而且说得更加深刻，更加准确，不愧是大师的作品，而且作者Jon Bentley,乔恩·本特利，著名计算机科学家，是Joshua Bloch（Effective Java）、James Gosling(Java之父)的老师，相信做过Java开发的读者们会很熟悉
打分： 5颗星（满分5颗星）
page F
1986年出版的文集，距今2020年，已有34年的历史了
page 3
怎样给一个磁盘文件排序？ 这里面其实有很多坑，需要排序的内容，文件的格式等等，下面文章中其实也给出了解答
page 4
这个文档，相信每个程序员看到都会很高兴，因为很准确，没有歧义
page 5
一般的确是前两种方法，文中的神奇排序又是？
page 6
位图精妙之处
page 7
结构简单、部件很少、易于维护、非常坚固 对小问题的仔细分析，有时可以得到明显的实际益处。 结构简单、部件很少、易于维护、非常坚固 明确问题 位图数据结构 多趟算法
page 8
不能再减少任何东西-设计的标准 设计者确定其设计已经达到了完美地标准 不是不能再增加任何东西而是不能再减少任何东西
page 9
边界检查
page 9
这些问题都很不错，可以当做面试题来面试
page 10
不能解决问题的根本原因 他企图解决错误的问题。问题的最终解决，是通过打破他的概念壁垒 进而去解决一个较简单的问题而实现的。
page 11
关键在于你需要不停的思考，来住着这灵机一动
page 11
很经典的问题，同样也是很好地面试题目
page 12
0.3ms的上升，是一个巨大的变化！ 这在《ACM通讯》发布的1958年是很重要的
page 13
二分搜索技术的皮毛应用和深层应用 求根程序 求解单变量方程式 树数据结构 程序调试
page 14
二分搜索时许多问题的解决方案
page 18
问题定义 使用那些基本操作来解决问题，即具体的技术方案
page 19
很好的问题，电话号码簿辅助程序
page 23
数据决定程序结构
page 25
为什么非要编写大程序呢？ 急于完成其最初的想法？ 受到了语言的限制，形成了概念壁垒， 数组 - 计数器动态数组
page 27
有检验的程序员的表现，占位符在模板中的作用
page 32
小程序实现的，就不要编写大程序 更一般性的问题也许更容易解决 通常拿到一个需求，是想的如何解决它，往往就是解决一个问题，但是如果上升到解决这一类问题的话，往往就会更简单
page 32
重构的一些技巧，退回起点并集中心力研究数据 使用数组重新编写重复代码 封装复杂结构
page 33
优秀的程序员会彻底理解输入、输出和中间数据结构 那就要不断的对输入、输出和中间 数据结构不断的思考，考虑哪一种结构更加适合
page 33
对于多个if语句的重构 封装方法，然后进行策略模式
page 35
小函数和软件项目，都需要理解数据和背后的数据结构
page 37
计算机编程的基本理解 问题定义 - 充分挖掘问题的各个方面，明确最终处理的是什么 算法设计 - 二分搜索、排序 数据结构 - 具有通用性
page 38
10%的展业程序员能够编程正确二分搜索的程序
page 38
二分搜索的伪代码框架，值得学习
page 39
一步一步的实现二分查找-1
page 40
一步一步的实现二分查找-2
page 44
测试用例，就是为程序员提供的一种对外表达的语言 用来表达他们对程序的理解
page 45
编写简单的代码通常是得到正确程序的关键
page 48
高效的使用程序验证技术-单元测试是基础
page 49
阐述了编程的开始到结束 深入挖掘了定义了正确的问题 通过仔细选择算法和数据结构平衡了真正的需求 （设计的更具一般性） 程序验证技术写出了优雅地伪代码（测试用例）
page 55
断言的重要性
page 57
程序上时间耗时的输出
page 57
生成即使图表的脚手架程序
page 59
脚手架可以是命令行，编码用伪代码可以管束实现；同样要记得计时
page 61
调试的趣事， 为什么作者可以登录系统？站着时就不能登录系统
page 62
如果解决一个很难复现的bug一样 为什么测试环境出现问题就很少，正式环境就会出现问题
page 63
程序员的终极目标 一个简单而又功能强大的程序 令用户欣喜而又不令开发者烦恼
page 63
研究程序的效率，有3个充足的理由
page 64
效率的一个优点是可以度量
page 71
Martin大叔快速验证得到关键参数，值得学习，在工作中快速搭建测试平台，快速估算
page 75
估算和实际运行(malloc)的区别
page 76
可以通过一些小实验来获得关键参数
page 77
按照所需强度的6倍来设计 想了想自己设计需要是按照2倍的，这里给出了更加准确的定义：安全系数来补偿自己的知识局限。
page 78
现实中你走了会有人补上，但是这个方法还是值得推荐的
page 79
用户系统的响应时间公式，简单、有效
page 79
要有规则进行简单快速尝试
page 81
费米近似，厉害了
page 81
通过估算，可以锻炼自己的批判性思维
page 82
激发起孩子们终其一生的好奇心
page 83
任何连续子向量中的最大和
page 84
伪代码写的很明确
page 86
分治算法，解决规模为n的问题，可以递归的解决两个规模近似为n/2的子问题 然后对他们的答案进行合并以得到整个问题的答案
page 86
分治算法的伪代码
page 88
线性算法，解决规模为n的问题，伪代码同样很好
page 89
合适的算法设计，可以极大地减少运行事件
page 90
几个重要的算法设计技术
page 91
反向求法，计算3-10月的销售额，可以转换为迄今10月-1和2月份的销售额
page 109
节省空间，你需要对其重要性有认识
page 109
简单性，可以衍生出功能性、健壮性以及速度和空间
page 110
简化的威力，用一个简单一些的问题替换了原始问题 税收用一个二维表表示： 一维是收入 另一维是免税额 显式地存储该表需要几千个字的内存，比机器的容量大 如果换成你，你该怎么做？
page 111
地理数据库，存储邻居，随着系统的增长，空间就不够用了 我想到的是位图，某个点有邻居，则赋值1
page 111
稀疏矩阵的例子，来解决 稀疏矩阵的解释： http://c.biancheng.net/view/3369.html
page 113
稀疏矩阵的几个通用问题
page 113
减少程序所需数据的存储空间，所使用的各种技术合集，每一条都很宝贵
page 114
数据压缩这个在传输的时候的确很有用
page 115
动态分配和垃圾回收，这些在Java和Go等高级语言中已经很常见
page 116
代码空间技术，用于节省空间 把画图程序，抽象成了解释程序来替换 从下面的数组中读取命令
page 117
解释程序、编译器和虚拟机-Java的流行，提供可移植、高效的表示 汇编语言的真正应用：内存宝贵的系统，比如数字信号处理器
page 119
使用适合任务的正确工具，前提是你得知道有哪些工具 四种节省数据空间的技术：重新计算、稀疏结构、信息理论和分配策略 三种节省代码空间的技术：函数定义、解释程序和翻译 一条最重要的原则：简单性 当内存很关键时，请务必考虑所有可能的选项
page 120
设计性能监控工具的采样数据结构，要求时间和空间效率都比较高
并且能够提供有用的输出
这里的要求常常是 体现了优秀程序员的素质
page 121
利用数据结构的对称性，使所需磁盘空间减少为原来的八分之一，巨大的节省
page 125
纸牌游戏玩家采用插入排序，来排列他们手中的纸牌
page 126
一步一步优化，需要不停的思考和分析
page 127
快速排序，利用了分治算法，1962年发布论文
page 130
qsort1是最简单的快速排序，展示了算法的很多重要属性
page 139
询问自己如何用不同的方法，来解决现有的问题
page 140
尽可能地多思考几种高层设计，不必考虑实现细节
page 142
正确理解问题，提炼出抽象问题，考虑尽可能多的解法
程序员很快发现了问题的“解决方案”， 他们只愿意花1分钟的时间思考，然后花一天的时间来写代码
而不是先花1个小时来思考，再用一个小时来写代码
page 148
事先知道集合的大小，那么选择数组，如果实现不知道集合的大小，那么链表是首选
page 151
支持快速搜索和插入的结构-二分搜索树
page 156
许多编程任务中都有用的原理
库的作用 空间的重要性 代码调优方法
page 156
这些就是集合内的常用操作，而且在日常编程中非常常用
page 158
实际搜索问题的解决
使用词缀分析，从单词中去除前后缀，缩小字典的规模
page 160
加快顺序搜索，支持快速访问，很好出错
page 161
堆的出现，解决了排序和优先级队列两个问题
易于编码且计算效率很高
page 162
二叉树是一个堆，有两个性质决定，顺序和形状
page 172
堆具有的几个特性，来保证了它的优秀
高效性 抽象性
page 172
page 173
让你设计一个锦标赛树的程序数据结构
page 179
子串搜索问题， 从这里看到了ES的设计思想，BM25 && TF IDF算法的经典之处
page 179
给定一个文本文件，查找其中最长的重复字符串，经常见的面试题目
page 180
替代散列表（求文本个数）的全新方法 - 后缀数组
page 181
后缀数组的定义：并且解决最长的重复字符串
包含了字符串的每个后缀
对其按照字母自然顺序排序
之后比较相邻元素，找出最长的重复字符串
page 187
生成随机字符串， 马尔科夫链的方式
page 187
字符串查找，应用场景是各个方面，比如如何快速地搜索整个CD-ROM?网页搜索引擎如何查找一个短语？
page 191
对程序设计做深入的思考，理解真实的需求本质
page 192
程序设计过程的10条建议
- 解决正确的问题： 需要和需求方不断地讨论和明确
- 探索所有可能的解决方案： 不仅仅是技术的方案
- 观察数据：你必须了解你的数据
- 使用粗略估算： 心里有底
- 利用对称性：
- 利用组件做设计：快速有效
- 必要时进行权衡：因为没有一个完美的方案， 需要照顾核心的需求
- 保持简单： 复杂的设计，会带来可维护性差
- 追求优美： 各种方案选择最优美的一个，前提是你想了多个方案
page 196
尽可能地复用已有的代码，尽可能地利用库函数来解决问题。当库函数不能满足需求时，需要亲自动手编写函数了
page 211
代码调优法则，Writing Efficient Programs， 27个法则
一、空间换时间法则
- 修改数据结构，减少数据上的常见运算所需要的时间，通常在数据结构中增加额外的信息，或者修改数据结构的信息使之更易访问。
- 存储预先计算好的结果
- 高速缓存
- 懒惰求值
二、时间换空间法则
- 堆积
- 解释程序
三、循环法则
- 将代码移出循环。与其在循环的每次迭代时都执行一次某种计算，不如将其移到循环体外，只计算一次
- 合并测试条件。高效的内循环应该包含尽量少的测试条件，最好只有一个。
- 循环展开。循环展开可以减少修改循环下标的开销，对于避免管道延迟、减少分支及增加指令级的并行性也很有帮助
- 删除赋值
- 循环合并
四、逻辑法则
- 利用等价的代数表达式。如果逻辑表达式的求值开销太大，就将其替换为开销较小的等价代数表达式
- 短路单调函数 3.对测试条件重新排序。在组织逻辑测试的时候，应该将低开小的、经常成功的测试放在高开销、很少成功的测试前面
- 预先计算逻辑函数。在比较小的有限域上，可以用查表来取代逻辑函数
- 消除布尔变量
五、过程法则
- 打破函数层次
- 高效处理常见情况
- 协同程序。通常，使用协同例程能够将多趟算法转换为单趟算法
- 递归函数转换
- 并行性
六、表达式法则
- 编译时初始化
- 利用等价的代数表达式
- 消除公共子表达式
- 成对计算
- 利用计算机字的并行性
page 226
如果使得程序更加健壮性以及 高效的查找某个元素是否在有序数组中
page 237
不错的伪代码实例，短小精悍
page 237
后缀序列的概念，是需要有广泛的知识面来支撑的
page 240
系统可靠的来源：设计初期就应该建立可靠性
简单的运行来检查代码 进行广泛的测试 可以在系统崩溃（一定会崩溃）时能够快速回复 仔细记录每次崩溃以便学习
page 240
提高效率之前先保证正确性，这句话是有适用场景的 那如果效率很慢呢？
page 243
算法复杂度，从n2降低到了n，这个伪代码厉害了！
扩展阅读
（完）
