无需迭代即可为一组数值数据维护哪些统计数据？

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离开,并知道新的总和是36,而不是16关列表和他们总结了11 + 13 + 12.

所以我的问题是,除了总和和平均等明显的计算之外,还有哪些其他计算是这样的？

---

第二次编辑:作为统计数据的一个任意例子(我几乎可以肯定)确实需要迭代 - 因此不能简单地维持为总和或平均值 - 考虑我是否问过你,"这个集合中有多少个数字被min分割？" 假设数字是5,15,19,20,21,25和30.该组的最小值为5,分为5,15,20,25和30(但不是19或21),所以答案是5.现在,如果我从集合中删除5并提出相同的问题,答案现在是2,因为只有15和30可以被新的15分组整除; 但是,据我所知,如果不再通过收藏,你就无法知道这一点.

因此,我认为这是我的问题的核心:如果我们可以将各种统计数据划分为这些类别,那些可维护的(我自己的术语,可能是某个地方更官方的那些)与那些需要迭代计算任何时间的数据集合改变了,所有可维护的集合是什么？

我所询问的与在线算法并不完全相同(尽管我真诚地感谢那些向我介绍过这个概念的人).在线算法可以在没有看到所有输入数据的情况下开始工作; 我所寻求的可维护统计数据肯定会看到所有数据,只要它发生变化,它们就不需要一遍又一遍地重复.

Answer 1

首先,你想要的术语是在线算法.所有时刻(平均值,标准偏差,倾斜等)都可以在线计算.其他包括最小值和最大值.请注意,无法在线计算中位数和模式.