algorithm - 具有最大内存效率的增量中值计算

Question

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

如果我必须计算平均值，我可以只存储总和和生成值的数量，因此需要 O(1) 内存。中位数呢？有没有办法节省来自存储所有值的明显 O(n) ？

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

Answer 1

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

编辑：

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

Answer 2

你可以

• 如果可以接受，请使用统计数据 - 例如，您可以使用抽样。
• 使用有关您的号码流的知识
  • 使用类似计数排序的方法：k不同的值意味着存储O(k)内存）
  • 或丢弃已知的异常值并保留一个（高，低）计数器。
  • 如果您知道没有重复项，则可以使用位图……但这只是O(n).

Answer 3

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

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

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

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

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

Answer 4

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

可能在计算的各个阶段，只要您确定中位数不在该顶部或底部范围内，您就可以丢弃顶部的“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，这是不正确的。

如果我们的人数分布良好，我们可以继续修剪四肢。如果它们可能以大量或大量的小数量聚集在一起，那么丢弃是有风险的。