一组数字数据在不迭代的情况下可以维护哪些统计信息？

Question

更新

为了以后的参考，我将列出所有我所知道可以在一个滚动集合中维护的统计数据，并在每次添加/删除时作为O(1)操作重新计算（这实际上是我应该从一开始就用的措辞）：

显而易见的

• 计数
• 总和
• 平均值
• 最大值*
• 最小值*
• 中位数**

不太明显的

• 方差
• 标准偏差
• 偏度
• 峰度
• 模式***
• 加权平均值
• 加权移动平均值****

好的，更准确地说：这些并不是我所知道的“所有”统计数据。它们只是我现在能够脱口而出记得的。

_{*仅可对添加进行O(1)重新计算，或者如果集合已排序，则可对添加和删除进行重新计算（但在这种情况下，插入不是O(1)）。对于非排序集合，删除可能会导致O(n)的重新计算。}

_{**仅可对排序的、索引的集合进行O(1)重新计算。}

_{***需要一个相当复杂的数据结构才能以O(1)重新计算。}

_{****当权重按线性下降方式分配时，可以在添加和删除时以O(1)实现。在其他情况下，我不确定。}

---

原问题

假设我维护了一组数字数据--比如说，只是一堆数字。对于这些数据，可能会有很多计算出来的值是感兴趣的；其中一个例子就是总和。要得到所有这些数据的总和，我可以...

选项1：遍历整个集合，将所有值相加：

double sum = 0.0;
for (int i = 0; i < values.Count; i++) sum += values[i];

选项2：保持总和，消除了为查找总和而迭代集合的需求。

void Add(double value) {
    values.Add(value);
    sum += value;
}

void Remove(double value) {
    values.Remove(value);
    sum -= value;
}

编辑：为了让这个问题更容易理解，让我们将上述两个选项与一个（有点）真实的情况进行比较：

假设我开始大声列出数字，并要求你记住它们。我先说：“11、16、13、12。”如果你只记住了数字本身，然后我说：“总和是多少？”，你需要自己思考一下，“好的，11+16+13+12等于多少？”然后回答“52”。另一方面，如果在我列出数字的时候你已经在脑海中跟踪了总和 （也就是说，当我说“11”时，你想到了“11”，当我说“16”时，你想到了“27”，以此类推），你可以立即回答“52”。然后如果我说：“好的，现在忘记数字16吧”，如果你一直在脑海中跟踪总和，你可以直接从52中减去16，知道新的总和是36，而不是从列表中删除16，然后计算11 + 13 + 12。

所以我的问题是，除了明显的统计量如总和和平均值之外，还有哪些统计量是像这样的？

---

第二次编辑：作为一个需要迭代计算的（我几乎可以确定的）统计量的任意示例，考虑这样一个问题：“在此集合中有多少个数字可被最小值整除？”假设这些数字是5、15、19、20、21、25和30。这组数据的最小值是5，它可以整除5、15、20、25和30（但不能整除19或21），因此答案是5。现在如果我从集合中删除5并问同样的问题，答案现在是2，因为只有15和30可以被新的最小值15整除；但是，据我所知，你无法在不再次遍历集合的情况下知道这一点。

因此，我认为这涉及到我的问题的核心：如果我们可以将统计量分成这些类别，即那些是可维护的（可能是我的术语，也许有更正式的术语），而那些需要迭代计算以在每次更改集合时进行计算，那么所有的可维护的统计量是什么？

我所询问的并不严格等同于在线算法（虽然我真诚地感谢那些向我介绍这个概念的人）。在线算法可以在没有看到全部输入数据的情况下开始工作；而我所寻求的可维护统计数据肯定已经看到了所有数据，只是每当数据发生变化时它们不需要反复迭代。

- Dan Tao

Answer 1

首先，你想要的术语是在线算法。所有的矩（均值、标准差、偏度等）都可以在线计算。其他的包括最小值和最大值。请注意，中位数和众数无法在线计算。

- jason

---

那是非常好知道的，感谢提供链接。不过我觉得我们在谈论的可能是稍微不同的事情；在线算法看起来是指在接收数据的同时可以进行计算的算法。而我所关注的情况（或许我没有表达清楚）是指已经完全接收到所有数据的情况；但我想知道在任何时刻都可以轻松获得哪些计算值，而无需迭代处理所有数据（这些数据已经以某种方式进行了处理）。 - Dan Tao

