计算平均次数时如何避免发生溢出的可能性? [英] how to avoid the potential of an overflow when computing an average of times?
问题描述
我正在编写一个函数,用于获取调用特定void (*)(void)
函数(又称为void -> void
函数)特定次数的时钟的平均值.
I am writing a function for getting the average of the clocks it takes to call a specific void (*)(void)
aka void -> void
function a specific number of times.
我担心,如果样本量太大,则观测值的总和将会溢出并使平均值无效.
I am worried that it if the sample size gets too large, the sum of the observations will overflow and make the average invalid.
有没有一种标准的方法来消除此类问题中总和溢出的可能性?
is there a standard approach to removing the possibility of sum overflowing in these kinds of problems?
注意:我知道这个示例过于幼稚,无法得出任何有关性能的结论.我有兴趣消除总和溢出的可能性,而不是任何性能方面的结论.
Note: I understand that this example is too naive to conclude anything about performance; I am interested eliminating the possibility of sum overflow, not concluding anything performance wise.
注2:我也理解,除非程序运行了数百年,否则64位无符号数字实际上不会溢出,但是我很好奇是否也可以消除这种假设.
Note2: I also understand that a 64 bit unsigned number will not realistically overflow unless the program is run for hundreds of years, but I am curious if it is possible to eliminate this assumption too.
这是我自包含的代码:
#include <Windows.h>
#include <stdio.h>
/**
* i want to parametrize the type which is used to store sample size
* to see whether it impacts performance
*/
template <typename sampleunit_t>
static inline ULONGLONG AveragePerformanceClocks (void (*f)(), sampleunit_t nSamples)
{
ULONGLONG sum;
sampleunit_t i;
sum = 0;
for (i = 0; i < nSamples; ++i) {
LARGE_INTEGER t1;
LARGE_INTEGER t2;
ULONGLONG dt;
QueryPerformanceCounter(&t1);
f();
QueryPerformanceCounter(&t2);
dt = t2.QuadPart - t1.QuadPart;
// sum may possibly overflow if program runs long enough with
// a large enough nSamples
sum += dt;
}
return (ULONGLONG)(sum / nSamples);
}
/* a cdecl callback that consumes time */
static void test1()
{
// don't optimize
volatile int i;
for (i = 0; i < 10000; ++i) {
}
}
int main(int argc, char **argv)
{
ULONGLONG avg;
avg = AveragePerformanceClocks<BYTE>(test1, 255);
printf("average clocks(truncated): %llu.\n", avg);
avg = AveragePerformanceClocks<WORD>(test1, 255);
printf("average clocks(truncated): %llu.\n", avg);
avg = AveragePerformanceClocks<DWORD>(test1, 255);
printf("average clocks(truncated): %llu.\n", avg);
avg = AveragePerformanceClocks<ULONGLONG>(test1, 255);
printf("average clocks(truncated): %llu.\n", avg);
system("pause");
return 0;
}
推荐答案
前n个元素的平均值为
SUM
Average = ---
n
下一个元素Mi是
(SUM + Mi)
Average2 = ----------
n + 1
因此,给定当前平均值,就可以用新的读数找到下一个平均值.
So given the current average, it is possible to find the next average with the new reading.
(Average * n + Mi )
Average2 = -------------------
n + 1
然后可以将其更改为不增加的方程式
This can then be changed to an equation which doesn't increase
n Mi
Average2 = Average * ----- + -----
n + 1 n + 1
实际上,计时的大小适合计算机的数据类型.
In practice for timing, the size of time will fit within the datatype of the computer.
如前所述,这需要使用浮点表示形式,并且虽然不会因溢出而失败,但是当n/(n+1)
小于浮点小数部分的精度时仍然会失败.
As pointed out, this needs to use a floating point representation, and whilst will not fail due to overflow, can still fail when n/(n+1)
is smaller than the accuracy of the floating point fraction part.
来自增量平均值
有一个更好的重组.
Mi - Average
Average2 = Average + -------------
n + 1
更好,因为它只有一个分区.
It is better, because it only has one division.
这篇关于计算平均次数时如何避免发生溢出的可能性?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!