【计算机科学】《编程珠玑》书摘

对实例研究的深入思考不仅很有趣，而且可以获得实际的益处。

基础

1. 程序员在节省空间方面无计可施时，将自己从代码中解脱出来，退回起点并集中心力研究数据，常常能有奇效。数据的表示形式就是程序设计的根本。
2. 退回起点思考的原则
   • 使用数组重新编写重复代码；
   • 封装复杂结构；
   • 尽可能使用高级工具；
   • 从数据得出程序的结构。

性能

程序员的终极目标：简单而又功能强大，令用户欣喜而又不令开发者烦恼

1. 计算机系统中最廉价、最快速且最可靠的元件是根本不存在的。如果需要较小的加速，就对效果最佳的层面做改进；如果需要较大的加速，就对多个层面做改进。
2. 粗略估算的基本技巧：两个答案比一个答案好、快速检验、经验法则、实践。
3. 算法设计技术
   • 保存状态，避免重复设计；
   • 将信息预处理至数据结构中；
   • 分治算法；
   • 扫描算法；
   • 累加数组；
   • 下界。
4. 代码调优的最重要原理就是尽量少用它。
5. 数据空间技术：重新计算、稀疏结构、数据压缩、分配策略、垃圾回收，代码空间技术：函数定义、解释程序、翻译成机器语言。

应用

1. 作者对程序员的10条建议
   1. 解决正确的问题；
   2. 探索所有可能的解决方案；
   3. 观察数据；
   4. 使用粗略估算；
   5. 利用对称性；
   6. 利用组件做设计；
   7. 建立原型；
   8. 必要时进行权衡；
   9. 保持简单；
   10. 追求优美。
2. 代码调优法则：
   • 空间换时间法则
     • 修改数据结构
     • 存储预先计算好的结果
     • 高速缓存
     • 懒惰求值
   • 时间换空间法则
     • 堆积
     • 解释程序
   • 循环法则
     • 将代码移出循环
     • 合并测试条件
     • 循环展开
     • 删除赋值
     • 消除无条件分支
     • 循环合并
   • 逻辑法则
     • 利用等价代数表达式
     • 短路单调函数
     • 对测试条件重新排序
     • 预先计算逻辑函数
     • 消除布尔变量
   • 过程法则
     • 打破函数层次
     • 高效处理常见情况
     • 协同程序
     • 递归函数转换
     • 并行性
   • 表达式法则
     • 编译时初始化
     • 利用等价代数表达式
     • 消除公共子表达式
     • 成对计算
     • 利用计算机字的并行性