计算大于可用内存的滑动窗口的无限流的均值和标准差

Question

考虑无限的数字流。我想计算 O(1) 内存复杂度中最新 N 个数字的流的平均值和标准偏差（因为 N 大于我拥有的内存）。最重要的是，流是分布式的，平均值和标准差也只能以分布式方式计算（不存在整个流经过的单点）。

我明白这是不可能的。但是近似解呢？

Answer 1

要计算一系列数字的平均值和标准差，您需要收集的是：

1. 值的数量 n,
2. 值的总和 sum(x)
3. 值的平方和 sum(x²)

可以轻松地在恒定空间中收集整个流的这些值。如果流被划分为子流，那么您甚至可以为每个子流独立收集它们，然后将它们添加在一起。

您的困难在于您只需要一个滑动窗口，因此您必须减去早于 N 个样本之前的所有值的总和。如果您需要更新每个样本，则需要 O(N) 内存，因为您需要记住所有要减去的总和。

但是，如果 N 非常大，那么通常不需要更新每个样本。如果您只需要每 N/1000 个样本更新一次，那么您只需要记住 N/1000 个样本中 1000 个blocks 的计数和总和，这就是常数空间。