[珠玑之椟]估算的应用与Little定律

估算的数据主要依赖于所能获得的数据和常识，有时还包括实践而不仅仅是理论。它常常作为一个大问题中的子问题，恰当地估算可以省去精确计算的时间和开销。在计算机领域，所谓常识的内容很宽泛，比如硬盘的传输速度、CPU每秒能执行多少指令、各种数据结构的大小甚至每分钟录入的单词数。有些数据是能够从各种资料中查得的，但仅仅靠记忆总难免遗漏；如果有经过学习而建立起的系统的知识结构，那便能很方便地把这些常识组织起来，除此以外，还可以靠平时经验的积累和一些面试题上的启发了。这里将进行一个收集，随时更新。

Little定律深入了估算所依赖的法则的细节：总花费等于各个部分的花费再乘以总的部分数，它在计算机系统方面的一些计算中十分有用。

---

 

计算机方面的估算问题：

1.硬盘文件读写速度的小问题：是否能超过10MB/s？（笔者某次面试中被问到的的一个关于服务器的问题的子问题）

分析：根据以往拷贝文件的经验，对于不是多个零散小文件的情况，读写速度比这个值要快得多，因此做出了肯定的答案。

 

2.确定一个空循环for(i=0;i<n;i++)在一秒钟执行的次数n，使其为CPU在1秒钟内执行总指令数目的一半（《编程之美》第一章的子问题）

分析：先把空循环化为汇编指令：

loop:
mov dx i
inc dx
mov i dx
cmp i n
jl loop

一共5条指令，假设使用的CPU是单核2.4GHz即每秒2.4G个时钟周期，（常识）现代CPU每个时钟周期执行两条以上的代码，那么一秒钟可以执行空循环(2 400 000 000 *2)/5 = 960 000 000次。

（为了提高精度而进行降低数量级的优化不再讨论）

 

3.struct node {int i; struct node *p}是否可以将这样的2 000 000个结点装入128MB内存的计算机中？（《编程珠玑》7.2性能估计）

分析：为了简化讨论，假定在32位机上int和指针都是32位的，共用了8B，直接计算的结果是只需16MB空间，而《编程珠玑》作者的128MB的计算机通常有85MB空闲，看上去是够用的。然而使用malloc()为结点分配空间时会额外占用空间（原因：malloc的机制，Linux的malloc()有一个每次分配的最小大小，小于这个值也会分配这么多；struct的对齐），这个值在作者计算机上是40B，导致了一共占用了96MB空间，事实上是不够用的。

 

4.运算的实际消耗时间：使用for(i=0;i<n;i++) fa =sqrt(10.0);计算单次sqrt()的运行时间是否准确？（《编程珠玑》7.2性能估计）

实际的单次运算时间可能慢得多，因为sqrt()可能保存了最近参数作为起始值。

（更多待补充……）

---

 

估算常用法则：

1.“72法则”：以年利率r%进行投资y年，如果r * y = 72，那么投资差不多会翻倍。

如果以t = (1+r/100)^y，并把r代换成72/y，即t = (1+72/(100y))^y,进行作图，会发现这一段t的值都在2附近，符合这条法则。

应用：假设一个指数程序解决n=40的问题需要10s，且n每增加1运行时间就增加12%，那么根据72法则，n每增加6，运行时间就加倍。进一步地，n每增加60，运行时间就为原来的1000倍(2¹⁰的近似数)。

 

2.(记忆常识)π秒是一个纳世纪。

注：一年有3.155 * 10⁷秒，而π取3.14、纳世纪为100年 * 10^-9 ，这时两者的积与这个值近似。

 

3.Little定律：队列中物体的平均数量为进入速率与平均停留时间的乘积。

注：显而易见的法则是，总开销等于每个开销乘以单元的个数；而Litte定律描述的是一个动态系统。如果想了解定律的证明，需要随机过程与排队论的相关知识。

应用：多用户系统的响应时间公式，思考时间z的n个用户登录到响应时间r的系统，每个用户周期都为用户的思考和系统响应，即z+r；作业总数为n，那么对一个时间点来看，平均负荷为n、平均响应时间为z+r，吞吐量为x（每个时间单位处理的作业数），根据Little定律，n = x*(z+r)，这样就可以求解r = n/x -z。

例1：（编程珠玑（续），7.4节）一个计算机系统，包括磁盘、处理器、操作系统和20个思考时间为20秒的终端，通过观察，它的磁盘每处理一个作业就要处理100个数据请求，而磁盘每秒钟可以处理25个请求。那么系统的吞吐量和响应时间各为多少？

解答：吞吐量直接计算，为25/100=0.25个作业/秒，响应时间r = 20/0.25 -20 = 60秒。这在流平衡下就是精确解。

例2：（编程珠玑（续），习题7.8）假设一个作业在某机器上执行时间是20秒，该机器一次可能同时执行10个作业，而你的作业是100等待执行的作业中的最后一个，作业以先进先出方式执行。大概需要等多久才能等到作业执行结束？

解答：这里要考虑两个排队系统：待执行任务队列和计算机系统本身。根据Little定律，第二个系统任务输出率X=L/R，L=10个任务，R=20秒，因此X=0.5个任务/秒。这也是第二个系统的任务到达率。因此最后一个任务会在前99个任务在198秒后完成时进入，再加上20秒的执行时间，总的时间是218秒。

 

往期回顾：

 

“珠玑之椟”系列简介与索引

位向量/位图的定义和应用