解决问题:
在不知道数据规模n的前提下,实现以的概率去数据进行采样
思路:
首先设计容量为k的容器C,把前k个元素放入,之后遍历到第m个元素时,以的概率选中当前元素,若当前元素被选中,则以的概率替换容器C中的元素(即容器C中的元素被替换的概率相同)。遍历完成后,可以保证数据中每个元素均以的概率被选中。
证明:
不写详细过程,只写大概思路:
- 分2部分去证明,1部分是证明k之前的元素,1部分是证明k之后的元素
- 通过证明某元素被替换掉的概率,然后取补集则可以更加容易的求出该元素不被替换掉的概率