什么是战略上的突破？
- 区分两个层次: 技艺改进带来的是技巧上的提高, 而战略上的突破来自算法或数据表达方式的改变;
- 算法例子: 快速傅立叶变换; 把比较算法复杂度从
n² 降到 n log n;
- 更普遍的情况: 战略上突破常来自数据或表的重新表达;
- 作者的检验标准: 给我看程序流程图, 我仍然会很迷惑; 给我看表数据, 往往就不再需要流程图, 程序结构非常清晰;
为什么数据的表现形式是编程的根本？
- 原因: 程序的核心是数据及其关系, 控制流程只是对数据的操作序列;
- 经验: 由于缺乏空间而绞尽脑汁的编程人员, 常常通过从自己的代码中挣脱出来, 回顾、分析实际情况、仔细思考程序的数据, 最终获得非常好的结果;
- 推论: 当性能或规模成为瓶颈时, 优先检查数据结构与表达方式, 而不是先优化语句;
有哪些重新表达数据带来突破的例子？
- IBM 650 控制台解释器: 一位年轻人发现用户交互很慢且空间昂贵, 于是编写"解释器的解释器", 使最终程序所占空间减少到不可思议的程度;
- Digitek 的 Fortran 编译器: 使用非常密集、专业化的代码来表达自己, 以至于不再需要外部存储;
- 解码代价: 对这种表达方式解码会损失一些时间, 但避免了输入-输出, 反而得到十倍的补偿;
- 来源提示: 作者与 Iverson 合著的《自动数据处理》第 6 章结尾的练习, 以及 Knuth 的练习中, 包含许多类似例子;