海量数据等概率选取问题
<div id="cnblogs_post_body">1、问题定义可以简化如下：在不知道文件总行数的情况下，如何从文件中随机的抽取一行，并且每行被抽中的概率相等？首先想到的是我们做过类似的题目吗？当然，在知道文件行数的情况下，我们可以很容易的用C运行库的rand()函数随机的获得一个行数，从而随机的取出一行，但是，当前的情况是不知道行数，这样如何求呢？我们需要一个概念来帮助我们做出猜想，来使得对每一行取出的概率相等，也即随机。这个概念即蓄水池抽样（Reservoir Sampling）。
有了这个概念，我们便有了这样一个解决方案：定义取出的行号为choice，第一次直接以第一行作为取出choice ，而后第二次以二分之一概率决定是否用第二行替换 choice ，第三次以三分之一的概率决定是否以第三行替换 choice &hellip;&hellip;，以此类推，可用伪代码描述如下：
<div class="cnblogs_code">i = 0while more input lines with probability 1.0/++i choice = this input lineprint choice
页:
[1]