计算平均值时如何避免溢出的可能性？

Question

我正在编写一个函数，用于获取调用特定

void (*)(void)

又名

void -> void

函数特定次数所需的时钟平均值。

我担心如果样本量太大，观察值的总和会溢出，导致平均值无效。

是否有一种标准方法可以消除此类问题中总和溢出的可能性？

注意：我知道这个例子太天真，无法得出有关性能的任何结论；我感兴趣的是消除总和溢出的可能性，而不是得出任何性能方面的结论。

注2：我也理解64位无符号数实际上不会溢出，除非程序运行数百年，但我很好奇是否也可以消除这个假设。

这是我的独立代码：

#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;
}

Answer 1

前n个元素的平均值是

          SUM
Average = ---
           n

下一个元素Mi是

           (SUM + Mi)
Average2 = ----------
              n + 1

因此，根据当前平均值，可以使用新读数找到下一个平均值。

           (Average * n + Mi )
Average2 = -------------------
                  n + 1

然后可以将其更改为不增加的方程

                       n      Mi
Average2 = Average * ----- + -----
                     n + 1   n + 1

在计时实践中，时间的大小将适合计算机的数据类型。

正如所指出的，这需要使用浮点表示，虽然不会因溢出而失败，但当

n/(n+1)

小于浮点小数部分的精度时仍然会失败。

更新

来自增量平均

有更好的重组。

                       Mi - Average
Average2 = Average  +  -------------
                           n + 1

更好，因为它只有一个部门。

Answer 2

您可以通过添加值

sum

来减少溢出的可能性，同时确保不会丢失

dt/nSamples

。dt%nSamples

Answer 3

假设您的输入数据是：

template <typename sampleunit_t>
static inline ULONGLONG AveragePerformanceClocks (void (*f)(),
                                                  sampleunit_t nSamples)

{
    ULONGLONG delta = 0;
    ULONGLONG sum = 0;
    sampleunit_t i;    

    for (i = 0; i < nSamples; ++i) {
        LARGE_INTEGER t1; 
        LARGE_INTEGER t2;
        ULONGLONG dt;

        QueryPerformanceCounter(&t1);
        f();        
        QueryPerformanceCounter(&t2);

        dt = t2.QuadPart - t1.QuadPart;

        // Reduce the potential for overflow.
        delta += (dt%nSamples);
        sum += (dt/nSamples);
        sum += (delta/nSamples);
        delta = (delta%nSamples);
    }

    return sum;
}

20
20
20
20
20

为 100，

sum

为 20，

average

为 5。如果现在添加一个新值 30，并且我将使用 7 位整数作为值来存储

count

，那么您将遇到溢出并出现问题。

诀窍是标准化：

取新值 30，并将其除以

sum
1. 值，我们称之为

   average

   将
new_val_norm
2. 值除以

   average

   （即 1.000），然后乘以

   average

   ，我们称之为

   count

   将新值
avg_norm
3. 添加到

   new_val_norm

   值，除以

   avg_norm

   +1（我们刚刚添加了一个额外值），然后乘以

   count

   以获得新的平均值。
由于不再使用总和，溢出的风险就被推开了。

如果 avg * count (

average

) 仍然太大，您还可以选择将新值除以 avg 和 count，然后加 1。

Answer 4

以下使用估计前一次调用的平均值（第一个除外，其中选择 0，相当于惯用的平均函数）。

当然，这也不是避免溢出的万无一失的方法。

avg_norm