Archive for 2014年11月

水塘抽样 (reservoir sampling)

十一月 21, 2014

题目:从n个物品中等概率取出k个。

最直接的想法:先把n个物品乱序,然后取出前k个。缺点是需要n个随机数,且需要排序,太复杂。实际上完全不需要这么复杂。

进一步需求:在不知道n的时候怎么办(比如数据来自一个数据流)?

答案:

设想数据不断传来。当数据个数不超过k时,当然应该直接把所有数据都选中。

第k+1个数据传来时,我们需要做个操作,使得这个新数据以及所有已有的数据被选中的几率为k/(k+1);换句话说,已有的数据有1/(k+1)的几率被踢掉。具体做法是,只需要生成1到k+1之间的整型随机数,如果这个随机数不超过k,就把相应位置的数据替换成新数据,否则不操作。

进一步,假设当收到第n个数后我们的操作满足题目的要求,即每个数被选中的几率为k/n,问第n+1个数到来时应该怎么操作。同样,生成1到n+1之间的随机整数,如果这个整数不超过k,则把相应位置的数据替换成新数据,否则不操作。新数据被选中的几率是k/(n+1),而旧数据不被替换的几率是n/(n+1),考虑到旧数据已被选中的几率本身是k/n,于是旧数据继续呆在那里的几率是k/(n+1)。正确。

所以,不需要知道总共有多少数据,只需要知道当前收到了多少数据就可以了。

Advertisements