如何在不存储列表的情况下计算或近似列表的中位数 [英] How to calculate or approximate the median of a list without storing the list

问题描述

我正在尝试计算一组值的中位数，但我不想存储所有值，因为这可能会超出内存要求.有没有一种方法可以在不存储和排序所有单个值的情况下计算或近似中值?

I'm trying to calculate the median of a set of values, but I don't want to store all the values as that could blow memory requirements. Is there a way of calculating or approximating the median without storing and sorting all the individual values?

理想情况下，我想编写如下代码

Ideally I would like to write my code a bit like the following

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

我只需要实际的 MedianCalculator 代码！

All I need is the actual MedianCalculator code!

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

Update: Some people have asked if the values I'm trying to calculate the median for have known properties. The answer is yes. One value is in 0.5 increments from about -25 to -0.5. The other is also in 0.5 increments from -120 to -60. I guess this means I can use some form of histogram for each value.

谢谢

尼克

推荐答案

如果值是离散的并且不同值的数量不是太多，您可以将每个值在直方图中出现的次数累加，然后从直方图计数中找到中位数(只需将直方图顶部和底部的计数相加，直到到达中间).或者，如果它们是连续值，您可以将它们分配到箱中 - 这不会告诉您确切的中位数，但它会给您一个范围，如果您需要更准确地了解您可以再次遍历列表，只检查中央垃圾箱中的元素.

If the values are discrete and the number of distinct values isn't too high, you could just accumulate the number of times each value occurs in a histogram, then find the median from the histogram counts (just add up counts from the top and bottom of the histogram until you reach the middle). Or if they're continuous values, you could distribute them into bins - that wouldn't tell you the exact median but it would give you a range, and if you need to know more precisely you could iterate over the list again, examining only the elements in the central bin.

这篇关于如何在不存储列表的情况下计算或近似列表的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！