Redian新闻
>
find the median of an infinite data stream of integers
avatar
find the median of an infinite data stream of integers# JobHunting - 待字闺中
s*r
1
昨天遇到的题目,大家有啥好的解答吗,我当时没答上来。每来一个数字之后,我要能
查到开始到当前的median。
avatar
j*e
2
你能记录以前所有的数字么?如果不能记录,只能返回estimated median。
如果记录的话,搞个BST,额外记录左右子树的节点数,这样每来个数字,都是
logN的复杂度。

【在 s********r 的大作中提到】
: 昨天遇到的题目,大家有啥好的解答吗,我当时没答上来。每来一个数字之后,我要能
: 查到开始到当前的median。

avatar
s*r
3
不能记录所有的数字,能记录的话用两个堆就可以了。 estimated median 也行,怎么
算的。
avatar
t*r
4
如果不能记录所有的数字的话
我可以
1 1000 1000 1000 ...(100000000个1000)0 0 0 ... (100000000个0)

【在 s********r 的大作中提到】
: 不能记录所有的数字,能记录的话用两个堆就可以了。 estimated median 也行,怎么
: 算的。

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

【在 s********r 的大作中提到】
: 不能记录所有的数字,能记录的话用两个堆就可以了。 estimated median 也行,怎么
: 算的。

avatar
b*o
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
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。