本文共 557 字，大约阅读时间需要 1 分钟。

转载自   

Reservoir Sampling( Reservoir sampling ) 

这是我在今年求职过程中面试的时候被问到的，因为之前很少接触Streaming的算法，在听到这个题目的时候被惊呆了，根本不能理解：  

给一个Streaming的Data，未知长度，要求在Streaming结束后返回N个Data，且是等概率的。  

在听到这个问题的时候简直惊呆了。如果Streaming长度已知为L，当然对于每一个Data，我生成一个N/L的概率即可。但是长度未知，也即概率未知，怎么可能在Data来的时候判断要不要保留这个Data，还能保证是等概率的……百思不得其解。  

事后一番研究，才发现了这类算法，算法之简单令人惊叹：  

首先保留前N个Data，对于后面来的Data以N/i的概率选择是否保留，i为当前Data序号，保留的话在原来保留的N的Data中随机剔除一个。最后返回这N的即可。  

证明也很容易，奇妙得地方在于在计算概率的时候，出现了很长的，可以前后上下不断约掉的分式。相互约去之后剩下的概率刚好是N/L，L为总长度。简直美妙极了！ 

显然这类算法也非常有用，因为在实际问题中会出现大量需要在Streaming的数据中进行Sample，为下一步处理数据做准备的情形。而这竟然有一个O(L)的算法，真是太惊艳了！

转载地址：https://maokun.blog.csdn.net/article/details/81369525 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！