一道算法题——从数据流中随机去m个数

题目：有一个很大很大的输入流，大到没有存储器可以将其存储下来，且只输入一次，如何从这个输入流中随机取得m个记录。

我的思路：

首先，存储开始的m条记录，存放于数组result[m]中；

然后，假设有n条记录，每一次读取记录后，取随机数x，0<= x < n；
判断随机数，
    当0<= x < m时，我们将记录存放到result[x]中；
    当m<= x < n时，我们不存这个记录；

最后，输入所有的数据流后，result[m]存放的就是随机出来的m条记录。

    分析下，我们期待的某一个记录被选中的概率为m/n，按照我的这个算法，第i个记录被选中的事件可以描述成“该记录被选在数组里并且后面的记录都没有替代这个位置”，概率为

        p = m/n * (1- 1/n)^(n-m-i)

    很显然，这个对于所有的i，这个值都是趋近于m/n的。算法结果应该是正确的。
    欢迎踊跃拍砖！

 

//==========================================更正

 

重新想了想，这个方法不是绝对公平的随机，每个数被选中的概率不是都相等，正如回复中说的，前m个数的P一样，对于后来的数，P越来越大。

 

欢迎提出新办法！

 

 

评论

2 楼 peizhyi 2013-06-03  

zdbill 写道

“存储开始的m条记录”，你不觉得前m条记录选中的概率比后面的记录要大很多吗？

感觉好像是，但用上面的概率公式看，i越大，P越大，最大达到m/n。
也就是说：
前面m个数的概率是i=0的时候P的值，是最小的；
但m以后的数，P的概率越来越大，最后趋近m/n。
这个方法的确没有保证平等的概率，希望一起讨论更公平的方法。

1 楼 zdbill 2012-09-29  

“存储开始的m条记录”，你不觉得前m条记录选中的概率比后面的记录要大很多吗？