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

您至少需要存储ceil(n/2)个点,因为前n/2个点中的任何一个都可能是中间值。存储点并找到中间值可能是最简单的方法。如果保存ceil(n/2)点是有价值的,那么将前n/2点读入一个排序列表(二叉树可能是最好的),然后在添加新点时抛出低点或高点,并跟踪抛出两端的点数。

编辑:

如果流的长度是未知的,那么很显然,正如斯蒂芬在评论中所观察到的,那么我们别无选择,只能记住所有的事情。如果可能出现重复项,我们可以使用存储值和计数的方法节省一点内存。

你可以

• 使用有关数字流的知识
  • 使用类似计数的方法: k 不同的值意味着存储 O(k)
  • 如果你知道你没有复制品,你可以用位图。。。但这只是一个较小的常数 O(n) .

可能吧 在计算的各个阶段,只要确定中间值不在该顶部或底部范围内,就可以丢弃顶部的“n”和底部的“n”值。
e、 假设您期望值为100000。每次你存储的数字达到12000,你就可以放弃最高的1000和最低的1000,把存储空间降回10000。

如果值的分布是相当一致的,这将很好地工作。但是,如果有可能在接近结束时收到大量非常高或非常低的值,则可能会扭曲计算。基本上,如果你放弃了一个小于(最终)中值的“高”值,或者一个等于或大于(最终)中值的“低”值,那么你的计算就被取消了。

更新

假设数据集是数字1,2,3,4,5,6,7,8,9。
经检查,中位数为5。

为了节省空间,我们放弃了最高和最低的,留下3,5,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

如果我们的数字分布均匀,我们就可以不断地修剪四肢。如果它们可能被聚成许多大的或许多小的数字,那么丢弃它们是有风险的。

如果不知道整个数据样本的取值范围,仍然可以估计出中值的可能取值范围,并在此范围内计算直方图。这在本质上降低了异常值,但这正是我们在计算中值时所需要的。