常用算法

2022-09-18 23:05:00
admin
原创 924
摘要:常用算法

一、常用算法

Reservoir Sampling,蓄水池算法,用来解决大量数据的采样问题,算法过程如下:

1、假设数据规模为n,需要采样的数量为k;
2、首先构建一个可容纳k个元素的数组,并将数据的前k个元素放入数组;
3、从第k+1个元素开始,假设是第m个元素,它会以k/m的概率进入数组,数组中每个元素被替换的概率是1/k;
4、当遍历完所有元素之后,数组中剩下的元素即为所需采取的样本;
5、对于其中每个元素,被保留的概率都为k/n;

发表评论
评论通过审核之后才会显示。