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

Question

假设我们经常对特定值进行采样，并希望保留有关样本的统计信息。最简单的方法是存储每个样本，这样我们就可以计算我们想要的任何统计数据，但这需要无限存储。使用恒定的存储量，我们可以跟踪一些统计数据，例如最小值和最大值。我们还可以仅使用常量存储来跟踪什么？我正在考虑百分位数、标准偏差和任何其他有用的统计数据。

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

Answer 1

最小值、最大值、平均值、总计数、方差都很简单且有用。那是5个值。通常你会存储总和而不是平均值，当你需要平均值时，你可以将总和除以计数。

所以，在你的循环中

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

稍后，您可以打印这些统计数据中的任何一个。可以随时计算平均值和标准差，它们是:

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

中位数和百分位数估计比较困难，但有可能。通常的技巧是制作一组直方图分箱，并在其中发现样本时填充分箱。然后，您可以通过查看这些 bin 总体的分布来估计中位数等。这只是分布的近似值，但通常足够了。要找到确切的中位数，您必须存储所有样本。