概述

对于一个输入流，如果已知文件的总大小L，要取出其中的n个数据，并且要求所取出的文件都是等概率的，那么只需要根据n/L的概率来取数据就okay了。
然而在大多数情况下，L并不可知，此时还要求按照等概率来取n个数据，如何做到呢？

方法

1. 先依次从数据流中取n个数据
2. 从第n+1个数据开始，以n/i的概率来保留新数据，如果新数据要保留，那么旧数据以1/n的等概率淘汰
3. 旧数据保留的概率为1-n/i

论证（假设n=10）

1. 当有10个数据时，数据全部都保存，item的保留概率是1
2. 当有11个数据时，数据的保留概率为：10/11。旧数据的保留概率为（1）*（1/11 + 10/11 * 9/10）= 10/11。
   （1）为2的前提1的概率，1/11为旧数据的保留概率：1-10/11=1/11，10/11为保留新数据的概率，9/10为，当出现保留新数据时，旧数据保留的概率：1-1/n
3. 当有12个数据时，数据的保留概率为：10/12。旧数据的保留概率为（10/11）*（2/12 + 10/12 * 9/10）= 10/12。

以上可得出，当有i个数据的时候，数据保留的概率为 10/i。