使用最大内存效率的增量中值计算

Question

我有一个生成值的过程，我观察过。当进程终止时，我想计算这些值的中位数。

如果我必须计算平均值，我可以只存储总和和生成值的数量，从而具有O（1）内存要求。中位数呢？有没有办法保存来自存储所有值的显而易见的O（n）？

编辑：对2种情况感兴趣：1）流长已知，2）不是。

Answer 1

你将需要至少存储小区（N/2）点，因为第n/2个点的任何一个都可能是中位数。只存储点并找到中位数可能是最简单的。如果保存ceil（n/2）点是有价值的，那么在第一个n/2点读入一个排序列表（二叉树可能是最好的），然后当新点添加时，抛出低点或高点并保持追踪任何一端抛出的点数。

编辑：

如果流长度未知，那么很明显，斯蒂芬在评论中观察到的，那么我们就没有选择，只能记住一切。如果可能有重复的项目，我们可以使用Dolphins存储值和计数的想法来节省一些内存。

Answer 2

可以

• 使用统计，如果这是可以接受的 - 例如，你可以使用抽样。 k不同的值是指存储O(k)内存）
• 或折腾出已知的异常值并保持（高，低）计数器：
• 使用你的号码流
  • 使用计数有点像方法的知识。
  • 如果你知道你没有重复，你可以使用位图...但这只是一个较小的常数O(n)。

Answer 3

如果你有离散的值和大量的重复，你可以存储值和计数，这将节省一点空间。

在通过计算阶段可能你可以丢弃前“n”底“N”值，只要你相信，中位数是不是在顶部或底部范围。
例如假设您期望100,000个值。每当您存储的数字达到（比如说）12,000时，您可以丢弃最高1000和最低1000，将存储降至10,000。

如果价值的分配是相当一致的，这将工作得很好。但是，如果您有可能在结束时收到大量非常高或非常低的值，则可能会导致计算失真。基本上，如果您丢弃小于（最终）中位数的“高”值或等于或大于（最终）中位数的“低”值，则计算结果为关闭。

更新
为例位
假设数据集的数字1,2,3,4,5,6,7,8,9。
通过检查中位数是5.

比方说，你得到的前5个数字是1,3,5,7,9。
为了节省空间，我们丢弃最高和最低，剩下3,5,7
现在得到两个，2,6所以我们的存储是2,3,5,6,7
舍弃最高和最低，离开3,5,6
获得最后两个4,8，我们有3,4,5,6,8
中位数仍然是5，世界是一个很好的地方。

但是，让我们说，前五个数字，我们得到的是1,2,3,4,5
丢弃顶部和底部留下2,3,4
获得两个6,7和我们有2个， 3,4,6,7
舍弃顶部和底部离开3,4,6
获取最后两个8,9，我们有3,4,6,8,9
的中位数是6，这是不正确的。

如果我们的数字分布很好，我们可以不断修整四肢。如果他们可能被大量或大量小数目捆绑在一起，那么丢弃是有风险的。