-4

这是Al Kelley/Ira Pohl的A Book On C(3rd Edition)第 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 似乎是相同的。通过实验证明 avg 更好，即使 sum 没有溢出。

作为初级程序员，我的问题是：

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

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

4

3 回答 3

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)precision：下面的代码演示了，加上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();
}
于 2013-07-06T08:12:43.960 回答
0

请注意，即使您执行 ++i，您也在 for() 循环中除以零

于 2013-07-06T06:19:01.900 回答
0

我认为这是一个有效的问题，尽管措辞不太好。一个问题是，即使是弗林斯提到的问题也没有很好地表达出来，并且在得到一个好的答案之前就被关闭了。

然而，这个问题本身很有趣，特别是对于封闭的问题，它表明它甚至被包含在一本书中，因此它可以引导更多人朝一个或另一个方向发展。

我认为这两种算法都不是特别好。在朴素平均中，看起来我们会失去精度，或者当对具有几个差异幅度的数字进行平均时，我们甚至会丢失数字，但同样的情况也可能会在其他算法中发现，可能只是使用不同的输入数据集。

所以，特别是因为它来自现有的书，我认为这是一个寻求一些体面答案的完全有效的问题。

我试图通过一个例子来掩盖我对这两种算法的看法。因此，假设您有 4 个大小大致相同的数字，并且您想对它们进行平均。

天真的方法是先把它们总结起来，一个接着一个。在将前两个相加之后，您显然在低端损失了一点精度（因为您现在可能有一个更大的指数）。当您添加最后一个数字时，您丢失了 2 位（这些位现在用于表示总和的高部分）。但是然后你除以四，在这种情况下基本上只是从你的指数中减去 2。

在这个过程中我们失去了什么？现在更容易回答如果所有数字先被截断 2 位会怎样。在这种情况下，结果平均值的最后两位显然将为零，并且可能会引入多达 2 位的额外错误（如果所有截断的位恰好是原始数字中的位，而不是如果它们是零）。因此，本质上，如果源是具有 23 位小数的单精度浮点数，则生成的 avg 现在将具有大约 19 位的精度。

朴素方法的实际结果更好，尽管第一个数字相加并没有失去那么多精度。

在每次迭代中的微分方法中，将适当加权的差值添加到总和中。如果这些数字具有相同的数量级，那么这种差异很可能会比某个数量级低一个数量级。然后将其除以当前计数，在此操作中没有丢失任何内容，但最后一个数字（在此示例中 i=4）的结果差异可能比源数字低约 3 个数量级。我们将此添加到与原始数字大致相同的运行平均值中。

因此，使用此示例中的微分方法添加最后一个数字似乎损失了大约 3 位精度，对于所有 4 个数字，它甚至可能看起来我们可能会下降到 5 个本质上损失的精度位 - 甚至可能比天真的更糟糕方法？

微分方法更难遵循，也许我在假设中犯了一些错误。但我认为很清楚：认为一个或另一个表现更好似乎是不正确的，或者如果是这样，也许它取决于数据的布局和大小差异。

于 2013-07-06T07:17:11.313 回答