代码之家  ›  专栏  ›  技术社区  ›  Bennett McElwee

使用常量存储汇总无限序列

  •  2
  • Bennett McElwee  · 技术社区  · 17 年前

    假设我们经常对一个特定的值进行采样,并希望保留样本的统计信息。最简单的方法是存储每个样本,这样我们就可以计算我们想要的任何统计数据,但这需要无限的存储空间。使用恒定的存储量,我们可以跟踪一些统计数据,如最小值和最大值。仅使用常量存储还可以跟踪哪些内容?我想到的是百分位数、标准差和任何其他有用的统计数据。

    这是理论问题。在我的实际情况中,示例只是毫秒计时:为长时间运行的应用程序分析信息。将有数百万个样本,但不会超过十亿左右。那么,使用不超过10个变量可以为样本保留哪些统计数据呢?

    3 回复  |  直到 17 年前
        1
  •  4
  •   SPWorley    17 年前

    通常,您将存储总和而不是平均值,当您需要平均值时,您可以将总和除以计数。

    所以,在你的循环中

    maxVal=max(x, maxVal);
    minVal=min(x, minVal);
    count+=1;
    sum+=x;
    secondorder+=x*x;
    

    稍后,您可以打印任何这些统计信息。可随时计算平均值和标准偏差,其为:

    mean=sum/count;
    std=sqrt(secondorder/count - mean*mean);
    

    中位数和百分位估计更困难,但可能。通常的技巧是制作一组直方图箱,并在箱中发现样本时填充这些箱。 这只是一个例子

        2
  •  0
  •   Charlie Martin    17 年前

    嗯,很多。考虑,例如,西格玛。方差的平方根,由平均值和数据点反复计算得出。在某一点上 X ,您有截至此点的所有点的估计方差;然后加上 wikipedia