粗略估算 和 Little 定律

今天在看厕所专刊(编程珠玑)的时候看到了粗略估算,有点感悟,所以写下关于粗略估算的笔记。

粗略估算

粗略估算在工程角度来说是非常重要的,对于个人的能力评估也是很重要的,粗略估算不是说和仔细的数学的计算正确结果相悖,而是在某些情况下,在得到正确的结果之前,能够给我们一个很准确的方向,例如下面这道题。

题目:从N个数中取M个最大值。N是无序的,不连续的。

当然,在做上面这道题的时候,大家都可以很容易的做出来,例如快速排序,取前M个数,用二叉排序树,后序遍历M个数,堆排序,等等,不是很复杂。当然,这个题还可以变形一下,如下。

题目:从100万个数中取最大的10个数。

好吧,我想大部分的人都会犯这样一个错误,100万?这么大,那么我怎么组织空间才能性能最好,速度最快呢?其实,这个肯定是有一定问题的,100万,不是小数目,但是我们不妨计算一下,在各个系统中占用的内存最坏是多少,我们可以大约估算一下,在16位的机器里,一个指针和一个整数大约占4个字节,32位,那么就是8字节,那么64位就是16字节。那么100万个32位的整数和指针,大约会占用8M的内存,也就是说,在现在的计算机里,就算你将100万个数全部放到内存中,也才8M,那么,最坏最坏才8M,你就可以为你的程序计算出最坏的情况,比如这个程序需要10M内存,CPUx%以及进程数n,那么最后的程序应该在这个预期之内或更好。为了追求速度,可以牺牲一点空间,可以全部读入,如果要求空间有限,那就要优化一下,只用4M或2M内存或者更少。

当然这个题目你可以进行插入排序维护M个节点,这样你可以节约很多空间,只要维护N个字节即可,但是维护节点的性能上也会有很大的损失,100万个数字要维护线性次数,也不是一个小数目,如果你内存需求不是很高,可以一次读入,也会很快。

所以估算能力也是非常重要的,例如我们项目需要写一个程序,需要算法若干,功能若干,我们可以大概的估算一下我们所需要的内存是多少,例如10M,估算一下CPU使用率,大概不会超过5%,估算一下时间,如发送一个报告或者查找一个文件需要0.1秒,发送100个报告大概需要10秒。那么整个系统自动化跑下来可能总共花20M内存,2分钟,线程2个,嗯,是不错的结果。然后在开发过程中,如果大约估算是这个估算结果以内的话,我们可以说程序达到了一个预期的目的,如果再次优化的优先级不高(因为在估算内,肯定是与客户交流过),已经是不错的程序了。当然,程序还是会有很多优化手段的,这里不再做过多的说明了,毕竟任何程序都是可以优化的。

Little定律

编程珠玑里面讲到了Little定律,我觉得是非常有必要再拿出来一说的。Little定律指出“系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积”,所以我们也可以看到这个例子,“这个地方可以容纳约60个人,每个人在这里面逗留的时间大约是3小时,所以我们可以看到进入这个地方的速率大约是每小时20人,现在前面的队伍中还有20人,所以我们估计还需要等待1个多小时”。

同样的我们可以计算一下我有100瓶矿泉水,我每天喝掉2瓶并买入2瓶,那么每瓶矿泉水保存的时间是多少天?可以估算一下100/2就是50天,平均情况下,每瓶矿泉水都可以保存50天(100=2*x=>x=50)。所以Litte法则也可以简单的说成“队列中物体的平均数量为进入速率与平与停留时间的乘积”。

在计算机系统中,这个定律也是有一定的估算作用的,例如在一个系统队列中,平均每秒处理n个数据,这个数据会在队列中停留t时间,而系统的响应时间为r,而整个系统队列中的总数为x,我们就可以得到一个简单的式子,那就是(根据Little定律得到)x=n*(t+r),即进入队列平均数量为进入的速率与平均停留时间的乘积,而这个估算是相当精确的。

所以在程序开发中,能够写出好的程序是第一步(得到正确的结果和不错的速度),第二步就是在一定的情况下的在一定的成本和需求下进行优化(如1天内速度从50秒达到10秒,虽然可以优化到5秒,但是不是非常必要的,因为10秒对客户已经足够友好)。虽然以上两点已经足够,但是在程序开发之初,我们能够通过粗略估算计算出程序的性能为10秒的话,我们可以在设计之初就能够判断我们的设计是否正确,而不是在后期去进行优化,当第一个版本的程序已经能够满足客户需求的时候,我们就不需要额外的成本再去优化以达到某种程序的性能要求了。(不过通常优化的速度越快越好:))


- - - - - - - - End Thank For Your Reading - - - - - - - -