Chapter-Five.md

第五章 编程小事

1. 全面评论一下本章以及本书的编程风格。解决变量名、二分搜索函数的形式和规范说明、代码的布局等方面的问题。

编写大型程序时，我为全局变量使用较长的名字（10 个或 20 个字符）。本章使用了像 x、n 和 t 这样的短变量名。在大多数软件项目中，最短的合理名称可能类似于 elem、nelems 和 target。我发现建立脚手架的时候使用短名字比较方便，在类似 4.3 节的数学证明中使用短名字也是很必要的。数学上也有类似的法则：对数学不熟悉的人可能希望听到“直角三角形斜边的平方等于两条直角边的平方和”，而处理该问题的人通常会说“a^2+b^2=c^2”。

2. 将二分搜索的伪代码描述转换成 C 语言之外的其他编程语言，并建立脚手架对你的实现进行测试和调试。所使用的语言和系统对你有哪些帮助，又有哪些妨碍？

3. 在二分搜索函数中引入错误。如何通过测试捕获这些错误？脚手架是如何帮助你找出错误的？（这个练习最好作为一个双人游戏来完成，其中攻击方引入错误，而防御方则必须追踪错误）。

搜索“mutation testing”之类的术语。

4. 重复习题 3，但是这次让二分搜索的代码保持正确而将错误引入调用二分搜索的函数中（例如忘记对数组进行排序）。

5. [R.S.Cox]一个常见的错误就是把二分搜索应用于未排序的数组，而在每次搜索前检测整个数组是否有序需要进行 n-1 次额外的比较。你能否为该函数添加部分检测程序，以显著降低检测的开销？

仅进行 O(log n) 或 O(1) 次额外的比较，如何实现？

6. 实现一个用于研究二分搜索算法的图形用户界面。为增加调试效率而付出额外的开发时间是否值得？

本书网站上提供了一个带有图形用户界面的 Java 程序，可用于研究排序算法。

7. 5.5 节的计时脚手架有一个潜在的计时错误：通过按顺序搜索每个元素，我们获得了非常有利的缓存性能。如果已知在潜在的应用中搜索是按相似的方式进行的，那么这是一个正确的程序框架（但是那样的话二分搜索恐怕并不是一个恰当的工具）。但是，如果我们希望搜索算法对数组的探测随机进行，那么我们也许还应该初始化并打乱一个排列向量，然后按随机顺序执行搜索。度量这两个版本的运行时间，看看是否存在差异。

当 n=1000 时，按照排好的顺序搜索整个数组每次需要 351 纳秒，而按随机顺序搜索会使平均开销提高到 418 纳秒（大约减慢 20%）。当 n=10^6 时，实验中甚至连二级缓存都会溢出，并且减速因子为 2.7。对于 8.3 节中高度调优过的二分搜索，有序搜索能够在 125 纳秒内搜索包含 n=1000 个元素的表，而随机搜索则需要 266 纳秒的时间，减速因子超过 2。

8. 脚手架并未被充分利用，而且很少有公开的描述。查看你所能找到的任意脚手架，失望或许会驱使你去访问本书的网站。编写脚手架来测试一个你自己编写的复杂函数。

9. 从本书的网站上下载 search.c 脚手架程序，通过实验看看二分搜索程序在你机器上的运行时间。你打算使用哪些工具来生成输入以及存储并分析输出？

脚手架以制表符作为分隔符，这种输出格式能够兼容大多数的电子表格。我通常将一系列的相关实验和它们的性能图表存储在同一页电子表格上，并在该页说明为什么做这些实验以及从中能学到什么。