这篇文章介绍了如何在Go语言中实现蓄水池抽样法。蓄水池抽样法是一种等概率随机抽取的方法,适用于从大量数据中抽取样本。文章首先构建了一个可以放置m个元素的蓄水池,然后将前m个数依次放入。从第m+1个元素开始,以m/n的概率决定元素是否被替换到池子中。当遍历完所有元素后,就可以得出随机挑选的k个元素。该方法的时间复杂度为O(n)。
相关文章
https://www.cnblogs.com/snowInPluto/p/5996269.html
代码示例
const Num = 10
/**
* 蓄水池抽样法
* 先构建一个可以放m个元素的蓄水池
* 将前m个数依次放入,从第m+1个元素开始,以m/n的概率决定元素是否被替换到池子中
* 当遍历完所有的的元素后,及得出随机挑选的k个元素,时间复杂度为O(n)
*/
func sampling(ids []string) []string {
reservoir := make([]string, 10)
for i := 0; i < Num; i++{
reservoir[i] = ids[i];
}
for i := Num; i < len(ids); i++ {
/*随机获得一个[0, i]内的随机整数*/
d := rand.Intn(i + 1)
/*如果随机整数落在[0, m-1]范围内,则替换蓄水池中的元素*/
if d < Num {
reservoir[d] = ids[i]
}
}
return reservoir
}