有一个很大很大的输入流，大到没有存储器可以将其存储下来， 而且只输入一次，如何从这个输入流中随机取得n 个记录。采用何种方法,才能在不需要存储数据流的基础上,获得这
n个等概率的随机数据呢?
That is, If m<=n, just keep it. For m>n, generate a random number R=rand(m) in [0, m), replace a[R] with new number
if R falls in [0, n).
程序如下：
#include <iostream>
using namespace std;
void sample(int n,int* output)
{
int m=0;
int val;
while(m<n && cin>>val)
output[m++]=val;
while(cin>>val)
{
m++;
if(rand()%m<n)
output[rand()%n]=val;
}
}
此方法正确性证明：
1.由于一共n个元素被存储，所以选取其中一个元素的概率为1/n（这个暂时放着，后面要用到）
2.如图
我们先求n个数据中，一个数据被最终取到的概率，显然需要所有s个数据（假设数据总数为s）中每个数字被取得的概率均等，即为1/s。
如果要n个数据中的第一个数据被取得，就是没有被后续数据的任何一个数据所替换。
先来求没有被第n+1个数据替换的概率：
先求取相关概率吧，以n/k概率判断是否取，即为：
取得的概率——n/(n+1)
不取得的概率——1/(n+1)
取得并与第一个数据交换的概率(n/(n+1)) * (1/n)
所以：第一个数据不被第n+1个数据替换的概率为(1 - (n/(n+1)) * (1/n))
化简为：n/(n+1)
这是第n+1个数据，那么 后续数据呢？依次可得
不被第n+2个数据替换的概率：(n+1) / (n+2)
不被第n+3个数据替换的概率：(n+2) / (n+3)
…………………………………………………………………………………………………
不被第s-1个数据替换的概率: (s-2) / (s-1)
不被第s个数据替换的概率： (s-1) / s
综合起来，第一个数据不被替换的概率为各个概率的乘积，也就是：
(n/(n+1)) * ((n+1)/(n+2)) * ((n+2)/(n+3)) * …… * ((s-2)/(s-1)) * ((s-1)/s)
这个，前后项上下约分咯，结果化简后是： n/s。
3.可以用到第一步的那个概率咯，因为第一个数据为前n个数据中的一个，而最终的结果是n个数据中随机的一个，所以第二步求得的概率还需要乘以第一步中的1/n，结果就是(n/s) * (1/n)即为1/s，果然是我们期待的结果。既然每个数据取得的概率都是1/s，那么，等概率。