数据流中的中位数 | Baeldung中文网

1. 简介

在本文中，我们将介绍两种用于计算数据流中位数的算法。由于数据流的特殊性（数据量大、无法一次性加载到内存），传统的排序求中位数方式不再适用，我们需要使用专门的流式算法。

2. 数据流中的中位数

中位数是一个样本中将数据范围一分为二的值。在静态数据集中，我们通常通过排序后取中间值来计算中位数：

若样本个数 n 为奇数：median = x[n/2]
若为偶数：median = (x[n/2] + x[n/2 + 1]) / 2

但这种方式要求我们能完整存储并多次遍历数据，在数据流场景中不可行。

2.1 数据流的特点

数据量极大，无法一次性加载到内存
数据逐条到达，通常只能遍历一次
某些情况下无法回溯已读取的数据

因此，我们不能使用传统排序方法计算中位数，而必须使用低内存复杂度的流式算法。

3. 对称分布下的中位数估算

如果数据服从对称分布（如正态分布或均匀分布），中位数等于均值。此时我们可以使用流式均值算法估算中位数：

algorithm StreamingMeanAlgorithm(stream):
    n <- 0
    mean <- 0

    while stream is not empty:
        n <- n + 1
        x <- get the next element of stream
        mean <- ((n - 1) * mean + x) / n

    return mean

✅ 优点：

时间复杂度 O(n)
空间复杂度 O(1)

⚠️ 注意：仅适用于数据分布对称的情况，否则误差较大。

4. P² 算法（Piecewise Parabolic Quantile Estimator）

若无法确定数据分布，则可使用 P² 算法估算中位数。该算法是流式分位数估算的一种经典方法。

4.1 核心思想

P² 算法维护 5 个标记（markers）来估算分位点：

q1：最小值（0%）
q2：25% 分位数
q3：中位数（50%）
q4：75% 分位数
q5：最大值（100%）

算法在读取数据流时动态调整这 5 个标记的位置，以逼近实际分布的分位点。

4.2 更新逻辑

每个标记 qi 都关联一个 ni，表示当前已读取的数据中小于等于 qi 的数量。

理想情况下，ni 应该接近某个目标值 n’i：

n’1 = 1
n’2 = 0.25(n - 1) + 1
n’3 = 0.5(n - 1) + 1
n’4 = 0.75(n - 1) + 1
n’5 = n

当读入新元素 x 后，更新所有 ni（若 x >= qi），然后检查 |ni - n’i| >= 1，若成立则更新 qi。

4.3 调整公式

P² 使用两种方式调整标记：

抛物线插值公式（Parabolic Formula）：

q_i \leftarrow q_i + \frac{d}{n_{i+1}-n_{i-1}} \left((n_i - n_{i-1} + d) \frac{q_{i+1} - q_i}{n_{i+1} - n_i} +  (n_{i+1} - n_i - d) \frac{q_i - q_{i-1}}{n_{i} - n_{i-1}}\right)

线性插值公式（Linear Formula）（当抛物线公式破坏顺序时使用）：
```
q_i \leftarrow q_i + d\frac{q_{i+d} - q_i}{n_{i+d} - n_i}
```

其中 d = sgn(ni - n’i)。

4.4 实现细节

初始阶段：前 5 个元素排序后初始化 q1~q5，并设置 n1~n5 = 1~5
更新顺序：先更新 n’i，再更新 ni，最后判断是否调整 qi
保证 q1 ≤ q2 ≤ q3 ≤ q4 ≤ q5，否则使用线性公式替代

4.5 伪代码

algorithm P2Algorithm(stream):
    // 初始化前5个元素
    for n <- 1, 2, 3, 4, 5:
        x_n <- get the next element of stream
    Sort x_1, x_2, x_3, x_4, x_5
    Initialize q_i and n_i accordingly
    n <- 5

    while stream is not empty:
        n <- n + 1
        x_n <- get the next element of stream
        Update ideal positions n'_i
        Find j such that x_n >= q_j
        for i <- j to 5:
            n_i <- n_i + 1
        for i <- 2, 3, 4:
            d_i <- n'_i - n_i
            if |d_i| >= 1:
                d <- sgn(d_i)
                Use parabolic or linear formula to adjust q_i
                q_i <- new value
                n_i <- n_i + d

    return q_3

4.6 优化与权衡

精度 vs 性能：使用更多标记（如 7 个）可能提高精度，但会增加计算开销
曲线拟合 vs 线性逼近：抛物线插值更精确，但计算更复杂

4.7 时间与空间复杂度

✅ 空间复杂度：O(1)，仅维护固定数量的标记
✅ 时间复杂度：O(n)，每条数据只处理一次

5. 示例演示

我们以如下数据流为例：

x = [50, 30, 20, 40, 10, 10, 20]

5.1 初始化阶段

读取前 5 个数并排序：

[10, 20, 30, 40, 50]

初始化：

q1=10, q2=20, q3=30, q4=40, q5=50
n1=1, n2=2, n3=3, n4=4, n5=5

5.2 第6个元素 x=10

更新 n’i：

n’2=2.25, n’3=3.5, n’4=4.75

更新 ni：

n1=2, n2=3, n3=4, n4=5, n5=6

所有差值 < 1，不调整。

5.3 第7个元素 x=20

更新 n’i：

n’2=2.5, n’3=4, n’4=5.5

更新 ni：

n1=2, n2=4, n3=5, n4=6, n5=7

此时 |n’2 - n2| = 1.5, |n’3 - n3| = 1，需要调整 q2 和 q3。

使用抛物线公式调整 q2：

q'_2 = 20 - \frac{1}{3}(1\cdot 10 + 2\cdot 5) = 20 - \frac{20}{3} \approx 13.33

由于 10 < 13.33 < 30，接受该调整。

6. 总结

✅ 两种主要方法：

流式均值法：适用于数据分布对称的场景（如正态分布）
P² 算法：适用于任意分布，通过动态调整标记估算中位数

✅ P² 的优势：

低内存占用（O(1)）
一次遍历完成（O(n)）
支持任意分位数估算（中位数是 50% 分位数）

⚠️ 注意事项：

P² 是近似算法，精度取决于数据分布和标记调整策略
不建议用于对精度要求极高的场景

如果你正在处理实时数据流（如日志、传感器数据、交易数据等），并且需要快速估算中位数，P² 是一个非常实用的选择。

Persistence

REST

Security