如果您能够先处理数据，那么您可以存储任何和所有统计信息。 - tster

@tster：你正在考虑一组静态数据。某些统计信息一旦数据改变就会失效，如果要重新检索，则必须通过迭代数据来查找。作为一个微不足道的例子，考虑未排序数据的最大/最小值：一旦当前的最大值被删除，就必须再次迭代数据以找到新的最大值，最小值同理。 - Dan Tao

Answer 2

为了始终保持数据的高/低，您需要按排序顺序存储数据。有一些算法可以维护数据结构以保留排序。

如果数据已经排序，中位数就很容易计算。

如果将数据略微减少并转换为频率表，您可以维护模式。如果将数据保存为随机的、扁平的值列表，则在存在变化时无法轻松地计算模式。

- S.Lott

---

这是一个很好的建议，但有一定的权衡：如果你保持数据排序，就更难跟踪添加顺序。（你仍然可以做到这一点，但是制作例如滚动集合变得更加复杂。） - Dan Tao

@Dan：这就是关键。泛泛地说“我可以维护哪些统计信息”需要具体、详细的事务清单来支持。你没有提供这样的清单，因此它是更新事务和可以保持不变的统计摘要的随机混合。 - S.Lott

@S. Lott：我并不是想表达我对这个答案不满意。当然，对于某些统计数据来说，会有一些权衡；你提出了一个保持高/低的场景，这确实是可能的，而我（很尴尬地承认）甚至没有考虑过——可能是因为它与我目前正在处理的情况不同。这仍然是一个很好的答案。无论如何，我肯定不会幻想所有可以维护的统计数据都可以在所有情况下都可用。有条件的答案也是可以接受的。 - Dan Tao

Answer 3

这个问题的答案可能会有所帮助。关于您的需求可用性，我想说，尽管一些在线算法可用于使用部分数据估计摘要统计信息，但其他算法也可以根据您的需要从数据流中维护它们。

您还可以查看复杂事件处理（CEP），它用于跟踪和分析实时数据，例如金融或网络商务。我知道的唯一免费CEP产品是Esper。

- Ville Koskinen

Answer 4

这并不是对你问题的直接回答，但对于许多非在线统计数据，通常可以找到一些规则来通过迭代计算部分时间，并在其余时间缓存正确的值。这对你可能足够好了吗？

例如，对于高价值：

public void Add(double value) {
    values.Add(value);
    if (value > highValue)
        highValue = value;
}

public void Remove(double value) {
    values.Remove(value);
    if (value.WithinTolerance(highValue))
        highValue = RecalculateHighValueByIteration();
}

- John

---

约翰，我认为这是一个不错的方法，而且事实上我也在使用。很奇怪的是，我甚至从未真正考虑过S.Lott的想法...但正如他所说，如果列表是随机的，那么它并不适用（在这种情况下，我认为你的想法可能是最好的）。 - Dan Tao

Answer 5

正如 Jason所说 ，你确实在描述一种在线算法。我也看到过这种计算被称为累加器模式，无论循环是显式还是通过递归实现的。

- ire_and_curses

---

除了这个，他还想要一个删除操作，这就排除了像min和max这样的在线算法。 - xan

Answer 6

使用常数时间的添加和删除操作无法保持高或低，因为这将给您一个线性时间排序算法。您可以使用搜索树来维护按排序顺序排列的数据，这会给您对数时间的最小值和最大值。如果您还保留子树大小和计数，则可以轻松找到中位数。

如果您只想在添加和删除的情况下保持高或低，请查看优先队列，它们比搜索树更有效。

- JaakkoK

Answer 7

如果您事先不知道数据集的确切大小，或者它可能是无限的，或者您只是想要一些想法，那么您绝对应该研究流算法中使用的技术。

- PeterAllenWebb

Answer 8

即使在您进行第二次编辑之后，它听起来仍然像是描述在线算法，并且还要求允许“删除”操作。其中一个例子是用于在流中查找频繁项目的“草图算法”。

- Jouni K. Seppänen