bgping
@bgping
·
未知输入流总量，取出n个数据，要求取出的数据是等概率的
# 概述 对于一个输入流，如果已知文件的总大小L，要取出其中的n个数据，并且要求所取出的文件都是等概率的，那么只需要根据n/L的概率来取数据就okay了。 然而在大多数情况下，L并不可知，此时还要求按照等概率来取n个数据，如何做到呢？ ### 方法 1. 先依次从数据流中取n个数据 2. 从第n+1个数据开始，以n/i的概率来保留新数据，如果新数据要保留，那么旧数据以1/n的等概率淘汰 3. 旧…