《编程珠玑》学习笔记第7、8章

第七章粗略估算

1、问题引入：密西西比河一天流出多少水？

估算河出口大约1英里宽、20英尺深（即1/250英里），猜测水流速度为每小时5英里或说是每年120英里，所以密西西比河每天大约流出1*1/250*120=1/2英里³/天，误差在一个数量级之内。

2、基本技巧：

（1）两个答案比一个答案好，使用不同的方法解决问题，通过比较问题的答案对估算的结果进行检验；例如，上述问题的估算方法有三种：

a. 河流出口宽度*河流出口深度*流速

b. 流入水量 = 流域面积 * 日均降雨径流量；

c. 从某年鉴数据，密西西比河每秒的排水量得到流出水量；

以上三种方法估算结果相近，验证了结果的可靠性；

（2）快速检验，和式中各项的量纲要相同，这个量纲同时也是最终求和结果的量纲；乘积的量纲是各乘数的量纲的乘积。量纲检验检验的是等式形式，对于乘除法，可以使用计算尺时代的方法检验：分别计算第一个数位和指数。

（3）经验法则，“72法则”用于估算指数过程的增长。

（4）实践，通过多实践提高估算技巧。

3、性能估计：

（1）两百万个存储着一个整数和一个指向另一结点指针的结点是否可以装入128M内存的计算机中呢？

在16位机时代，一个指针和一个整数共占4字节；32位机中是8字节；64位机中是16字节。因此若使用32位机器，计算一个节点大小：printf(“sizeof(struct node) = %d\n”,sizeof(struct node))，输出结果显示每条记录占8个字节，那么200万个8字节结点总共使用16MB。但是由于程序中使用了molloc函数动态分配空间，每个结点就多占用了40字节空间，即每条记录就占用了48字节，这样200万条记录使用总计96MB。查看系统性能监视器，得到128M内存通常在机器上只有85M的空闲。因此实际上两百万个node是不能装入128M的计算机中的。

（2）已知某数值算法的运行时间主要取决于其N³次的开方运算，N=1000，大约需要多长时间完成10亿次的开方呢？

程序进行百万次开方的时间约0.2秒，进行千万次开方运算大约需2秒，以此类推，进行10亿次开方运算大约需200秒。实际上程序要慢很多，或许因为开方函数缓存最近的参数作为计算初始值；寄希望于用相同参数来重复调用一个函数以减少运行时间不太现实。

（3）网络速度有多快？通过ping测试来估算

4、安全系数：计算的输入决定了其输出的质量。

使用很大的安全系数来补偿知识局限。

在估算实时软件性能时，以2、4或6的系数来降低对性能的估计；

在做出可靠性/可用性保证时，给出一个比我们认为能达到差110倍的结果；

在估算规模、开销和时间进度时，给出保守2倍或4倍的结果。

5、Little定律：系统中物体的平均数量=物体离开系统的平均速率*每个物体在系统中停留的平均时间。

问题描述：夜总会容纳60人，每人逗留时间约3小时，队伍前还有20人，求排队时间。

问题求解：进入夜总会的速率为60/3=20人/小时，还需等1小时。

6、原理：任何事都应尽量简单，但不宜过于简单。——爱因斯坦

第八章算法设计的艺术

复杂深奥的算法有时可以极大地提高程序性能。

1、问题与简单算法：输入是具有N个浮点数的向量X，输出是输入向量的任何连续子向量中的最大和。

算法1：对满足0<=i<=j<n的（i，j）整数对进行迭代。程序要计算x[i…j]的总和，并检验该总和是否大于迄今为止的最大总和。运行时间是O（n³）.

算法2：x[i…j]的总和与前面已计算出的总和（x[i…j-1]）密切相关。因此无需对(i,j)每一次都进行逐一相加求和，而是保留之前的结果和再加上x[j]即可。

运行时间是O（n²）.

算法3：通过访问在外循环执行之前就已构建的数据结构的方式在内循环中计算总和。考虑到sum(i,j) = sum(0,j)-sum(0,i-1)，因此在外循环开始之前首先遍历x，求出从0到i的累积和记录入数组，然后对每一个(i,j)对做减法即可。运行时间是O（n²）。

算法4：分治算法，将原问题递归的解决近似规模位n/2的子问题，然后对问题答案进行合并以得到整个问题的答案。把数组平均分成两半，分别在左右两侧找连续子序列的最大和Sl和SR，并记录其区间a和b,则结果为a或b或跨越边界。代码如下。时间复杂度为O(nlogn)

float maxsum3(1,u)

if(1 > u)

return 0

if(1 == u)

return max(0,x[1])

m = (1 + u) / 2

lmax = sum = 0

for(i = m; i >= 1; i--)

sum += x[i]

lmax = max(lmax, sum)

rmax = sum = 0

for i = (m, u]

sum += x[i]

rmax = max(rmax, sum)

return max(lmax + rmax, maxsum3(1,m), maxsum3(m+1,u))

算法5：扫描算法，从数组的最左端开始扫描，一直到最右端为止，并记下所遇到的总和最大的子向量。假设已经解决了x[0…i-1]的问题，只要扩展到x[i]就可以了。前i个元素中，最大总和子数组要么在前i-1个元素中，要么在其结束位置i中。不从头开始计算结束位置为i的最大子向量，而是利用结束位置为i-1的最大子向量进行计算。代码如下。运行时间为O（n）。