K-Best 测量方法

hanzhi09

在检测程序运行时间这个复杂问题上，可以采用 Randal E.Bryant 和 David R. O’Hallaron 提出的 K 次最优测量方法。假设重复的执行一个程序，并纪录 K 次最快的时间，如果发现测量的误差  很小，那么用测量的最快值表示过程的真正执行时间，称这种方法为“ K 次最优（K-Best）方法”，要求设置三个参数：
K: 要求在某个接近最快值范围内的测量值数量。
: 测量值必须多大程度的接近，即测量值按照升序标号 V1, V2, V3, … , Vi, … ，同时必须满足（1+）Vi  Vk
M: 在结束测试之前，测量值的最大数量。
按照升序的方式维护一个 K 个最快时间的数组，对于每一个新的测量值，如果比当前 K 处的值更快，则用最新的值替换数组中的元素 K ，然后再进行升序排序，持续不断的进行该过程，并满足误差标准，此时就称测量值已经收敛。如果 M 次后，不能满足误差标准，则称为不能收敛。
在接下来的所有试验中，采用 K=10，=2%，M=200 来获取程序运行时间，同时也对 K 次最优测量方法进行了改进，不是采用最小值来表示程序执行的时间，而是采用 K 次测量值的平均值来表示程序的真正运行时间。由于采用的误差 比较大，在所有试验程序的时间收集过程中，均能收敛，但也能说明问题。
为了可移植性，采用 gettimeofday() 来获取系统时钟（system clock）时间，可以精确到微秒。


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/106856/showart_2125369.html