相关疑难解决方法(0)

我需要知道一组数字与一组数字相比是否超出了平均值的1 stddev等.

我正在尝试计算一组值的中位数,但我不想存储所有值,因为这可能会破坏内存需求.有没有一种计算或近似中位数的方法,而不存储和排序所有单个值？

理想情况下,我想编写我的代码,如下所示

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

我只需要实际的MedianCalculator代码!

更新:有些人问我正在尝试计算中位数的值是否具有已知属性.答案是肯定的.一个值从约-25到-0.5以0.5为增量.另一个也是从-120到-60的0.5增量.我想这意味着我可以为每个值使用某种形式的直方图.

谢谢

缺口

我需要计算大量数据的分位数.

假设我们只能通过某些部分(即大矩阵的一行)获取数据.要计算Q3分位数,需要获取数据的所有部分并将其存储在某处,然后对其进行排序并计算分位数:

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

我想找到一种获得分位数的方法,而不将数据存储在中间变量中.最好的解决方案是计算第一行中间结果的一些参数,然后逐步调整下一行.

注意:

• 这些数据集非常大(每行约5000个元素)
• 可以估计Q3,它不必是精确值.
• 我将数据部分称为"行",但它们可以有不同的长度!通常它变化不大(+/-几百个样本),但它会有所不同!

这个问题类似于"在线"(迭代器)算法,用于估计统计中位数,模式,偏度,峰度,但我需要计算分位数.

此外,本主题中的文章很少,即:

• 一种有效的近似中值选择问题算法
• 用于大规模跟踪的增量分位数估计

在尝试实现这些方法之前,我想知道是否有其他更快的方法来计算0.25/0.75分位数？

更新

仅供将来参考,我将列出我所知道的所有可以在滚动集合中维护的统计信息,在每次添加/删除时重新计算为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 …