我想计算一组值的中位数，但我不想存储所有值，因为那可能会使内存要求过高。有没有一种方法可以在不存储和排序所有单个值的情况下计算或近似中位数？
理想情况下，我希望编写的代码类似于以下内容
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为增量递增。另一个值也以0.5为增量从-120到-60递增。我想这意味着我可以使用某种直方图来处理每个值。
谢谢
Nick
如果值是离散的并且不同值的数量不太高，您可以仅累积每个值出现的次数以生成直方图，然后从直方图计数中找到中位数（只需从直方图顶部和底部累加计数，直到到达中间即可）。或者如果它们是连续值，您可以将它们分布到桶中-这不会告诉您确切的中位数，但它会给您一个范围，如果您需要更精确地知道，您可以再次遍历列表，仅检查中心桶中的元素。
这里介绍一种名为“remedian（中位数滑动窗口）”的统计方法。它通过首先设置k个长度为b的数组来工作。将数据值输入第一个数组，当该数组已满时，计算并存储其中位数于下一个数组的第一个位置，然后重新使用第一个数组。当第二个数组也已满时，将其值的中位数存储在第三个数组的第一个位置上，以此类推。您明白了吧 :)
这个方法简单而且相当健壮。您可以查看参考文献...
http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/Remedian.pdf
希望这有所帮助
迈克尔
我使用这些增量/递归平均值和中位数估算器，两者都使用恒定的存储空间：
mean += eta * (sample - mean)
median += eta * sgn(sample - median)
其中eta是一个小的学习率参数（例如0.001），sgn()是符号函数，返回{-1, 0, 1}中的一个。（如果数据非平稳且要跟踪时间内的变化，请使用常量eta；否则，对于平稳源，可以使用像eta=1/n这样的东西作为均值估计器，其中n是迄今为止看到的样本数... 不幸的是，这似乎不能用于中位数估计器。）
这种增量均值估计器似乎在很多地方都被使用，比如无监督神经网络学习规则，但中位数版本似乎要少得多，尽管它具有优点（对离群值的鲁棒性）。这意味着中位数版本可以在许多应用程序中替代均值估计器。
此外，我修改了增量中位数估计器以估计任意分位数。一般来说，分位数函数告诉您将数据分成两个部分的值：p和1-p。以下逐步估计该值：
quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)
变量p的值应该在[0,1]之间。这本质上将sgn()函数的对称输出{-1、0、1}偏向一侧，将数据样本分成两个不同大小的箱子（数据中小于/大于分位数估计的比例分别为p和1-p）。请注意，当p=0.5时，这就简化成了中位数估计。
我很想看到一个类似形式的增量模式估计器...
（注：我也在这里发布了一个类似的话题：“用于估算统计中位数、模式、偏度、峰度的“在线”（迭代器）算法？”）
这里有一种疯狂的方法，也许你可以尝试一下。这是流算法中的一个经典问题。规则如下：
O(log n)，其中 n 是你想要的项目数找到中位数的思路很简单。从列表中随机采样 O(1 / a^2 * log(1 / p)) * log(n) 个元素，你可以通过蓄水池抽样（见之前的问题）来做到这一点。现在，只需使用经典方法从采样的元素中返回中位数即可。
保证返回的项的索引将以至少为 1-p 的概率为 (1 +/- a) / 2。因此有可能失败，你可以通过采样更多的元素来选择它。它不会返回中位数，也不能保证返回的项的值接近于中位数，只是当你对列表进行排序时，返回的项将接近列表的一半。
该算法使用额外的 O(log n) 空间，并且在线性时间内运行。
a 和 p 分别代表什么？另外，你提供的链接现在已经失效了。 - user7364588对于近似中位数的计算，David的建议似乎是最明智的方法。
同样问题的运行平均数要容易计算得多：
Mn = Mn-1 + ((Vn - Mn-1) / n)
其中Mn是n个值的平均值，Mn-1是前一个平均值，而Vn是新值。
换句话说，新平均值等于现有平均值加上新值与平均值之间的差异，再除以值的数量。
在代码中，这看起来可能是这样的：
new_mean = prev_mean + ((value - prev_mean) / count)
我认为在没有将列表导入内存的情况下无法做到。如果您知道数据是对称分布的，可以使用平均值进行近似计算，或者计算一小部分数据的适当中位数（适合内存），如果您知道样本中具有相同分布的数据（例如，第一个元素与最后一个元素具有相同的分布）。
我学习了迭代分位数计算的思路。在选择起始点和eta值时非常重要，这些值可以来自均值和标准差。因此，我编写了以下代码：
Function QuantileIterative(Var x : Array of Double; n : Integer; p, mean, sigma : Double) : Double;
Var eta, quantile,q1, dq : Double;
i : Integer;
Begin
quantile:= mean + 1.25*sigma*(p-0.5);
q1:=quantile;
eta:=0.2*sigma/xy(1+n,0.75); // should not be too large! sets accuracy
For i:=1 to n Do
quantile := quantile + eta * (signum_smooth(x[i] - quantile,eta) + 2*p - 1);
dq:=abs(q1-quantile);
If dq>eta
then Begin
If dq<3*eta then eta:=eta/4;
For i:=1 to n Do
quantile := quantile + eta * (signum_smooth(x[i] - quantile,eta) + 2*p - 1);
end;
QuantileIterative:=quantile
end;
由于两个元素的中位数是均值，所以我使用了平滑符号函数，而xy() 是 x^y。有没有更好的想法？当然，如果我们有一些先验知识，我们可以使用数组的最小值和最大值，偏度等添加代码。对于大数据，您可能不会使用数组，但对于测试来说，这样更容易。