《编程珠玑》第 6 章──程序性能分析

本章描述了后三章如何在构建计算机系统的设计层面来提高运行效率。

实例研究

设计层面 加速系数 改进
算法和数据结构 12 二叉树使得 $O\left(n^2\right)$ 的运行时间缩短为 $O\left(n\log n\right)$
算法调优 2 使用较大时间步
数据结构重组 2 产生合适树算法的簇
与系统无关的代码调优 2 使用单精度浮点数代替双精度浮点数
与系统相关的代码调优 2.5 使用汇编语言重新编写关键函数
硬件 2 使用浮点加速器
总计 400

设计层面

  1. 问题定义
  2. 系统结构
  3. 算法和数据结构
  4. 代码调优
  5. 系统软件
  6. 硬件

原理

  1. 计算机系统中最廉价、最快速且最可靠的元件是根本不存在的。
  2. 如果仅需要较小的加速,就对效果最佳的层面做改进。
  3. 如果需要较大的加速,就对多个层面做改进。

习题

1

假如现在的计算机比 Appel 做实验时所用的计算机快 1000 倍。如果使用相同的总计算时间(大约一天),对于 $O\left(n^2\right)$ 算法和 $O\left(n\log n\right)$ 算法,问题的规模 n 分别增加到多少?

前者增加到 32 倍,后者增长到 140 倍。