预计阅读本页时间:-
基准测试
例2-7是一个计算2n的程序抽象。例子中我们要计算2851。
例2-7:耗时的计算
![阅读 ‧ 电子书库](https://book.vik.im/contents/771570957898/images/00036.jpeg)
![阅读 ‧ 电子书库](https://book.vik.im/contents/771570957898/images/00037.jpeg)
在这个抽象中,计算是与依赖的平台相互独立的。也就是说,在大多数平台下,使用Java或者C语言计算2851都会导致数据溢出。不过抽象的程序中却能够快速得到结果。依赖的结构非常抽象,对于我们不可见,这是一个优点还是缺点呢?考虑以下两个假设。
广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元
假设H1
计算2n的行为与n的值无关。
假设H2
大数(例如在之前处理的数)能够和其他的数用同样的方式进行处理,例如123 827或者997。
为了验证假设H1,我们将做50次实验,计算10 000次2n。我们抛弃最好和最坏的结果,留下48次。48次实验的平均时间如图2-8所示。
![阅读 ‧ 电子书库](https://book.vik.im/contents/771570957898/images/00038.jpeg)
求2的幂计算的性能初始很明显是线性。但是,一旦x达到30左右,出现了另外一种线性关系。由于某些原因,数是2的幂且比30大时,性能会发生改变。
为了验证假设H2,我们进行另外一个实验,首先计算出2n,然后对计算3.14159*2n的时间进行对比。我们将做50次试验,每次实验执行10 000次计算,并且抛弃最好和最坏的结果,留下48个。图2-9所示的是48次试验的平均时间(这些结果非常相似,即使我们用1.0000001代替3.14159)。
![阅读 ‧ 电子书库](https://book.vik.im/contents/771570957898/images/00039.jpeg)
为什么图2-9的点不在一条直线上?当x等于多少时这条线开始不为直线?乘法操作显得超负荷。这个操作根据乘数的不同会做不同的事情,乘数可以是浮点数、单字的整型、多字的大整数,或是这些的聚合形式。
第一个断点是在x={30,31}时,这个断点的产生很难解释。剩下的平稳状态则有传统的解释,这些改变发生在(32,64,96,128)时,这些表示的是做实验的计算机的字长(即单字长、双字长、三字长以及四字长)。随着数据需要的存储空间的增长,乘法计算的时间也不断增长。
基准操作对算法来说是非常重要的,通过计算基准操作的执行次数能够对程序的执行时间有一个很好的预测。TwoToTheN的基准操作就是乘法。