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

Question

我有一个生成价值的过程,我观察到了.当进程终止时,我想计算这些值的中值.

如果我必须计算均值,我可以只存储总和和生成的数量,因此有O(1)内存要求.中位数怎么样？有没有办法节省存储所有值的明显O(n)？

编辑:对2种情况感兴趣:1)流长度已知,2)它不是.

Answer 1

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

编辑:

如果流长度未知,那么显然,正如斯蒂芬在评论中所观察到的那样,那么我们别无选择,只能记住一切.如果可能存在重复项目,我们可以使用Dolphins存储值和计数的想法来节省一些内存.

Answer 2

我遇到了同样的问题，并得到了一种尚未发布在这里的方法。希望我的回答可以帮助将来的人。

如果您知道值范围并且不太关心中值精度，则可以使用常量内存逐步创建量化值的直方图。然后很容易找到中值或值的任何位置以及量化误差。

例如，假设您的数据流是图像像素值，并且您知道这些值都是 0~255 范围内的整数。要增量创建图像直方图，只需创建 256 个从 0 开始的计数器（箱），并在扫描输入时对与像素值对应的箱计数 1。创建直方图后，找到大于数据大小一半的第一个累积计数以获得中值。

对于实数数据，您仍然可以计算直方图，其中每个 bin 具有量化值（例如 10、1 或 0.1 等 bin），具体取决于您期望的数据值范围和所需的精度。

如果你不知道整个数据样本的取值范围，你仍然可以估计中位数可能的取值范围，并在这个范围内计算直方图。这本质上会丢弃异常值，但这正是我们在计算中位数时想要的。