Chapter-Seven.md

第七章 粗略估算

1. 贝尔实验室距离狂野的密西西比河有大约 1 000 英里，而我们距离平时比较温和的帕塞伊克河只有几公里。在一星期的倾盆大雨之后，1992 年 6 月 10 日出版的 Star-Ledger 援引一位工程师的话说：“帕塞伊克河的流速为每小时 200 英里，大约是平时的 5 倍。”对此你有何评论？

即使当帕塞伊克河在新泽西州帕特森市的美丽的大瀑布处从 80 英尺的高度落下来时，其流速也达不到每小时 200 英里。我怀疑该工程师跟记者说的是：该河的流速为每天 200 英里，是每天 40 英里的常见速度的 5 倍；常见流速比较慢，不到每小时两英里。

2. 在什么距离下骑自行车的送信人使用移动存储介质传递信息的速度高于高速数据线的数据传输速度？

老式的可移动磁盘容量为 100 MB。ISDN 线每秒能传输 112 Kbit，或者说每小时能传输 50 MB。这就相当于在骑自行车的人的口袋中放一个磁盘，然后让他骑两小时或绕半径 15 英里的圆一周。为了使比较更有趣，我们将 100 张 DVD 放入骑车人的背包，这样他的带宽就变成了原来的 17 000 倍；把 ISDN 线更新为 ATM 可以使带宽变为原来的 1 400 倍，每秒能传输 155 Mbit。这样骑车的人又得到了一个系数 12，或要说需要骑一天。（写完这段文字的第二天，我发现同事的办公桌上堆着 200 张 5 GB 的一次写入唱片。在 1999 年，拥有这么多的媒体数据是很惊人的。）

3. 手动录入文字来填满一张软盘需要多长时间？

软盘的容量为 1.44 MB。我全速打字的速度约为每分钟 50 个单词（300 字节），因此可以在 4 800 分钟或 80 小时内填满一张软盘。（本书的输入文本仅有 0.5 MB，但是我却花了超过三天的时间才完成录入）。

4. 假设整个世界变慢为原来的百万分之一。你的计算机执行一条指令需要多长时间？你的磁盘旋转一周需要多长时间？磁盘臂在磁盘上搜索需要多长时间？键入自己的名字又需要多长时间？

我原本希望得到的答案是：以前只需要 10 纳秒的指令执行现在需要 1/100 秒，以前只需要 11 毫秒的磁盘旋转（5 400转/分钟）现在需要 3 小时，以前只需要 20 毫秒的磁盘臂搜索现在需要 6 个小时，以前只需要两秒钟的名字键入现在大约需要一个月。一位聪明的读者写道：“需要多长时间？如果时钟也同样变慢，则所需的时间跟以前完全一样。”

5. 证明为什么“舍九法”可以正确地检验加法。如何进一步检验“72法则”？关于这个法则你能证明些什么？

增长速率介于 5% 和 10% 之间时，“72法则”估算的误差在 1% 以内。

6. 联合国估算 1998 年的世界人口为 59 亿，年增长率为 1.33%。如果按这个速率下去，到 2050 年世界人口会是多少？

由于 72/1.33 约为 54，因此到 2052 年人口将翻倍（令人欣喜的是，联合国的估算使得人口增长率有了显著的降低）。

7. 附录 C 描述了对系统进行时间和空间开销建模的程序。阅读这些模型，并写下你对自己系统的时间和空间开销的猜测。然后从本书的网站上下载这些程序，在你的系统上运行，并将所得的估算值和你的猜测进行比较。

8. 请使用速算估计一下本书勾勒出的那些设计方案的运行时间。a. 估计一下这些程序和设计方案的时间和空间需求。b. 大 O 运行时间估算这些算法实现为程序后的运行时间。请将你的估算值与各章中的实验结果进行比较。

9. 假设系统处理一个事务需要执行 100 次磁盘访问（尽管有些系统需要的次数可能会少些，但有些系统则需要数百次的磁盘访问）。该系统在每个磁盘中每小时可以处理多少事务？

忽略由于排队而导致的减速，如果每次磁盘操作需要 20 毫秒（磁盘臂搜索时间）的话，那么处理每个事务需要 2 秒，也就是说每小时可以处理 1 800 个事务。

10. 请估计一下你所在城市的死亡率，用每年的总人口百分比来度量。

可以通过统计报纸上的死亡通告并估算本地人口来估算本地的死亡率。一种跟简单的方法是利用 Little 定律以及对平均寿命的估算。例如，如果平均寿命为 70 年，那么每年有 1/70 或 1.4% 的人口死亡。

11. [P.J.Denning]请给出 Little 定律的概要证明。

Peter Denning 对 Little 定律的证明可以分为两部分。“首先，定义 y=A/T 为到达速率，其中 A 是在长度为 T 的观察时间内到达的数目。定义 X=C/T 为输出速率，其中 C 是在长度为 T 的观察时间内的完成数。用 n(t) 表示在 [0,T] 内的时间 t 上系统中的数目。令 W 是 n(t) 下的区域（单位为“项一秒”），表示观察期间系统中所有元素的等待时间总和。每个元素完成的平均响应时间定义为 R=W/C，单位为“（项一秒）/项”。系统中的平均数是 n(t) 的平均高度，即 L=W/T，单位为“（项一秒）/秒”。现在很明显 L=RX。这个公式仅就输出速率而言。没有必要进行“流平衡”，即具有相同的输出流量（用符号表示为 y=X）。如果你添加了这个假设条件，公式就变成 L=y*R，这是排队论和系统论中遇到的公式。”

12. 一篇报纸文章称，25 美分硬币的“平均寿命是 30 年”。如何检验该论述的真伪呢？

当读到一枚 25 美分硬币的“平均寿命是 30 年”时，我觉得这个数太大了，我记得自己没看到过多少古老的硬币。因此，我把手伸进口袋，找出了 12 枚 25 美分的硬币。它们的年龄如下（以年为单位）：

3 4 5 7 9 9 12 17 17 19 20 34

平均年龄为 13 年，这和 25 美分硬币的平均寿命约为（年龄分布相当均匀情况下）寿命的两倍非常一致。如果能找到大量年龄都少于 5 年的硬币，我就可以进一步研究这个问题。然而，这次我认为这篇文章的结论是正确的。该文章还说“至少制造了 7.5 亿枚新泽西州的 25 美分硬币”，还说每 10 周就会发行一种新的 25 美分的州硬币。这乘起来就得出如下结论：每年大约发行 40 亿枚 25 美分硬币，或者说每个美国居民每年能得到 12 枚新的 25 美分硬币。每枚 25 美分硬币具有 30 年的寿命就意味着每个美国居民拥有 360 枚 25 美分硬币。这些硬币放在口袋里太多了，但是如果加上家里和汽车里的零钱，以及收银机、投币式自动售货机和银行里的硬币，那就差不多了。