find the median of an infinite data stream of integers - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

find the median of an infinite data stream of integers

find the median of an infinite data stream of integers# JobHunting - 待字闺中

s*r2012-06-14 07:06

1 楼

昨天遇到的题目，大家有啥好的解答吗，我当时没答上来。每来一个数字之后，我要能
查到开始到当前的median。

j*e2012-06-14 07:06

2 楼

你能记录以前所有的数字么？如果不能记录，只能返回estimated median。
如果记录的话，搞个BST，额外记录左右子树的节点数，这样每来个数字，都是
logN的复杂度。

【在 s********r 的大作中提到】

: 昨天遇到的题目，大家有啥好的解答吗，我当时没答上来。每来一个数字之后，我要能
: 查到开始到当前的median。

s*r2012-06-14 07:06

3 楼

不能记录所有的数字，能记录的话用两个堆就可以了。 estimated median 也行，怎么
算的。

t*r2012-06-14 07:06

4 楼

如果不能记录所有的数字的话
我可以
1 1000 1000 1000 ...（100000000个1000）0 0 0 ... (100000000个0)

【在 s********r 的大作中提到】

: 不能记录所有的数字，能记录的话用两个堆就可以了。 estimated median 也行，怎么
: 算的。

j*e2012-06-14 07:06

5 楼

有proximation算法，我大概记得的一个算法是：
每来一个数据D，跟当前的median比较，如果D大，那么就增加median，
否则就减少median。那这个增加和减少的step有多种选法，例如
a const small number，或者根据数据的variance，或者density estimation
等。我记得能保证这样的得到的数的expectation是median，而且可以
用于任何quantile （例如75-percentile).

【在 s********r 的大作中提到】

: 不能记录所有的数字，能记录的话用两个堆就可以了。 estimated median 也行，怎么
: 算的。

b*o2012-06-14 07:06

6 楼

对于one pass算法,
（1）要求exact median, 可以证明内存需要至少是N/2。
（2）如果允许用随机算法，对于内存量是s，可以先用reservoir sampling采样出s个
sample,然后在对这s个数求median。你可以用概率公式算一下误差。
（3）如果允许approximate median,可以把内存量减少到(log(N))^2。大致想法是把
已经扫描过的数作类似quantization的压缩:对于长度为s的buffer，每个元素不但存一
个value(i),而且还存一个weight(i)。所有的weight加起来就是目前扫描过的数的总数
。算法的关键是要保证：在任何时刻，如果把value(i)重复weight(i)次,然后把所有这
样重复出来的数组成一个stream，用它来计算median，和用原数组计算median，能大致
相当
。细节可参看以下paper:
http://infolab.stanford.edu/~manku/papers/98sigmod-quantiles.pd