c - 如何展示更好的平均水平？

Question

这是 Al Kelley/Ira Pohl 的《A Book On C(第三版)》第 60-61 页上的一个问题:

以下代码片段显示了计算运行平均值的两种不同方法:

int i;
double x;
double avg= sum= 0.0;
double navg;

for (i=1; scanf("%lf", &x)==1; ++i)
{
  avg+= (x-avg)/i;
  sum+= x;
  navg= sum/i;
}

书上写的原始问题是:如果你输入一些“普通”数字，avg和navg似乎是相同的。通过实验证明即使总和没有溢出，平均值也更好。

作为一名初级程序员，我的问题是:

1. “更好”算法的标准是什么？我相信精度和运行时间是两个关键因素，但是还有其他因素可以使算法“更好”吗？

2. 就精度和运行时间而言，如何通过实验证明在排除溢出的情况下，avg 仍然是比 navg 更好的方法？我是否应该使用“不寻常”的数字，例如大小相差很大的数字？

Answer 1

1. 两种算法在运行时间上没有太大区别；
2. 与navg相比，avg在精度上更好。

(1)运行时间: 下面两段代码说明，在1000000数量级上，两种算法没有太大区别。

#include<stdio.h>
#include<time.h>

int main()
{
  int i ;
  double x ,sum = 0,avg = 0;
  srand(time(NULL));
  for(i = 0; i < 1000000 ; i++)
    {
      x = rand()%10+1;
      sum += x;
    }

  avg = sum/i;
  printf("%lf\n",avg);
  printf("time use:%lf\n",(double)clock()/CLOCKS_PER_SEC);
}

#include<stdio.h>
#include<time.h>

int main()
{
  double sum = 0,avg = 0;
  double x;
  int i;
  srand(time(NULL));
  for(i = 0 ; i < 1000000; i++)
    {
      x = rand()%10+1;
      avg += (x-avg)/(i+1);
    }

  printf("%lf\n",avg);
  printf("time use:%lf\n",(double)clock()/CLOCKS_PER_SEC);
}

(2)精度: 下面的代码演示了，将 avg 与每个 x 之间的差值相加，结果为 0；而navg的结果是-2.44718e-005，这意味着avg的精度更好。

#include <stdlib.h>
#include <stdio.h>

int main()
{
  static double data[1000000];
  double sum, avg, check_value;

  int i;
  int n = sizeof(data)/sizeof(data[0]);

  avg = 0;
  for( i = 0; i < n; ++ i)
    {
      avg += ( data[i] - avg) / (i + 1);
    }

  check_value = 0;
  for( i = 0; i < n; ++ i)
    {
      check_value = check_value + ( data[i] - avg );
    }
  printf("\navg += (x[i] - avb) / i:\tavg = %g\t check_value = %g", avg, check_value );

  for( i = 0; i < n; ++ i )
    {
      data[i] = 1.3;
    }

  sum = 0;
  for( i = 0; i < n; ++ i)
    {
      sum += data[i];
    }
  avg = sum / n;

  check_value = 0;
  for( i = 0; i < n; ++ i)
    {
      check_value = check_value + ( data[i] - avg );
    }
  printf("\n avg = sum / N: \tavg = %g\t check_value = %g", avg, check_value );

  getchar();
}