python - NumPy:计算累积中位数

Question

我有大小为 n 的样本。

我想为每个 i 计算:numpy 中 sample[:i] 的 1 <= i <= n 中位数。 例如，我计算了每个 i 的平均值:

cummean = np.cumsum(样本)/np.arange(1, n + 1)

我可以在没有循环和理解的情况下对中位数做类似的事情吗？

Answer 1

知道 Python 有一个 heapq 模块可以让你保持一个可迭代的运行“最小值”，我搜索了 heapq 和 median，并找到了蒸介质的各种元素。这个:

http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/

有一个 class streamMedian 维护两个 heapq，一个是下半部分的值，另一个是上半部分的值。中位数是一个的“顶部”或两个值的平均值。该类有一个insert 方法和一个getMedian 方法。大部分工作都在 insert 中。

我将其复制到 Ipython session 中，并定义:

def cummedian_stream(b):
    S=streamMedian()
    ret = []
    for item in b:
        S.insert(item)
        ret.append(S.getMedian())
    return np.array(ret)

测试:

In [155]: a = np.random.randint(0,100,(5000))
In [156]: amed = cummedian_stream(a)
In [157]: np.allclose(cummedian_sorted(a), amed)
Out[157]: True
In [158]: timeit cummedian_sorted(a)
1 loop, best of 3: 781 ms per loop
In [159]: timeit cummedian_stream(a)
10 loops, best of 3: 39.6 ms per loop

heapq 流方法要快得多。

---

@Uriel 给出的列表理解相对较慢。但是如果我用 np.median 代替 statistics.median 它比 @Divakar 的 排序解决方案更快:

def fastloop(a):
    return np.array([np.median(a[:i+1]) for i in range(len(a))])

In [161]: timeit fastloop(a)
1 loop, best of 3: 360 ms per loop

@Paul Panzer 的分区方法也不错，但与流类相比仍然很慢。

In [165]: timeit cummedian_partition(a)
1 loop, best of 3: 391 ms per loop

(如果需要，我可以将 streamMedian 类复制到此答案)。