我见过这个问题的更广泛版本，其中个人正在寻找多个汇总统计数据，但我还没有看到提出的解决方案。我只对 Python 中的中位数感兴趣。
假设我在循环中生成一百万个值。由于内存问题，我无法将百万个值保存到列表中并在完成后计算中位数。我可以一边计算中位数吗？对于平均值，我只是逐步对值求和，完成后除以一百万。对于中位数来说，答案似乎并不那么直观。
我陷入了“思想实验”部分，所以我无法真正尝试任何我认为可能有效的东西。我不确定这是否是一个已经实现的算法，但我找不到它是否已经实现。
除非你的“价值观”观念以某种可利用的方式受到限制，否则这是不可能的；和/或您可以对数据进行多次传递；和/或您也愿意在磁盘上存储内容。假设你知道有 5 个值，都是不同的整数，并且你知道前 3 个值是 5、6、7。中位数将是其中之一，但此时你不知道是哪一个，所以你必须记住他们全部。如果接下来是 1 和 2，则中位数为 5；如果接下来是 4 和 8，则为 6；如果接下来是 8 和 9，则为 7。
这显然可以推广到任何奇数个值range(i, i + 2*N+1)，当您看到第一个N+1值时：中位数可以是第一个值中的任何一个N+1，因此除非值的性质有可利用的内容，否则您必须记住那时的所有人。
一个可利用的例子：您知道最多有 100 个不同的值。然后，您可以使用字典来计算每个出现的数量，并根据分布的压缩表示轻松计算最后的中位数。
由于已经提到的原因，这里一般没有“捷径”。但我将附上合理的一次性近似方法的 Python 代码，如“补救措施：大型数据集的鲁棒平均方法”中详细介绍的。该论文还指出了其他近似方法。
关键：选择一个大于1的奇数。B然后将连续的元素存储在缓冲区中，直到B它们被记录为止。那时，这些中值前进到下一个级别，并且缓冲区被清除。它们的中位数仍然是这些元素保留的唯一记忆B。
同样的模式也在更深层次上继续：在记录了B这些中位数的中位数之后，这些中位数前进到下一个级别，并且第二级缓冲区被清除。然后，先进的中位数仍然是进入其中的元素的唯一记忆。BB**2
等等。在最坏的情况下，它可能需要存储B * log(N, B)值，其中N是元素的总数。在 Python 中，很容易对其进行编码，因此可以根据需要创建缓冲区，因此N不需要提前知道。
如果B >= N，该方法是精确的，但您还存储了每个元素。如果B < N，它是中位数的近似值。有关详细信息，请参阅论文 - 它非常复杂。这是一个看起来非常好的案例;-)
>>> import random
>>> xs = [random.random() for i in range(1000001)]
>>> sorted(xs)[500000] # true median
0.5006315438367565
>>> w = MedianEst(11)
>>> for x in xs:
... w.add(x)
>>> w.get()
0.5008443883489089
也许令人惊讶的是，如果输入按排序顺序添加，情况会更糟：
>>> w.clear()
>>> for x in sorted(xs):
... w.add(x)
>>> w.get()
0.5021045181828147
用户小心！这是代码：
class MedianEst:
def __init__(self, B):
assert B > 1 and B & 1
self.B = B
self.half = B >> 1
self.clear()
def add(self, x):
for xs in self.a:
xs.append(x)
if len(xs) == self.B:
x = sorted(xs)[self.half]
xs.clear()
else:
break
else:
self.a.append([x])
def get(self):
total = 0
weight = 1
accum = []
for xs in self.a:
total += len(xs) * weight
accum.extend((x, weight) for x in xs)
weight *= self.B
# `total` elements in all
limit = total // 2 + 1
total = 0
for x, weight in sorted(accum):
total += weight
if total >= limit:
return x
def clear(self):
self.a = []