Golang 蓄水池抽样法

August 29, 2020

这篇文章介绍了如何在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
}
Go抽样

IARNO

服务端开发

Golang excel导出

hexo博客迁移